阅读时有任何问题/意见欢迎随时在评论区交流🤺
1. 证明存在非递归枚举语言
接下来我们将使用对角化方法证明存在任何图灵机不可接受的语言 。
首先，图灵机是可以进行编码的，简单来看就像我们的C程序一样。那么，任何图灵机都可以表示为一个有限长度的串，这意味着只有可列个图灵机，或者而言，有“第i个图灵机”这种说法。
接下来有两种证明方法，
- 说明“语言的数量”要多于“图灵机的数量”，但任何图灵机都只能接受一种语言，因而不能建立从图灵机到语言的满射，因此总有某个语言使任何图灵机无法接受。
- 开门见山，直接找一个任何图灵机不能接受的语言。
1.1. 证明语言比图灵机更“多”
以下内容和证明实数是不可列的方法非常相似。
假设所有语言的集合是可列的，那么任何语言都有一个编号，而且也可以表达成一个特征向量的形式，即如果该语言能包含第i个字符串（注意，某个符号集$latex \Sigma$上的所有字符串当然是可列的），那么特征向量的第$ latex i$位为1，否则为0。因此所有语言都可以像这样排列在一个表中：
n f(n)
--------------
1 0101010...
2 1010011...
3 1110001...
4 0100011...
...我想，现在已经把每一个语言表示成了一个“实数”。接下来形式化地完成剩余的证明。
现在我们考虑构造一个语言$L$，它的特征向量中，第$i$个分量不等于$f(i)$的第$i$个分量，可以看出这样的语言实际上有很多，我们只取一个就好。但很容易发现$L$不能被分配任何自然数编号，否则总是会产生矛盾。因此这与”所有语言的集合可列”的假设矛盾。
1.2. 找一个语言证明它不能被任何图灵机接受
像上面一样，再列一个表，只是这次该表中存放从图灵机编号到语言的映射。换言之，这张表表示的是第i个图灵机能表示什么语言。
现在构造一个语言L_d，对于任意自然数i，如果w_i不属于L(M_i)，那么w_i属于L_d。容易发现这样的语言是存在的。
假设L_d是第j个语言，那么请问w_j是否属于L_d？矛盾就出现了。
2. 证明存在是递归可枚举但不可判定的问题
2.1. 停机问题
大名鼎鼎的停机问题。题干是：给定图灵机编码和一段输入，问该图灵机在该输入上是否停机？
首先从直观上理解该问题，请看Python代码。
def halt(func, in):
...
def halt_or_not(in):
if halt(halt_or_not, in):
loop_forever()
else:
return假如有一个halt函数能在有限时间内判断函数func在输入为in时是否停机，那么构造一个新的函数halt_or_not，如果halt说它会停，它就陷进死循环；如果halt说它不会停，它马上就停。总之不论哪种情况下它都狠狠打了halt的脸，因此符合上述要求的halt是不可能存在的。
上面的伪代码非常容易理解，但如果用于图灵机证明会有些困难，因为当我们试图构建图灵机halt_or_not时，我们发现它自身的编码还没有定义完整，所以对if语句建模时会产生问题。我们对其进行修改如下：
def halt(func, in):
...
def fku_halt(func):
if halt(func, func.__code__):
loop_forever()
else:
returnfku_halt正如其名，它要和halt唱反调。如果halt说某个函数能停，它就不干了；反之就返回。其实，如果给fku_halt传入它自己的编码，那么条件分支语句处就会变成 halt(fku_halt, fku_halt.__code__)，和最开始所说的情况是一样的了，将产生一个矛盾。
接下来给出在图灵机上的证明。
假设有图灵机能以停机方式解决这个问题，设其为H，它的输入为图灵机编码M和输入字符串x。如果M在x上能停机，则停机并接受，否则停机并不接受。
接下来构造图灵机J，它获取一份图灵机编码M，并模拟H进行判断：图灵机M在输入为<M>时（其实也可以是别的什么串，无所谓）是否会停机？如果停机，J就陷入死循环；否则，J就停机。
现在J已经定义好了，那J的编码作为J的输入会怎么样？我们发现，如果J没有停机，那么这是因为H认为J会停机所造成的；如果J停机了，那么这是因为H认为J不会停机所造成的。根据定义H一定是正确的，但J停机与否的事实更是正确的，现在二者给出的结果互相矛盾，说明二者都是错的！
现在我们证明了停机问题是不可判定的。然而，存在一个图灵机以终结状态接受它对应的语言，即模拟输入的图灵机在输入的字符串上做状态转移。如果模拟过程结束了，我们构造的图灵机也就停机了；反之，不要求停机。所以它对应的语言仍是递归可枚举的。
2.2. 归约
有了停机问题作为种子，我们可以证明其它一些问题的不可判定性，思路是：反设待证问题是可判定的，我们将可以用它来判定一些已明确证明是不可判定的问题（即归约），从而产生矛盾。
我们把以终结状态接受停机问题语言的图灵机记为H。
2.2.1. 判断某图灵机M是否能接受某输入串？（成员性测试）
令A为该问题的图灵机，假设它以停机方式接受。现在我们可以用它解决停机问题，即把停机问题归约到成员性测试问题上。
我们可以先让H模拟A，如果A表示接受，说明给定的图灵机M接受了给定的输入，那么M肯定停机了，因此H可以接受。
如果A不接受，我们可以构造为A的终结状态取补的图灵机A’，它的语言为A的语言的补。再让H模拟A’，如果A’表示接受，说明给定的图灵机M拒绝了给定的输入，那么M还是肯定停机了，因此H可以接受。
如果A’也不接受，说明M根本没有停机，所以H会拒绝。
那么停机问题成为了一个可判定问题，产生矛盾，所以A不能以停机方式接受。
A的递归可枚举性显而易见，不再赘述。
2.2.2. 判断某图灵机M的语言是否不为空？（非空性测试）
令NE为该问题的图灵机，假设它以停机方式接受。我们将用它解决成员性测试问题。
显然，如果M为空，那么M不会接受任意的串，也包括w，所以A拒绝。
但如果M不为空，并不能说明M就一定会接受w。为此，我们构造一个新的图灵机M_w，它以一个串作为输入，首先判断该串是否为w，不是则拒绝，是则完全模拟图灵机M的行为。这样，要是M_w的语言不为空，那只能包含一个串，即w，并说明M接受w。反之，M_w的语言为空，并说明M不接受w。
因此，我们可以直接把M_w交给NE来测试非空性，如果NE接受，就说明M接受w，反之亦然。我们又一次判定了一个不可判定的问题。因而L(NE)是不可判定的。
至于递归可枚举性，我们可以将NE构造为NTM，利用非确定性的超能力去猜测。如果L(M)非空，那么NTM将猜到其中的一个串并接受；否则，L(M)会无穷尽地猜下去，并不停机。因而我们证明了L(NE)是RE。
注意，上述的NTM不停机并不能用来说明非空性测试是不可判定的，因为可能只是你太笨没有构造出一个合适的停机图灵机而已 🙂
2.3. 通法——莱斯定理
事实上，RE语言的所有非平凡性质都是不可判定的，这就是莱斯定理。
性质：是RE语言的一个集合，这个集合中的所有语言满足一个使用命题来描述的性质。例如，“是上下文无关的”的性质，就是所有CFL的集合；“为空集”的性质，就是{\varnothing}。
平凡的：如果某性质P为空，或为全体RE，则为平凡性质。注意，空性质和“为空集”的性质不是一回事，前者是平凡的而后者不是。
至于“不可判定”这个定语，我们之前一般都把它用来修饰一个语言，即该语言不存在一个停机图灵机来接受。但语言的集合不能表示成语言，因为语言通常是无穷集合，不可能写成有限长度的串。所以，更准确地来说，“不可判定”修饰的是“所有接受这些语言的图灵机编码的集合L_P”，毕竟图灵机编码的长度是有穷的。当我们讨论一个性质P的不可判定性时，我们实际上指的是L_P的不可判定性。
2.3.1. 莱斯定理的运用
在正式证明莱斯定理之前，我们先通过使用它，来获得一个初步的了解。例如我们要证明“不存在一个图灵机E，以图灵机M的编码作为输入，如果L(M)为空则E接受，反之则拒绝”。
反设E存在，那么，所有接受语言“为空集”的图灵机的编码构成一个集合，它正是E所接受的语言。由于“为空集”这一性质包含一个语言\varnothing，因而它是非平凡的，根据莱斯定理可知L(E)是不可判定的，这与E的定义相矛盾，毕竟定义中的E所接受的是一个递归语言。
2.3.2. 莱斯定理的证明
还记得前面提到的成员性测试吗？我们将其中的图灵机称为A。令A接受的语言为L_A，其中每一个串的形式为(M,w)的二元组，即以M为编码的图灵机接受输入w。我们已经证明它是一个RE且非递归的语言，即不可判定。接下来，对于任意的非平凡性质P，我们将会假设L_P是可判定的，并构造从L_A到L_P的归约。L_A是明确的不可判定的语言，所以假设错误，故而L_P是不可判定的。
首先假设空集合不属于P，之后我们会讨论相反的情形。这样的话，因为P是非平凡的，所以必有一个非空语言L属于P，设图灵机M_L接受该语言。
和2.2.2.节中证明空性的不可判定类似，我们对M_L做一点小小的改造（记为M’）。通过判断M’的语言是否属于性质P，我们可以得出M是否接受w。M’的输入和M_L类似，都是获取一个串x，其具体构造如下：
- 先在w上模拟M。模拟可能停止也可能不。
- 如果M接受w，则M’在x上模拟M_L。我们可以发现，如果走这条分支，L(M’)=L(M_L)，所以M’的语言具有性质P。
- 如果M不接受w，就停机，总之永不接受输入x。M还有可能不停机，此时M’本身也不停机，所以实际上也是什么都不接受。如果走这条分支，L(M’)=\varnothing，我们刚才明确地假设过\varnothing不属于P，所以M’的语言不具有性质P。
因而，我们得到了一个归约算法，可以将(M,w)转化为自动机M’。L_P包含M’的编码，当且仅当M接受w，即(M,w)属于语言L_A。但L_A是不可判定的，从而导致矛盾，所以P是不可判定的。
另一方面，如果空集合属于P，我们考虑P的补P’，根据上述证明过程，P’是不可判定的。现在反设L_P是可判定的，因为递归语言对补封闭，(L_P)’也是可判定的。由于所有TM都接受RE，故任何TM的语言要么属于性质P，要么属于性质P’，所以(L_P)’=L_(P’)，所以L_(P’)是可判定的，但我们已经知道P’是不可判定的。所以L_P，即P，仍然是不可判定的。
2.3.3. 莱斯定理证明过程的特化
作为练习，我们用莱斯定理的证明步骤说明L_NE是不可判定的，来加深对它的证明方法的理解。
NE接受图灵机M的编码，当且仅当M的语言非空，即M的语言具有“非空的”性质P，该性质不包含空集。反设L_NE是可判定的，我们将会用它来推出L_A的可判定性，产生矛盾。
任取一个接受语言具有“非空的”性质的图灵机M_L，我们将其改造为M’，M’的语言“非空”当且仅当M接受w。
- 首先在w上模拟M；
- M接受w，则M‘在输入x上模拟M_L，故接受的语言一定是非空的；
- M拒绝w，则M’什么都不接受，故接受的语言一定是空的。
下面由NE判断M’的语言是否为非空，是则说明M接受w，不是则说明M拒绝w，归约完成。
