第4章 计算

Quo facto，quando orientur controversiae, non magis disputatione opus erit inter duos philosophos, quam inter duos Computistas.Sufficiet enim calamos in manus sumere sedereque ad abacos, et sibi mutuo dicere：Calculemus！（如果产生了争议，哲学家们用不着像会计师一样相互争执，他们只需要掏出纸和笔，然后说：来，演算一下。）

——莱布尼茨（转译自罗素译文）

在普通人眼里，计算就是计算机做的事情，电子表格、文档处理、电子邮件，诸如此类。计算机在人们脑海里就是台式电脑或笔记本，里面有电子电路，一般都带有显示器和鼠标，以前还流行用真空管。对于我们自己的大脑，我们也模糊地觉得有点像计算机，有逻辑演算、记忆存储和输入输出。

不过如果你读复杂系统方面的学术文献，你会发现计算这个词的用法蛮奇怪：“细胞和组织中的计算”；“免疫系统的计算”；“市场的分布式计算的本质和局限”；“植物中的涌现计算”。这样的例子数不胜数。

自从计算机诞生以来，计算的概念已经走过了很长一段时间，现在许多科学家都将计算视为自然界中很普遍的现象。细胞、组织、植物、免疫系统和金融市场显然和计算机的运作方式不一样，那么他们说的计算到底是什么呢？他们又为什么要这样说呢？

在第12章我们会讨论这些问题，在此之前我们先了解一下计算思想的历史以及科学家用来理解自然界复杂系统的计算概念的基础。

什么是计算？什么可以计算

香农的信息定义关注的是消息源的可预测性。不过在现实世界中，信息是用来分析并产生意义的东西，信息被存储，并和其他信息结合，产生结果或行为。总之，信息是用来计算的。

历史上计算的意义变化很大。直到20世纪40年代末，计算都是指手工进行数学运算（小学生称之为“做算术”）。计算员（Computer）就是做数学运算的人。我以前的老师伯克斯（Art Burks）常和我们说他娶的是“计算机”——指的是第二次世界大战时被征召入伍手工计算弹道的妇女，伯克斯的夫人在遇到他时正是这样一位计算员。

现在计算指的是各式各样的计算机干的事情，另外自然界的复杂系统似乎也干这个。但是计算到底是什么呢？它又能做些什么呢？计算机什么都能算吗？是不是存在原则上的局限性？这些问题都是在20世纪中叶才得到解决。

希尔伯特问题和哥德尔定理

对计算的基础及其局限的研究，导致了电子计算机的发明，但其最初的根源却是为了解决一组抽象（而且深奥）的数学问题。这些问题是德国数学大师希尔伯特（David Hilbert，图4.1）于1900年在巴黎的国际数学家大会上提出来的。

希尔伯特在演讲中提出了世纪之交面临的23个亟待解决的数学问题。其中第2个和第10个问题在后来影响最大。实际上，它们不仅仅是数学内部的问题，它们还是关于数学本身以及数学能证明什么的问题。总的来说，这些问题可以分为三个部分：

1．数学是不是完备的？也就是说，是不是所有数学命题都可以用一组有限的公理证明或证否。

举个例子，还记得中学几何里学过的欧几里得公理吧？记不记得用这些公理可以证明“三角形内角和为180度”这样的定理？希尔伯特的问题是：是不是有某个公理集可以证明所有真命题？

2．数学是不是一致的？换句话说，是不是可以证明的都是真命题？“真命题”是专业术语，但我在这里用的是直接意义。假如我们证出了假命题，例如1+1=3，数学就是不一致的，这样就会有大麻烦。

3．是不是所有命题都是数学可判定的？也就是说，是不是对所有命题都有明确程序（definite procedure）可以在有限时间内告诉我们命题是真是假？这样你就可以提出一个数学命题，比如“所有比2大的偶数都可以表示为两个素数之和”，然后将它交给计算机，计算机就会用“明确程序”在有限时间内得出命题是“真”还是“假”的结论。

最后这个问题就是所谓的Entscheidungsproblem（“判定问题”），它可以追溯到17世纪的数学家莱布尼茨（Gottfried Leibniz）。莱布尼茨建造了他自己的计算机器，并且认为人类将建造出能判定所有数学命题真假的机器。

这三个问题过了30年都没有解决，不过希尔伯特很有信心，认为答案一定是“是”，并且还断言“不存在不可解的问题”。

然而他的乐观断言并没有维持太久，可以说非常短命。因为就在希尔伯特做出上述断言的同一次会议中，一位25岁的数学家宣布了对不完备性定理的证明，他的发现震惊了整个数学界，这位年轻人名叫哥德尔（Kurt G del，图4.2）。不完备性定理说的是，如果上面的问题2的答案是“是”（即数学是一致的），那么问题1（数学是不是完备的）的答案就必须是“否”。

哥德尔的不完备性定理是从算术着手。他证明，如果算术是一致的，那么在算术中就必然存在无法被证明的真命题——也就是说，算术是不完备的。而如果算术是不一致的，那么就会存在能被证明的假命题，这样整个数学都会崩塌。

哥德尔的证明很复杂。不过直观上却很容易解释。哥德尔给出了一个数学命题，翻译成白话就是“这个命题是不可证的”。

仔细思考一下。这个命题很奇怪，它居然谈论的是它自身——事实上，它说的是它不可证。我们姑且称它为“命题A”。现在假设命题A可证，那它就为假（因为它说它不可证），这就意味着证明了假命题——从而算术是不一致的。好了，那我们就假设命题A不可证，这就意味着命题A为真（因为它断言的就是自己不可证），但这样就存在不可证的真命题——算术是不完备的。因此，算术要么不一致，要么不完备。

难以想象这个命题如何转换成用数学语言表述，但是哥德尔做到了——哥德尔证明的复杂和精彩之处就在此，在这里我们不去讨论。

绝大多数数学家和哲学家都坚定地认为希尔伯特问题能被正面解决，这对他们是个沉重的打击。就像数学作家霍吉斯（Andrew Hodges）说的：“这是在研究中惊人的转折，因为希尔伯特曾以为他的计划将一统天下。对于那些认为数学完美而且无懈可击的人来说，这让人难以接受……”

图灵机和不可计算性

哥德尔干净利落地解决了希尔伯特第一和第二问题，接着第三问题又被英国数学家图灵（Alan Turing，图4.3）干掉了。

1935年，图灵23岁，在剑桥跟随逻辑学家纽曼（Max Newman）攻读研究生。纽曼向图灵介绍了哥德尔刚刚得出的不完备性定理。在理解哥德尔的结果之后，图灵发现了该如何解决希尔伯特的第三问题，&nbsp；判定问题，同样，他的答案也是“否”。

图灵是怎么证明的呢？前面说过，判定问题问的是，是否有“明确程序”可以判定任意命题是否可证？“明确程序”指的是什么呢？图灵的第一步就是定义这个概念。沿着莱布尼茨在两个世纪以前的思路，图灵通过构想一种强有力的运算机器来阐述他的定义，这个机器不仅能进行算术运算，也能操作符号，这样就能证明数学命题。通过思考人类如何计算，他构造了一种假想的机器，这种机器现在被称为图灵机。图灵机后来成了电子计算机的蓝图。

图灵机概述

如图4.4所示，图灵机由三部分组成：

1．带子，被分成许多方格（或“地址”），符号可以被写入其中或从中读出。带子两头都有无限长。

2．可以移动的读写头，能从带子上读取符号或将符号写到带子上。在任何时候，读写头都处于一组状态中的一个。

3．指示读写头下一步如何做的一组规则。

读写头开始处于特定的开始状态，并停在特定的格子上。每一步，读写头读取当前格子中的符号。然后读写头根据读取的符号和读写头的当前状态按照规则动作。规则决定读写头在当前格子中写入什么符号（替换当前符号）；读写头是向右还是向左移动或是停止不动；以及读写头的新状态是什么。如果读写头进入停机状态，机器就会停下来。

图灵机的输入是机器启动之前写在带子上的符号集合。输出则是停机之后留在带子上的符号集。

一个简单的例子

用一个简单的例子解释一下。为简便起见，假设带子上的符号只有0和1（同真正的计算机一样），而空符号则指格子中为空。我们设计一个图灵机，它读取的带子上有两个0，中间夹着一串1（例如，011110），然后判断1的个数是奇数还是偶数。如果是偶数，机器最后就在带子上输出一个0（其他格子为空）。如果是奇数，最后就在带子上输出一个1（其他格子为空）。假设带子的输入总是刚好有两个0，中间夹着零个或多个1，其他的格子都为空。

我们的图灵机的读写头得有4种可能状态：启动、偶数、奇数和停机。读写头最初停在最左边的0，处于启动状态。我们编写规则让读写头往右移动，每次一格，用空格替换遇到的0和1。如果读写头在当前格子中读到1，读写头就变成奇数状态，并往右移动一格。如果再次读到1，就变成偶数状态，再往右移动一格。就这样读到1就在偶数和奇数状态之间切换，一直往下。

如果读写头读到0，输入就走完了，这时所处的状态（奇数或偶数）就是想要的结果。然后机器根据状态在当前格子里写1或0，并变成停机状态。

下面是读写头实现这个算法的规则：

1．如果处于启动状态，当前格子为0，就变成偶数状态，把0擦掉，并往右移动一格。

2．如果处于偶数状态，当前格子为1，就变为奇数状态，把1擦掉，并往右移动一格。

3．如果处于奇数状态，当前格子为1，就变成偶数状态，把1擦掉，并往右移动一格。

4．如果处于奇数状态，当前格子为0，就在格子中写入1，并变成停机状态。

5．如果处于偶数状态，当前格子为0，就在格子中写入0，并变成停机状态。

首先在带子上写好输入，然后让图灵机根据规则顺序处理输入，这个过程被称为“根据输入运行图灵机”。

定义为图灵机的明确程序

在上面的例子中，如果输入的格式正确，不管具体的输入是什么（包括一个1也没有的情况，这时视为有偶数个1），根据输入运行图灵机都能确保得出正确的输出。虽然这有点小儿科，但你还是得承认这是一个解决奇偶问题的“明确程序”，每一步都很明确。图灵的第一个目标就是落实明确程序的概念。其中的思想是，对于特定的问题，你可以通过设计一个解决这个问题的图灵机来构造明确程序。这样“明确程序”就定义为图灵机，虽然目前还有些模糊不清。

在对此进行思考时，图灵并没有真的去建造一台机器（虽然后来他这样做了）。他对图灵机的所有思考都是通过纸和笔完成的。

通用图灵机

接下来，图灵又证明了图灵机的一个神奇特性：人们可以设计出一种通用图灵机（称之为U），它可以模拟任何图灵机的运作。U在模拟图灵机M处理输入I时，U处理的带子上不仅包含编码输入I的序列，还包含编码图灵机M的序列。你可能会奇怪图灵机M也能被编码，不过这其实不难。首先，所有规则（同前面那五条差不多）都可以简写成下面这种形式：

—当前状态—当前符号—新状态—新符号—动作—

这样前面的规则1就表示成：

—启动—0—偶数—空—右移—

（分隔符“—”不是必需的，只是方便我们读规则。）然后用0/1序列对规则进行编码：例如，启动=000，偶数=001，奇数=010，停机=100。类似的，符号也能编码成0/1序列：例如，符号“0”=000，符号“1”=001，空符号=100。0/1序列可以随意设定，只要与符号一一对应就行。状态和符号——比如启动和“0”——之间使用的0/1序列可以相同；因为我们知道规则的结构形式，据此就能分析出编码的内容。

类似的，也可对动作进行编码，“右移”对应000，“左移”对应111。将分隔符“—”编码成111。这样整条规则都可以编成0/1序列了。编码出来的规则1是这个样子：

111000111000111001111100111000111

其他规则也可以依此编为0/1码。将所有规则的编码连到一起，形成一个长串，就是图灵机M的编码。为了让U模拟M处理I, U最初的带子上既包含I也包含M的编码。U的每一步在带子的输入部分读取I的当前符号，并从带子的M部分读取相应的规则，应用于输入部分；这样就能模拟跟踪M在处理给定输入时的状态和输出。

如果M到达停机状态，U也会停机，并且带子上产生的输出会与M处理给定输入I时产生的输出一样。因此我们说“U在I上运行M”。这里没有讨论U本身的状态和规则，因为比较复杂，但是这种图灵机是肯定可以设计出来的。事实上，现在的可编程计算机正是这样一台通用图灵机：它读取存储的程序，并在存储的输入I上运行这个程序。在图灵证明了存在通用图灵机之后十来年，第一台可编程的计算机就被建造出来了。

图灵对判定问题的解决

再来看看判定问题：是否有明确程序可以判定任意命题是否为真？

通过证明通用图灵机的存在，图灵证明了这个问题的答案是“否”。他意识到图灵机的编码也可以作为另一台图灵机的输入。这就好像用一个计算机程序作为另一个程序的输入。比方说，你可以用WORD写一个程序，存成一个文件，然后用另一个程序（字数统计）处理这个文件，输出你的程序的字数。字数统计程序并不运行你的程序，它只是统计文本文件中的字数。

类似的，你也可以设计出统计输入中1的个数的图灵机M（这个不是很难），然后运行M处理另一个图灵机M′。M会统计M′中的1的个数。当然，在通用图灵机U中，将M的代码置于U的带子的“程序”部分，将M置于带子的“输入”部分，U就能在M上运行M。为了好玩，我们也可以在U的带子的“程序”和“输入”部分都放置M，让M处理它自己的编码！这就好像让字数统计程序来计数它自己的字数。完全没有问题！

带子上的0/1序列既可以作为程序，也可以作为另一个程序的输入。对熟悉计算机的你来说，这一点可能稀松平常，但是在图灵提出他的证明的年代，这点洞察却是革命性的。

现在我们来看看图灵的证明。

图灵是用反证法证明判定问题的答案为“否”。首先假设答案是“是”，然后证明这个假设会导致矛盾，从而证明答案是相反的。

图灵首先假设，存在明确程序可以判定任意给定命题是否为真。然后他给出了这样一个命题：

图灵命题：图灵机M对于给定输入I会在有限步后停机。

根据前面的假设，将M和I作为输入，有一个明确程序可以判定这个命题是否为真。图灵证明，这个假设会导致矛盾。

我们注意到有一些图灵机永远也不会停机。例如，考虑与前面例子类似的一个图灵机，只有两条规则：

1．如果处于启动状态，读取到0或1，变为偶数状态，并往右移动一格。

2．如果处于偶数状态，读取到0或1，变为启动状态，并往左移动一格。

这个图灵机完全没有错误，但是它永远不会停机。用现在的话说是“死循环”——写程序时经常会碰到的bug。死循环有时候隐藏很深，让你很难发现。

前面假设了有明确程序能够判定图灵命题是否成立，这就等价于说我们能设计一个图灵机来检查死循环。

具体说，这个假设说的是我们能设计一个图灵机H，对于任何给定的图灵机M和输入I，都能在有限时间内判断M对输入I是会停机还是会进入死循环，停不了机。

设计H的问题被称为“停机问题”。注意到H本身必须总是能停机，不管答案是“是”还是“否”。因此H不能通过在I上运行M来做到这一点，因为有可能M不会停机，从而H也停不了。H必须想其他办法做到这一点。

虽然还不清楚H要如何做，但是我们假设了H是存在的。我们将运行H处理M和I记为H（M, I）。如果M对于I会停机就输出“是”（例如在带子上写一个1），如果M对于I不会停机就输出“否”（例如在带子上写一个0）。

然后图灵把H变了一下，将图灵机M也作为输入，计算H（M, M），记为H′。H′执行的步骤同H一样，它确定M处理它自身的编码M时会不会停机。不过，在得到结果后，H′执行的动作同H不一样。H在回答“是”或“否”后停机。H′则只有答案是“M对于编码M不会停机”时才会停机。如果答案是“M对于编码M会停机”，H′就进入死循环，永不停机。

这可能有点让人糊涂，希望你们能跟上。在计算理论的课程中，这是一个分水岭，一些学生会变得绝望，“我没法想明白这玩意！”一些学生则会拍手称快，“我喜欢这玩意！”

当初我也有些糊涂，不过我还是喜欢上了这些。也许你和我一样。我们来深呼吸一下，然后继续。

现在图灵抛出了最后的问题：

如果用H′自身的编码作为H′的输入，H′会怎么做呢？

到这个时候，拍手称快的学生也会开始头大。这确实很难想明白，不过我们还是试一试。

先假设H′对于输入H′不会停机。但这样就有个问题。前面说了，H′以图灵机M的编码作为输入时，如果M对于M会停机，H′就会进入死循环，反之则停机。因此，如果H′对于输入M不能停机，就意味着M对于输入M会停机。发现会有什么结果了吧？H′对于输入H′不会停机意味着H′对于输入H′会停机。但是H′不能既停机又不停机，这样就导致了矛盾。

因此假设H′对于H′不会停机是错误的，只能认为H′对于H′会停机。但是这样又会有问题。只有在M对于M不会停机时，H′才会停机。因此如果H′对于H′不会停机，H′对于H′就会停机。又导致了矛盾。

这证明H′对于输入H′既不能停机也不能不停机。这是没法做到的，因此H′不可能存在。H′本身是H的特例，因此我们就证明了H不可能存在。

因此不存在明确程序能解决停机问题，这就是图灵的最后结论。停机问题证明了判定问题的答案是“否”；不存在明确程序能判定任意数学命题是否为真。图灵从而彻底埋葬了希尔伯特的这个问题。

从上面可以看出，图灵对停机问题不可计算性的证明，与哥德尔的不完备性定理具有同样的核心思想。哥德尔提出了可以编码数学命题的方法，从而让它们可以谈论自身。图灵则提出了编码图灵机的方法，让它们可以运行自身。

在这里我总结一下图灵里程碑式的成就。首先，他严格定义了“明确程序”的概念。其次，他提出的图灵机为电子计算机的发明奠定了基础。第三，他改变了大多数人的观念——计算存在局限。

哥德尔和图灵的命运

19世纪时，数学和科学被认为无所不能。希尔伯特和他的追随者认为他们即将实现莱布尼茨的梦想：发现自动判定命题的方法，并证明数学无所不能。类似的，在第2章我们看到，拉普拉斯相信，根据牛顿定律，科学家原则上能预测宇宙将发生的一切。

然而，20世纪早期在数学和物理上的发现表明，这个无所不能实际上并不存在。量子力学和混沌摧垮了精确预测的希望，哥德尔和图灵的结果则摧垮了数学和计算无所不能的希望。然而，图灵对停机问题的解决却为另一个伟大发现——可编程电子计算机——开辟了舞台。计算机后来给科学研究以及我们的生活带来了翻天覆地的变化。

在20世纪30年代发表他们的成果之后，图灵和哥德尔的命运迥异。同当时许多人一样，在希特勒和第三帝国出现后，他们的命运被彻底改变了。哥德尔受到时断时续的精神问题困扰，他在维也纳一直待到1940年，最后为了不被征入德军服兵役，移民到美国。（据他的传记作者王浩说，在准备美国入籍面试时，他发现了美国宪法中的不一致性，结果他的朋友爱因斯坦在陪他去面试时只好不断同他聊天，以引开他的注意力。）

哥德尔和爱因斯坦一样，加入了声名卓著的普林斯顿高等研究院，并继续在数理逻辑领域做出重要贡献。然而，在20世纪60—70年代，他的精神状况不断恶化。去世前，他得了严重的妄想症，认为有人要毒害他。他拒绝进食，最终死于饥饿。

图灵也访问了普林斯顿高等研究院并得到了职位，但他决定回到英国。在第二次世界大战中，他加入了英国绝密的破解德军谜团密码（Enigma）的计划。以他的逻辑和统计学专长，再加上在电子计算上的成就，图灵领导研发了破译机器，最终几乎破解了所有使用谜团密码的情报。这使得英国在同德国作战时具有很大优势，并成为最终战胜纳粹的重要因素。

战后，图灵在曼彻斯特大学参与研制了第一批可编程电子计算机（基于通用图灵机的思想）。此后他的兴趣又回到探索大脑和身体的“计算”原理，他研究了神经学和生理学，并在发育生物学理论上做了有影响的工作，还探讨了智能计算机的可能性。然而他的生活与当时的社会道德习惯相抵触：他没有隐瞒自己的同性恋倾向。在20世纪50年代的英国同性恋是非法的，图灵因为与男性发生关系而被逮捕，并被判决接受药物“治疗”以改变他的“状况”。他也被取消了接触政府机密的权力。这些事件最终导致他在1954年自杀。有意思的是，哥德尔是因为怕被下毒而把自己饿死，图灵则是吃了有氰化物的苹果把自己毒死。图灵死的时候年仅41岁。