EverSeenFlash's Home

Appearance

Scroll to top↑

停机问题[1] ​

可判定性 ​

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

ADFA={<B,w>|B是DFA且接受输入串w}

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

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

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

ATM={<M,w>|M是一台图灵机，且接受w}

ATM是不可判定的。证明此结论的经典方法是反证法。

假设ATM是可判定的，那么存在一个判定器（图灵机）H，对于任意输入<M,w>：

  • 如果M接受w，H接受<M,w>。
  • 如果M不接受w，H拒绝<M,w>。

现在，我们构造一个新的图灵机D，它以H为子程序。D的输入是另一台图灵机M的编码<M>。D在内部调用H来判定当M以自身的编码<M>为输入时会发生什么。根据H的输出，D执行相反的操作：

  1. D接收输入<M>。
  2. D在内部运行H，输入为<M,<M>>。
  3. 如果H接受，说明M会接受<M>，则D拒绝。
  4. 如果H拒绝，说明M不会接受<M>，则D接受。

现在，考虑将D自身的编码<D>作为输入提供给D。根据D的定义，会发生以下情况：

  • 如果D接受<D>，那么根据步骤4，H必须拒绝<D,<D>>。而H拒绝意味着D不接受<D>。这产生了矛盾。
  • 如果D拒绝<D>，那么根据步骤3，H必须接受<D,<D>>。而H接受意味着D接受<D>。这也产生了矛盾。

无论哪种情况，我们都得出了一个逻辑上的矛盾。因此，最初的假设“ATM是可判定的”必然是错误的。这个例子和上面正则语言可判定性例子的差别在于图灵机要比DFA更强大，证明ATM可判定的图灵机自身也要被囊括在证明之内。

INFO

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

停机问题 ​

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

HALTTM={<M,w>|M是一台图灵机，且对输入w停机}

假设HALTTM是可判定的，即存在一台图灵机R可以判定HALTTM。我们可以利用R来构造一台ATM的判定器S。S的工作流程如下：

  1. S接收输入<M,w>。
  2. S在内部运行判定器R，输入为<M,w>。
  3. 如果R拒绝（即M在输入w上不会停机），那么M必然不接受w。此时，S拒绝<M,w>。
  4. 如果R接受（即M在输入w上会停机），S就继续在内部模拟M在输入w上的运行。因为已经知道M会停机，所以这个模拟过程必定会结束。
  5. 模拟结束后，如果M进入接受状态，S就接受<M,w>；如果M进入拒绝状态，S就拒绝<M,w>。

这样一来，图灵机S就能够判定任意的<M,w>是否属于ATM。这意味着S是ATM的判定器。然而我们已经证明了ATM是不可判定的，这与S的存在相矛盾。因此，最初的假设“HALTTM是可判定的”是错误的。

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)为真}。罗素悖论的思路在于找到这样一种性质，集合不包含自身：x是一个集合，且x∉x。通过考察一个由所有不包含自身的集合构成的集合就可以得出矛盾（是否包含自身也是对象的一种属性，因此根据概括公理就能找到对应的一个集合）。

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

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

INFO

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

用图灵机判定问题类比，“A非空”对应于A可以模拟并判定一些图灵机，“x不是集合”意味着x可能是一些能力较小的机器（如DFA），“x与A不相交”则可以直观地类比为x与A判定的图灵机没有交集。整理一下就是：“对于任意图灵机A，A可以模拟并判定的机器中至少存在一台机器x满足：要么x不是图灵机，要么x是图灵机，但它判定的图灵机与A判定的图灵机没有交集。”这个类比出来的“公理”保证了A所判定的机器层级总是低于自己（若A判定B、B判定C而C判定A，则A也可以判定A）。

这个类比看起来似乎承认了图灵机判定器的存在，与前文的结论矛盾，但其实不然。当我们讨论ATM的不可判定性时，我们实际上是在讨论一台能够判定所有图灵机的“通用图灵机”U。正是这种无限制的“通用性”导致了自指悖论的出现，无论是前文构造的H、D还是Ω，身上都有这种通用性的影子。ATM的不可判定性，本质上是说一台拥有无限状态（无限长纸带）的通用图灵机是无法构造出来的。

然而，如果我们对图灵机的能力加以限制，例如限制其纸带长度，就得到了“线性有界自动机（LBA）”。对于LBA，停机问题是可判定的。这对应了现实世界中我们拥有诸多代码静态分析、模型检测等软件分析工具的原因——它们分析的对象是状态有限的程序，而非理论上无限的通用图灵机。

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

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