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

Question

我正在纠结这是否是可判定的:

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

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

Answer 1

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

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

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

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

但是也就是说，这个证明是非构造性的。我们可以证明语言必须是可判定的，但我们实际上找不到总是停止接受它的 TM!其实没人知道是哪个TM，因为Goldbach's Conjecture (是否每一个大于二的偶数都是两个质数之和)是数学中的一个悬而未决的问题。

希望这对您有所帮助!