这种语言是否可判定？

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,因为Goldbach的猜想(无论每个偶数大于2都是两个素数的总和)都是数学中的一个开放问题.

希望这可以帮助!