10.6 不可计算的问题

到目前为止，我们讨论的所有问题都是可解的。有些问题的解法非常有效，有些问题的

解法则比较复杂。Hanoi 塔之类的问题称为难解问题，因为当问题规模较大时，相应算法需要太多太多的时间（或空间）来完成计算，事实上是无效、不可行的解法。

现实中还存在比难解问题更麻烦的问题，那就是不可解问题。考虑这个场景：计算机正在执行一个程序，我们坐在边上等待程序结束。当过了很久程序还没结束时，我们该怎么办呢？我们可能推测程序中出现了无穷循环，永远不会结束，这样我们就必须强行中断程序运行甚至重启计算机。然而，我们并不能绝对肯定是出现了无穷循环，也许是因为计算太复杂导致时间过长呢？这样的话，我们就该继续等待。显然，这是一个两难困境。我们设想，要是有这么一个程序 P 就好了：P 的功能是以另一个程序 Q 的代码作为输入，并分析 Q 中是否包含无穷循环。然而很遗憾，这样的程序 P 是不存在的！这个问题其实对应于图灵机的停机问题，下面对此进行简要介绍。

图灵机

英国数学家 Alan Turing 于 1936 年发明了一种抽象机器用于研究计算的本质，人们称这种机器为图灵机（Turing machine）。图灵机能够模拟算法式计算，即按预定的规则一步一步执行基本指令的过程。现代计算机就是这样按照预定的程序一步一步执行指令的，因此可以视为图灵机的具体实现。

人们为了进行计算，需要用到纸和笔。类似地，图灵机在“硬件”上由一条纸带和一个读写头组成：纸带用于记录信息，读写头用于读写信息。纸带在读写头下移动，读写头即可在纸带上写下符号（如 0 和 1）或读出符号。这有点类似磁带录音机中磁带与磁头的关系，但与录音机的顺序录音或回放不同的是，图灵机的读写头和纸带受预定的规则（相当于我们熟悉的程序）的控制。参见图 10.13。

图 10.13 图灵机的纸带和读写头

下面对图灵机进行更详细的描述。一个图灵机涉及以下一些要素：

纸带：纸带被划分成一个个格子单元，单元中可以写入符号。纸带在向左、向右两个方向上都是无限延伸的，即图灵机的存储能力不受限制。
读写头：用于读写纸带单元中的符号。纸带在读写头下可以向左或向右移动，每次移动一个单元。当然也可以理解成纸带不动而读写头左右移动。
符号表：能够写入纸带的合法符号。具体用什么符号系统并不重要，正如现代计算机基于二进制一样，只要提供 0 和 1 两个符号就足够从事任何计算。
状态：图灵机在任一时刻都处于某种状态，例如当前读写头下方是 0 或 1 即对应不同状态。不同状态的数目是有限的。两个特殊状态分别是开始状态和停止状态。
指令：指令描述的是如何根据图灵机的当前状态以及当前读写头所读到的符号来控制图灵机执行特定动作并转换为新的状态。形如：

当前状态，输入符号 ® 新状态，输出符号，移动读写头预定的多条指令构成一个指令表（程序），它完全决定了图灵机的行为。图灵机的运行就是按照指令表所确定的状态转换规则一步一步进行状态转换的过程。

下面我们设计一个对给定正整数 n 加 1 的图灵机。

【图灵机 T+1】T+1 的符号表仅由 0（表示空白）和 1 组成。正整数 n 在纸带上用 n 个连续单元的 1 表示，例如 1、2、3 在纸带上分别表示为 1、11、111。读写头初始位置是在输入数据 n 的左方，停止位置是在输出数据 n+1 的最后一位 1 之上。初始状态为 s1，停止状态为 s3。指令表如下：

s1, 0 => s1, 0, R
s1, 1 => s2, 1, R
s2, 0 => s3, 1, Stop
s2, 1 => s2, 1, R

假设输入数据是 3，则图 10.14 展示了 3+1 的计算过程。读写头里记录的是图灵机当前状态。

图 10.14 计算 n+1 的图灵机 T+1（输入 n=3）

第 1 条指令的意义是：当图灵机 T+1 处于 s1 状态，并且读写头所读单元的内容是 0，那么就保持 s1 状态，也不改动该单元的内容，然后读写头右移。第 3 条指令的意义是：当 T+1 处于 s2 状态，并且读写头所读单元里的内容是 0，那么就进入 s3 状态，将该单元内容改为 1，然后停止。其他两条指令的意义请读者自行解读。从初始状态开始执行这些指令，经过 6 步状态转换，T+1 将终止，并且终止时纸带上的计算结果是 4 个连续的 1，表示正整数 4。

尽管图灵机是如此简单，但它的计算能力却非常强大。从上例可知，存在计算 n+1 的图灵机，由此不难想象可以设计出计算 n+m 的图灵机，进而可以设计出计算 n×m 的图灵机，等等。注意，这里我们谈论图灵机的计算能力，并非针对它的计算速度或存储空间，因为图灵机毕竟不是现实的计算机。研究图灵机是为了在理论上探索计算的能力和局限，例如回答计算机科学的一个根本问题：究竟什么是可计算的？对此，Turing 和 Church 分别通过研究图灵机和λ演算，得出了一个重要假设——Turing-Church 论题，其大致意思是：一个问题是能行可计算的（即算法可计算），当且仅当该问题能用图灵机来计算。因此，图灵机事实上给出了“算法计算”或“机械计算”的精确意义。

图灵机的强大计算能力有一个重要表现，那就是一个图灵机可以模拟另一个图灵机的工作。如果将图灵机 T 1 的功能进行编码，然后输入给另一图灵机 T 2，那么 T 2 就能表现得像 T 1 一样。打个比方，这就像一个人可以模拟另一个人的行为一样。假设张三既懂加法又懂乘法，并且他知道不懂乘法的李四总是错误地将 n×m 算成 n+m，那么当我们将 n 和 m 输入给张三要他计算 n×m 时，他完全可以故意输出 n+m 来冒充李四。

既然一个图灵机可以模拟另一个图灵机的行为，那我们就可以设计一个通用图灵机，它可以模拟任何图灵机的行为。对此读者应不陌生，因为我们在第 1 章就说过，现代计算机是通用计算机，给它安装不同的程序，就能完成不同的功能。图 10.15 展示了如何用通用图灵机 UT 来模拟某个特定图灵机 T：将 T 的行为（指令表）用 0/1 序列进行编码得到 Tcode，连同 T 的输入数据 data 一同输入给 UT，然后 UT 即可对 Tcode 进行解码，并针对 data 来模拟 T 的行为。

图 10.15 通用图灵机 UT 模拟特定图灵机 T

如果用函数来表示图灵机，则 UT 模拟 T 的行为可表示为

UT(Tcode,data) = T(data)

停机问题

对任何给定的图灵机 T，以及输入数据 data，T 可能停机，也可能不停机。上面计算 n+1 的图灵机 T+1 显然总是能停下来的，因为正整数 n 在纸带上表示为 n 个连续的 1，T+1 的第二条指令要求读写头只要读到 1 就不断向右移，因此最终会读完这有限个数的 1，并读到连续 1 右方的第一个 0，第三条指令会将这个 0 改写为 1，并停机。

一个图灵机也很容易不停机。例如这样一条指令就有可能令图灵机无法终止：

s1, 0 => s1, 0, NoMove

即，在 s1 状态读到 0 时，保持 s1 状态和单元内容 0 不变，并且读写头也不移动。如果一个图灵机进入到 s1 状态并且恰好读到 0，那么这个图灵机就将永远处于这个状态而不停机。不难看出，这条指令的行为与 Python 中的无穷循环语句

while True: 
    pass

是一样的。顺便说明一下，pass 是 Python 语言的一条语句，功能是什么都不做。

我们当然希望设计的图灵机能正确地完成计算并停机，可现实经常不能如我们所愿，就像我们编写的程序经常陷入无穷循环而不能终止一样。更让人烦恼的是，当图灵机（或程序）一直在执行而不终止时，我们并不知道它是否陷入无穷循环了！现实中，我们只能通过运行时间长短的经验来判断到底是什么情况，但这毕竟是不可靠的。有没有办法来检验图灵机是否停机呢？也就是说，能不能设计这样的通用图灵机 HT，它的输入是另一个图灵机 T（的编码）和 T 的输入 data，它的功能是判断 T 在 data 上执行后是否停机：如果是，则 HT 输出 1 并停机；如果不是，则 HT 输出 0 并停机。亦即，HT 是判断其他任意图灵机是否终止的图灵机。

上述 HT 是否存在？这就是所谓停机问题（Halting problem）。Turing 的一个重要成果就是证明了 HT 不存在！下面我们用程序设计的术语来非形式地描述这个证明。

从程序设计角度看，停机问题就是要编一个程序 halt，它读入另一个程序 prog 的源代码，并判断 prog 是否导致无穷循环。由于 prog 的行为不仅依赖于它的源代码，还依赖于它的输入数据，因此为了分析 prog 的终止性，还要将 prog 的输入数据 data 交给 halt。由此可得 halt 的规格说明：

程序：停机分析程序 halt；
输入：程序 prog 的源代码，以及 prog 的输入数据 data；
输出：如果 prog 在 data 上的执行能终止，则输出 True，否则输出 False。

读者也许会觉得向程序 halt 输入另一个程序 prog 作为处理对象有点不可思议，但其实这是非常普通的事情。例如，编译器（或解释器）就是这样的程序：将一个程序 P 的源代码输入给编译器程序 C，C 可以分析 P 中是否有语法错误，有则报错，没有则输出 P 的目标代码。

在停机问题中，正常情况下是想运行 prog(data)，但又不知道这个执行过程能不能终止，于是希望将 prog 的代码和 data 交给停机分析程序 halt，由 halt 来判断 prog(data)的终止性。由 halt 的程序规格可见，halt 总是能得出结论并终止的，从而避免了直接执行 prog(data)时无法确切知道它是否能终止的困扰。

设计 halt 程序的初衷可以理解，可惜这个程序是编不出来的。我们用反证法来证明这个结论，即先假设存在程序 halt，然后推导出矛盾来。

假如我们已经设计出了停机分析程序 halt，其参数是两个字符串：prog 是被分析的程序的源代码，data 是 prog 的输入数据。

def halt(prog,data):
    …… # 分析 prog 代码，如果对 prog 输入 data 时运行能终止
    return True
    …… # 如果 prog 运行在 data 上不能终止
    return False

利用 halt 的功能，我们可以编出如下这个奇妙的程序：

def strange(p): result = halt(p,p)
    if result == True: # 即 p(p)终止
        while True: 
            pass
    else: # 即 p(p)不终止
        return

运行 strange(strange),结果如何?

函数 strange()有一个字符串类型的形参 p，调用时需传递一个程序给它，不妨假设所传递的程序也是以一个字符串数据作为输入。strange 首先调用 halt(p,p)，这里的关键技巧是，传递给函数 halt 的形参 prog 和 data 的实参都是 p，亦即我们要分析程序 p 以它自己为输入数据时——即 p(p)——运行是否终止。strange 根据 halt(p,p)的分析结果来决定自己接下去怎么做：如果结果为 True，即 p(p)能终止，则 strange 进入一个无穷循环；如果结果为 False，即 p(p)不终止，则 strange 就结束。

strange 程序看上去有点费解，但只要 halt 存在，strange 在编程方面显然没有任何问题。接下来是证明过程的最美妙的部分：假如将 strange 自身的源代码输入给 strange 时会发生什么？更确切地，strange(strange)能否终止？

我们参照上面的 strange 代码来分析。假如调用 strange(strange)不终止，那必然是因为执行到了代码中条件语句的 if result == True 部分，即 halt(strange,strange)返回了 True，这又意味着 strange 以 strange 为输入时运行能终止！另一方面，假如调用 strange(strange)能终止，那必然是因为执行到了条件语句的 else 部分，即 halt(strange,strange)返回了 False，这又意味着 strange 以 strange 为输入时运行不能终止！总之，我们得到了如下结论：

若 strange(strange)不终止，则 strange(strange)终止；若 strange(strange)终止，则 strange(strange)不终止。

这样的结论在逻辑上显然是荒谬的。导致这个矛盾的原因在于我们假设了 halt 的存在，并利用了 halt 的功能。至此，我们证明了编写 halt 程序是不可能完成的任务，即停机问题是一个不可解问题。

停机问题不可解的证明过程具有非常深刻的意义，它告诉我们算法式计算具有本质上的局限性。计算机虽然在各行各业解决了很多问题，但是确实存在计算机不能解决的问题。