第7章 信息论

是不同的“思维状态”。图灵机具有有限多个状态。在任何给定状态下，机器会根据当前符号的不同，执行一个或多个操作。例如，在状态a下，机器可能会在当前符号为1时右移一格，在当前符号为0时左移一格，在当前符号为空时则打印1。在状态b下，机器可能会擦除当前符号。

而在状态c下，机器可能会在当前符号为0或1时右移，否则就停机。执行完每组操作后，机器将具有一个新的状态，而它与先前状态可能相同也可能不同。给定一个计算，它所使用的各个状态都存放在一张表中，但至于如何物理地管理这张表则无关紧要。这张状态表其实就是机器的指令集。

这就是全部了。

图灵实际上是在对他的机器编程，尽管他没有使用这个术语。利用这些基本操作（移动、打印、擦除、变更状态，以及停机）就可以构建出更复杂的过程，并可以反复调用这些过程，如“复制符号序列、比较序列、擦除给定形式的所有符号等”。虽然机器一次只能看到一个符号，但实际上它可以利用部分纸带来暂时存储信息。用图灵的话来说，“另外一些［符号］则仅是临时笔记，以‘帮助记忆'”。而无穷无尽的纸带为此提供了无限的记录空间。就这样，图灵机可以完成所有算术运算。图灵演示了如何将两个数相加，也就是，写下了运算所需的状态表。他还演示了怎样让机器（无穷无尽地）打印出π的二进制表示。他花了很多时间探索这部机器能做什么以及实现某些具体任务的方法。最终他证明了，这部机器能做人类在计算数时所能做的一切工作，这其中不需要任何知识或直觉。任何可计算的，这部机器都可以计算。

接下来就是最后的准备工作。如果把图灵机简化到只剩下一张有限的状态表以及一个有限的输入集，那么图灵机本身就可以用数来表示。每一张可能的状态表，配以表示初始输入的纸带，表示了不同的机器。而每部这样的机器可以用一个特定的数来描述（这个数描述了其状态表和初始输入）。图灵给他的机器编码，就如同哥德尔给他的符号逻辑语言编码一样。如此这般，数据和指令之间的区分就被消除了：说到底，它们都不过是数而已。每个可计算数，必定对应着一个机器编号。

图灵最终（还是在脑子里）制造了一种机器，它可以模拟其他任何可能的图灵机——任何一部数字计算机。他把这部机器称为U ，取自“通用的”（universal）一词，这个说法也被数学家一直沿用至今。通用图灵机接受机器编号作为输入，也就是说，它可以从纸带上读取对其他机器的描述（这个数描述了其算法和输入）。无论一部数字计算机变得如何复杂，对它的描述都可以被编码后写入纸带，并由U读取。如果一个问题可以使用一部数字计算机来解决，也就是说，它能被编码成一组符号并通过一个算法来解决，那么这个问题也可以使用通用图灵机来解决。

现在显微镜把镜头对准了自身。通用图灵机开始检验每一个数，看它是否对应一个可计算的算法。有一些被证明是可计算的，还有一些被证明是不可计算的。但还存在第三种可能，这让图灵非常感兴趣。有那么一些算法会抗拒检查，自行其是，让机器一直计算下去，永不停机，也不明显地出现重复，只留下一旁的观察者始终纳闷它是否会停机。

现如今，图灵1936年对于停机问题的证明已经成为一个艰深难懂的杰作，其中充斥着递归定义、用以表示其他符号的符号、用以表示数（状态表、算法，乃至机器）的数。他的证明看上去是这样子的：

我们假设存在这样一个过程，也就是说，我们可以发明一台机器D，当提供了任一机器M的标准描述，它能够检测这个标准描述。如果M是循环机，则用符号u标记这个标准描述；如果M是非循环机，则用符号s标记这个标准描述。

结合机器D和U，我们可以构造机器H 来计算序列β''-。

机器D需要一条纸带。我们假设它使用了F-格所有符号之外的E-格，并在最后得出结论时，擦除机器D所做的所有中间工作……我们可以进一步证明，不存在这样的机器E，当给它提供了任意一台机器M的标准描述时，它可以判断M是否曾经打印过给定的符号（比如0）。

很少人能跟得上图灵的思路。 尽管这看上去像悖论（其实这就是悖论），但图灵的确证明了有些数是不可计算的。（事实上，绝大多数的数都是不可计算的。）

同时，由于每个数都对应着一个编码后的数学和逻辑学命题，因而图灵已经回答了希尔伯特的问题，即“命题是否都是可判定的”。

他证明了判定性问题有答案，且这个答案是否定的。一个不可计算的数，实际上就是一个不可判定的命题。

就这样，借助一台新奇、抽象、完全想象的机器，图灵得出了与哥德尔相似的证明和结论。不仅如此，他还更进一步，给出了一个形式体系的一般定义：任何用于生成公式的机械的流程，本质上都是 台图灵机。因此，任何形式体系中必然存在不可判定的命题。数学是不可判定的，其不完全性来源自不可计算性。

当数被拿来编码机器的行为时，悖论就会再次现身。这涉及不可避免的递归纠缠：被计算的实体与进行计算的实体纠缠到了一起，带来种种恶果。正如后来侯世达所说的，“整个事情依赖