math - 这种语言是可判定的吗？

Question

我正在为这是否可以确定而苦苦挣扎：

A = {x 是自然数集的一个元素 | 对于每个大于 x 的 y，2y 是两个素数之和}

我倾向于认为这是可以决定的，因为当输入图灵机时，它永远不会达到接受状态并无限循环，除非它拒绝。但是，我也知道，要确定一种语言，必须只存在一种算法来确定它；我们不一定要知道它是如何完成的。有了这个，我的一部分认为它是可判定的？有人知道如何证明吗？

Answer 1

这种语言是可判定的，尽管证明有点邪恶。

首先，让我们考虑一下这种语言的属性。显然，如果 n 是语言中包含的自然数，那么每个大于 n 的数也都包含在语言中。因此，这种语言可以采用三种可能的形式：

1. 该语言包含所有自然数，或
2. 该语言不包含自然数，或
3. 该语言包含所有大于某个自然数 n 的自然数。

语言 (1) 和 (2) 分别是 {0, 1}* 和空语言，它们都是可判定的（因此有些 TM 总是停止接受这些语言）。每种形式 (3) 的语言也是可判定的，因为对于任何 n，我们都可以轻松地编写一个将 n 硬编码到其中的 TM，它只检查输入是否至少为 n。因此，无论哪种情况为真（1、2 或 3），都会存在一些始终停止的 TM，其语言是您提供的语言，因此您的语言是可确定的。

但话虽如此，这个证明是非建设性的。我们可以证明该语言必须是可判定的，但我们实际上无法找到始终停止的 TM 接受它！事实上，没有人知道它是哪个 TM，因为哥德巴赫猜想（是否每个大于 2 的偶数都是两个素数之和）是数学中的一个悬而未决的问题。

希望这可以帮助！