停机问题^[1]

可判定性

检测一个特定的确定型有穷自动机是否接受一个事先给定的串，此问题可以表示为语言$A\mathrm{\_}DFA$，它包含了所有DFA的编码以及DFA接受的串的编码：

$$A\mathrm{\_}DFA=\{<B,w>|B\mathrm{是}DFA\mathrm{且}\mathrm{接}\mathrm{受}\mathrm{输}\mathrm{入}\mathrm{串}w\}$$

问题“$B$是否接受输入$w$”与问题“$<B,w>$是否是$A\mathrm{\_}DFA$的元素”是等价的。类似的，其他一些计算问题也可以表示成检查语言的成员隶属关系，证明这个语言是可判定的与证明这个计算问题是可判定的是一回事。

只要证明$A\mathrm{\_}DFA$是可判定的，也就证明了“一个给定的有穷自动机是否接受一个给定的串”是可判定的。我们对“可判定性”的定义是能找到一台图灵机H作为该问题的判定器，因此只要设计一个判定$A\mathrm{\_}DFA$的图灵机即可。就像我们使用通用编程语言编写一个图灵机的模拟那样，我们使用该图灵机模拟DFA并输入$w$，如果模拟以接受状态结束，则图灵机也接受；反之拒绝。

有了上述热身，我们来看下面这个语言：

$$A\mathrm{\_}TM=\{<M,w>|M\mathrm{是}\mathrm{一}\mathrm{台}\mathrm{图}\mathrm{灵}\mathrm{机}，\mathrm{且}\mathrm{接}\mathrm{受}w\}$$

$A\mathrm{\_}TM$是不可判定的。这类问题通常用反证自指得出矛盾的方法进行证明。不妨假设$A\mathrm{\_}TM$是可判定的，$H$是$A\mathrm{\_}TM$的判定器，即对于输入的一台图灵机$M$和一个串$w$：如果$M$接受$w$，$H$就停机并且接受$w$，如果$M$不接受$w$，则$H$也会停机，但拒绝$w$。现在来构造一个新的图灵机$D$，它以$H$作为子程序，$D$调用$H$以了解$M$将做什么，一旦得到这个信息，$D$就反着做，即$M$拒绝它就接受，$M$接受它就拒绝。

当$D$自己的源码作为输入来运行$D$时会得到什么？如果$D$接受，说明$M$拒绝，而$M$拒绝说明$M$不接受$w$，但此时输入的$M$就是$D$自己，于是得到了一个矛盾。这个例子和上面正则语言可判定性例子的差别在于图灵机要比DFA更强大，证明$A\mathrm{\_}TM$可判定的图灵机自身也要被囊括在证明之内。

INFO

这也说明了图灵可识别性的范围要比可判定性要广。书里还有一段关于对角线方法的讲解也很精彩。利用对角线方法可以证明语言是不可数的，而图灵机却是可数的。由于一台图灵机只能识别一个语言，故存在图灵机不可识别的语言。

停机问题

归约即将一个问题转化为另一个问题的过程。既然已经证明了$A\mathrm{\_}TM$是不可判定的，就可以将停机问题归约到这上面来。

$$HALT\mathrm{\_}TM=\{<M,w>|M\mathrm{是}\mathrm{一}\mathrm{台}\mathrm{图}\mathrm{灵}\mathrm{机}，\mathrm{且}\mathrm{对}\mathrm{输}\mathrm{入}w\mathrm{停}\mathrm{机}\}$$

假设$HALT\mathrm{\_}TM$是可判定的，即存在一台图灵机$R$可以判定$HALT\mathrm{\_}TM$，我们再构造图灵机$S$，在$S$上模拟$R$，如果$R$拒绝，则拒绝；如果$R$接受，那就模拟$R$所判定的那台图灵机$M$，因为$R$接受已经保证了$M$会停机，那么$S$对$M$的模拟不会进入无限循环，从而$S$是可判定的。和已知矛盾。

INFO

其实这些证明的重点都在于处理无限循环。判定器需要能终止，但机器不能检测自身是否进入了无限循环，然而我们可以用一台图灵机来模拟（编码运行）其他状态规模更小的机器，当输入串结束时，通过查看被模拟的机器是否进入接受状态来决定自己是接受还是拒绝。这样我们只需要保证被模拟的机器能读完输入串，不会在中途进入无限循环，也就是“空转”却不读取输入的情况发生。对于正则文法，由于与NFA等价，而任意的NFA都可以转化成DFA，因此一定可以读到输入串的末尾处。对于PDA或图灵机，由于它们确实允许只进行栈操作（读写头操作）而不读取输入，所以没法保证。这也是上面正则文法的例子没有强调无限循环，而停机问题的例子中却没有直接让$S$模拟$M$，而是先通过模拟$R$来保证$S$停机的原因。本文没有摘录对CFG可判定性的证明，该证明如果直接用$S$模拟PDA也会遇到类似的问题，解决方案是利用任意CFG都可以转化为乔姆斯基范式，而乔姆斯基范式具有一个特殊性质：该CFG的任意派生串$w$都只需要$2n-1$步，$n$是$w$的长度。因此我们只需要列出CFG的所有$2n-1$步的派生，检查$w$是否在这些派生中即可。

也许有人会质疑这里”机器不能检测自身是否无限循环“的前提，实际当机器进入无限循环时，如果要检测这个情况我们需要添加上一些代码，一些不会因无限循环而无法执行的模块，从而改变了这台机器的范畴，现在要检测的机器已经不仅仅是原来的机器了，于是为了检测新的机器是否进入无限循环又需要添加新的代码，又扩大了机器的内涵……来自哥德尔的凝视……

罗素悖论^[2]

用状态规模来表述上面“无限循环”的动态过程，机器正不断地试图往自己的纸带（存储单元）中添加一个能够表示当下自己的编码，而一旦添加了这个编码，机器的范畴就发生了改变需要扩充编码来容纳这个崭新的自己，这个过程是机器无限趋近自包含的过程。可以想见，最终纸带的长度将趋于无限。

集合论中存在一个危险的概括性公理，断言每一个性质都对应一个集合：对任意的对象$x$，若存在$x$的性质$P(x)$，那么存在一个集合$\{x|P(x)\mathrm{为}\mathrm{真}\}$。罗素悖论的思路在于找到这样一种性质，集合不包含自身：$x$是一个集合，且$x\notin x$。通过考察一个由所有不包含自身的集合构成的集合就可以得出矛盾（是否包含自身也是对象的一种属性，因此根据概括公理就能找到对应的一个集合）。

对于可判定性问题来说，“包含自身”对应的就是一台图灵机能模拟并判定自己。令性质$P(x)$表示“$x$是一台图灵机，且$x$不能够判定自己”，根据概括公理这些图灵机是存在的。于是我们就可以考察这样一台图灵机$\mathrm{\Omega }$：$\mathrm{\Omega }$能够判定所有不能判定自己的图灵机。下面的问题就是$P(\mathrm{\Omega })$是否为真，如果为真，说明$\mathrm{\Omega }$不能够判定自己，因此根据$\mathrm{\Omega }$的属性它应该能判定自己；如果为假，即$\mathrm{\Omega }$能够判定自己，但$\mathrm{\Omega }$自身的性质决定了它不能判定能判定自己的图灵机，从而矛盾。

这里概括公理的问题在于太过宽泛，从而允许了$\mathrm{\Omega }$的存在。解决概括公理荒谬之处的一种“非正式”方法是：考虑将对象按照一定的层次结构进行排列。前文机器范畴的说法就体现了这样的思想，其中的关键在于无论在哪一个层级，我们都无法构造出包含自身的集合。存在一个正则（基础）公理，可以确保罗素悖论不会出现：对于任意非空集合$A$，$A$中至少存在一个元素$x$满足：要么$x$不是集合，要么与$A$不相交。这个性质保证了$A$中至少有一个元素位于对象层级比较低的位置，以至于该元素不包含$A$中的其他任何元素。根据这个公理可以推出结论$A\notin A$（否则$A$就可以被构造出来。而且间接地循环自指也不被允许，例如我可能尝试构造$A=B,B=C,C=A$，$A,B,C$单拎出来都满足正则公理，但如果这三个集合能够同时存在，就可以构造出非空集合$T=A,B,C$不满足正则公理）。

INFO

分类公理：设$A$是一个集合，对$\mathrm{\forall }x\in A$，$P(x)$是$x$的一个性质，则集合$\{x|P(x)\mathrm{为}\mathrm{真}\}$存在。如果我们对比分类公理和概括公理，发现前者仅仅比后者多了一条$x$属于某集合$A$的前提条件，这间接说明概括公理等价于承认了一个大而全的集合$U$的存在，所有的对象（也包括$U$！！！）都属于这个集合。因此正则公理与概括公理是互斥的。

用图灵机判定问题类比，“$A$非空”对应于$A$可以模拟并判定一些图灵机，“$x$不是集合”意味着$x$可能是一些能力较小的机器，比如DFA和PDA，“$x$与$A$不相交”貌似有些微妙，直观的类比为$x$与$A$判定的图灵机没有交集。整理一下就是“对于任意图灵机$A$，$A$可以模拟并判定的机器中至少存在一台机器$x$满足：要么$x$是规模更小的机器即不是图灵机，要么$x$是图灵机，但它判定的图灵机与$A$判定的图灵机没有交集。”这个类比出来的“公理”保证了$A$所判定的机器层级总是小于自己（留意如果$A$判定$B$、$B$判定$C$而$C$判定$A$，则$A$也可以判定$A$）。说它微妙是因为它看起来好像承认了图灵机判定器的存在，与前文矛盾。其实并不矛盾，因为当我们尝试判定$A\mathrm{\_}TM$时，我们实际在打造一台“通用图灵机”$U$，当我们说$A\mathrm{\_}TM$不可判定时，实际在说有无限个状态（无限长纸带）的$U$不可判定。无论是前文的$H$、$D$还是$\mathrm{\Omega }$身上都有通用性的影子。因为通用性，在它所处的层级上出现了自指。如果对$U$的状态数量做出限制，对应当下有限的物理内存，对其进行分析也就成为可能，这类机器通常被称之为“线性有界自动机（LBA）”，这也是我们现在有诸多软件分析工具的原因。

---

1. 《计算理论导引（第三版）》[美] Michael Sipser ↩︎

2. 《陶哲轩实分析（第3版）》[澳] 陶哲轩 ↩︎