第2章
算法和图灵机

算法概念的背景

算法、图灵机或者普适图灵机究竟是什么呢？为何这些概念在可以构成“思维仪器”的东西的现代观点中占有如此核心的地位呢？是否在原则上存在一个算法可达到的绝对极限呢？为了充分地讨论这些问题，我们必须比较细致地考察算法和图灵机的观念。

我在下面的各种讨论中，有时将要用到一些数学表达式。我注意到有些读者排斥这类东西，或者觉得它们吓人。如果你是这种读者，那么我请你原谅，并请你参照我在“敬启读者”中的建议。其实，这里论证所需的数学知识并不超过小学水平，但要仔细地弄通它们，则需要一些认真的思考。事实上，大部分描述是十分显明的，只要细心地跟随就能很好地理解。即使，如果人们只是为了稍微领略其风味而取其精华，也能有很大的收益。另一方面，如果你是一位专家，我还要请你原谅。我猜想，它仍然值得你花一段时间把我所写的看一遍，并且可能会有一两件东西引起你的兴趣。

“算法”这个词来自于9世纪波斯数学家阿布·雅发·穆罕默德·依伯恩·缪莎·阿勒——霍瓦里松，他在公元825年左右写了一本影响深远的《代数对话录》。“算法”这个词现在之所以被拼写成“algorithm”，而不是早先的更精确的“algorism”，似乎是由于和“算术”（arithmetic）相关联的缘故。[还值得指出的是，“代数”（algebra）这个词来源于该书书名的阿拉伯字“al jabr”。]

然而，在阿勒——霍瓦里松的书以前很久人们就知道了算法的实例。现在被称作欧几里得算法的找两个数最大公约数的步骤是在古希腊（公元前300年左右）即有记载的一个非常熟知的例子。让我们看看这是如何进行的。随意取两个具体的数，譬如讲1365和3654。所谓的最大公约数是可以同时整除这两个数的最大的整数。在应用欧几里得算法时，我们让这两数中的一个被另一个除并取余数，在3654中取出1365的两倍，其余数为924（=3654-2730）。我们现在用此余数即924以及我们刚用的除数即1365去取代原先的两个数。我们用这一对新的数重复上述步骤，用924去除1365，余数为441。这又得到新的一对441和924，我们用441除924，得到余数42（=924-882），等等，直到能够被整除为止。我们把这一切如下列出：

我们最后用于做除数的21即是所需要的最大公约数。

欧几里得算法本身是我们寻找这一因子的系统步骤。我们刚才把这一步骤应用于具体的一对数，但是这步骤本身可被十分广泛地应用于任意大小的数。对于非常大的数，要花很长时间来执行该步骤，数字越大则所花的时间越长。但在任何特定的情形下，该步骤最后会终结，并在有限的步骤内得到一个确定的答复。每一步骤所要进行的运算都是非常明了的。此外，尽管它可应用到大小没有限制的自然数上去，但是可以用有限的术语来描述整个过程。（“自然数”简单地就是通常的非负 [1] 整数0，1，2，3，4，5，6，7，8，9，10，11……）。的确很容易建立一个（有限的）描述欧几里得算法全部逻辑运算的“流程图”。

应该提到，我们在这里隐含地假定，已经“知道”如何实行从两个任意自然数A和B的除法中得到余数的必需的基本运算，所以这一步骤还未完全被分解成最基本的部分。那种运算又是算法的，是用我们在小学学到的除法的非常熟悉的步骤来进行的。在实际上，这个步骤比欧几里得的其他部分更复杂不少，但是可以再为它建立一个流程图。其复杂性主要起源于这个事实，即我们是（假定）对自然数用标准的“十进制”记数法。这样子我们需要列出全部的乘法表并考虑进位，等等。如果我们简单地用一连串n个某种记号来代表数n，例如×××××代表5，那么可从非常初等的算法运算看到余数的形成。为了得到当A被B除时的余数，可以简单地从代表A的记号中不断去掉代表B的符号串，直到最后余下的记号不够再进行这种运算为止。最后剩下的符号串提供了所需的答案。例如，为了得到17被5除的余数，我们可以简单地从×××××××××××××××××不断地取走5的序列×××××正如下面所示：

由于我们不能再继续这种运算，所以很清楚，其答案是2。

用这种连续减法找到除法余数的流程图可由下图给出。

为了使欧几里得算法的全部流程图完整，我们把上面形成余数的流程图代入到原先流程图的中右部的盒子中去。这种把一个算法向另一个代入是一种普遍的编电脑程序的步骤。上述寻求余数的算法是一个子程序的例子，也就是说，它是由主程序当做它的运算的一部分（通常是预先知道的）调用的算法。

当然，把数n简单地用n个×号来表示，在涉及大数时效率非常低，这就是我们通常用更紧凑的诸如标准的（十进位）系统的原因。然而，我们在这里并不特别关心运算或记号的效率。我们所关心的是运算在原则上是否可被算法实行的问题。如果我们用一种数的记号是算法的东西，则用另一种记号也是算法的。两种情况中只有在细节上和复杂性上有差别。

欧几里得算法只是在整个数学中可找到的大量的经典算法步骤之一。可能出人意料的是，尽管算法的这一特殊例子有悠久的历史渊源，但一般算法概念的准确表达直到20世纪才诞生。事实上，这一概念的各种不同描述都是在20世纪30年代给出的。称作图灵机的概念是最直接的、最有说服力的，也是历史上最重要的。相当仔细地考查这些“机器”将是很适当的。

关于图灵“机”有一件事必须记在心里，就是说它是一段“抽象数学”，而不是一个物理对象。这一概念是由英国数学家，非凡的破码专家兼电脑科学的开山鼻祖阿伦·图灵在1935—1936年提出的（Turing 1937）。其目的是为了解决称为判决问题的一个范围广阔的问题。它是由伟大的德国数学家大卫·希尔伯特部分地于1900年巴黎国际数学家大会上（“希尔伯特第十问题”），更完整地于1928年波伦亚国际会议上提出的。希尔伯特不多不少地要求解决数学问题的一般算法步骤，或者不如讲，是否在原则上存在这样步骤的问题。希尔伯特还有一个要把数学置于无懈可击的坚固基础上的宏伟规划，其中公理和步骤法则一旦定下就不能变。但是在图灵完成其伟大的工作之际，这个规划已经遭受到由奥地利才气焕发的逻辑学家库尔特·哥德尔在1931年证明的令人吃惊的定理的粉碎性打击。我们将在第4章谈论哥德尔定理及其意义。图灵关心的希尔伯特问题（判决问题）超越出任何依据公理系统的特殊的数学形式。问题在于，是否存在能在原则上一个接一个地解决所有（属于某种适当定义的族的）数学问题的某种一般的机械步骤？

回答这一问题的部分困难在于决定什么叫作“机械过程”。这概念处于当时正常的数学概念之外。为了掌握它，图灵设想如何才能把“机器”的概念表达出来，它的动作被分解成基本的步骤。这一些似乎是清楚的，图灵也把人脑当成在他意义上的“机器”的例子。这样，由人类数学家在解决数学问题时进行的任何活动，都可以被冠以“机械步骤”之名。

虽然这一有关人类思维的观点似乎对于图灵发展他的极重要概念很有价值，我们却绝没有必要去附和它。的确，图灵在把机械过程的含义弄精确时，向我们展示出存在一些完好定义的数学运算，在任何通常的意义上，都不能被称为机械的！图灵本人的这一方面工作现在可间接地为我们提供了他自己有关精神现象性质观点的漏洞。这个事实也许不无讽刺意味。然而，这不是我们此刻所关心的。我们首先要弄清图灵心目中的机械过程究竟是什么。

图灵概念

我们设想实现某种（可以有限地定义的）计算步骤的一台仪器。这样仪器会采取什么样的一般形式呢？我们必须准备得理想化一些，而且不必为实用性过分担心：我们是真正地考虑一台数学上理想化的“机器”。我们要求该仪器具有有限（虽然也许非常大的）数目的不同可能态的分立集合。我们把这些称作仪器的内态。但是我们不限制该仪器在原则上要实现的计算的尺度。回顾一下上述的欧几里得算法。在原则上不存在被该算法作用的数的大小的限制。不管这些数有多大，算法或者一般计算步骤都是同样的。对于非常大的数，该步骤的确要用非常长的时间，而且需要在数量可观的“粗纸”上面进行实际的计算。但是不管这些数有多大，该算法是指令的同一有限集合。

这样，虽然我们仪器只有有限个内态，它却能够处理大小不受限制的输入。此外，为了计算应允许该仪器调用无限的外存空间（我们的“粗纸”）；而且能够产生大小不受限制的输出。由于该仪器只有有限数目的不同的内态，不能指望它把所有外部数据和所有自己计算的结果“内化”。相反地，它必须只考察那些立即处理的数据部分或者早先的计算，然后对它们进行任何需要的运算。也许可在外存空间把那个运算的相关结果记下来，然后以一种精确决定的方式进行下一个阶段的运算。正是输入、计算空间和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际上可真正建造的某种东西（图2.1）。但这是极其关键的理想化。对于大多数实用目的而言，当代电脑技术的奇迹为我们提供了无限的电子存储仪器。

事实上，在上述讨论中称为“外部的”存储空间的类型，可实际上被认为是现代电脑的内部工作的一部分。存储空间的某一确定部分是否被当作内部的或外部的，也许只是术语的问题。硬件和软件是划分“仪器”和“外部”的一种方法，内部可当成硬件，而外部为软件。我将不必拘泥于此，但是不管从哪个角度看，当代电子电脑是图灵的理想化的极好近似。

图灵是按照在上面做记号的“磁带”来描述其外部数据和存储空间的。一旦需要，仪器就会把该磁带调来“阅读”，而且作为其运算的一部分，磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号，允许同一磁带像外存（也就是“粗纸”）以及输入那样动作。因为在许多运算中，一个计算的中间结果起的作用正如同新的数据，所以事实上在“外存”和“输入”之间不做任何清楚的区分也许是有益的。我们记得在欧几里得算法中，不断地用计算不同阶段的结果去取代原先的输入（数A和B）。类似地，这同一磁带可被用作最后输出（也就是“答案”）。只必须进行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算最后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。

让我们有限的仪器前后移动一条潜在的无穷长的磁带，我自己觉得有点不舒服。不管其材料是多么轻，移动无限长的磁带是非常困难的！相反地，我宁愿把磁带设想成代表某一外部环境，我们有限的仪器可以通过这环境进行移动。（当然用现代电子学，既不需要“磁带”也不需要“仪器”做实际的、通常物理意义上的“运动”，但是这种“运动”是一种描述事体的便利方法。）依此观点，该仪器完全是从这个环境接受它的输入。它把环境当成它的“粗纸”。最后将其输出在这同一个环境中写出。

在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个单独的记号 。我们可利用有记号或者没有记号的方格来阐释，我们的环境（也就是磁带）可允许被细分并按照分立（和连续相反的）元素来描述。希望仪器以一种可靠并绝对确定的方式工作，这似乎是合情理的要做的事。然而，我们允许该“环境”是（潜在地）无限的，把这作为我们使用的数学理想化的特征。但是，在任何特殊的情形下，输入、计算和输出必须总是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该有有限数目的实在的记号。磁带在每一个方向的一定点以外必须是空白的。

我们用符号“0”来表示空白方格，用符号“1”来代表记号方格，例如：

我们要求该仪器“读”此磁带，并假定它在一个时刻读一个方格，在每一步运算后向右或向左移动一个方格。这里没有损失任何涉及的一般性。可以容易地由另一台一次只读和移动一个方格的仪器去仿照一台一次可读n个方格或者一次可移动k个方格的仪器。k方格的移动可由一个方格的k次移动来积累，而存储一个方格上的n种记号的行为正和一次读n个方格一样。

这样的一台仪器在细节上可做什么呢？什么是我们描述成“机械的”东西作用的最一般的方式呢？我们记得该仪器的内态在数目上是有限的。除了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号0或1来取代它刚读过的0或1；它向右或向左移动一个方格；最后它决定是继续还是终止计算并停机。

为了以明白的方式定义该仪器的运算。我们首先，譬如讲用标号0，1，2，3，4，5，……来为不同的内态编号；那么，用一张显明的代换表可以完全指定该仪器或图灵机的运行，譬如：

箭头左边的大写的数字是仪器在阅读过程中磁带上的符号，仪器用右边中间的大写的数字来取代之。R告诉我们仪器要向右移动一个方格，而L告诉我们它要向左移动一个方格。（如果，正如图灵原先描述的那样，我们认为磁带而不是仪器在移动，那么我们必须将R解释成把磁带向左移动一个方格，而L为向右移动一个方格。）词STOP表示计算已经完成而且机器就要停止。特别是，第二条指令01→131 L 告诉我们，如果仪器内态为0而在磁带上读到1，则它应改变到内态13，不改变磁带上的1，并沿着磁带向左移一格。最后一条指令2591→0 R.STOP告诉我们，如果仪器处于态259而且在磁带上读到，那么它应被改变为态0，在磁带上抹去1而产生0，沿着磁带向右移一格，然后终止计算。

如果我们只用由0到1构成的符号，而不用数字0，1，2，3，4，5……来为内态编号的话，则就和上述磁带上记号的表示更一致。如果我们有选择的话，可简单地用一串n个1来标号态n，但这是低效率的。相反地，我们使用现在人们很熟悉的二进制数系：

正如标准的（十进位）记数法一样，这里最右边的数字代表“个位”，但是紧靠在它前面的位数代表“二”而不是“十”。再前面的位数代表“四”而不是“百”，更前面的是“八”而不是“千”等。随着我们向左移动，每一接续的位数的值为接续的二的幂：1，2，4（=2×2），8（=2×2×2），16（=2×2×2×2），32（=2×2×2×2×2）等。（为了将来的其他目的，我们有时发现用二和十以外的基来表示自然数是有用的：例如基数为三，则十进位数64就可被写成2101，现在每一位数都为三的幂：64=（2×3 3 ）+3 2 +1；参阅第4章139页的脚注。）

对上面图灵机的内态使用这种二进制记数法，则原先的指令表便写成：

我还在上面把R.STOP简写成STOP，这是由于可以假定L.STOP从来不会发生，以使得计算的最后一步结果，作为答案的部分，总是显示在仪器的左边。

现在假定我们的仪器处于由二进制序列1010010代表的特殊内态中，它处于计算的过程中，第44页给出了它的磁带，而且我们利用指令110100100→111L：

在磁带上被读的特殊位数（这里是位数“0”）由一个更大写的数字指示，符号串的左边表示内态。在由上面（多多少少是我随机造出的）部分的指定的图灵机例子中，读到的“0”会被“1”所取代，而内态变成“11”，然后仪器向左移动一格：

该仪器现在即将读另一个数字，它又是“0”。根据该表，它现在不改变这个“0”，但是其内态由“100101”所取代，而且沿着磁带向右移回一格。现在它读到“1”，而在表的下面某处又有如何进一步取代内态的指令，告诉它是否改变所读到的数，并向那个方向沿着磁带移动。它就用这种方式不断继续下去，直到达到STOP为止，在该处（在它向右再移一格之后）我们可以想象听到一声铃响，警告机器操作员计算完毕。

我们将假定机器总是从内态“0”开始，而且在阅读机左边的磁带原先是空白的。所有指令和数据都是在右边输进去。正如早先提到的，被提供的这些信息总是采用0和1的有限串的形式，后面跟的是空白带（也就是0）。当机器达到STOP时，计算的结果就出现在阅读机左边的磁带上。

由于我们希望能把数字数据当作输入的一部分，这样就需要有一种描述作为输入部分的通常的数（我这里是说自然数0，1，2，3，4，……）的方法。一种方法可以是简单地利用一串n个1代表数n（尽管这会给我们带来和自然数0相关的困难）：

这一初等的数系（相当非逻辑地）被称作一进制数系。那么符号“0”可用作不同的数之间的分隔手段。这种把数分隔开的手段是重要的，这是由于许多算法要作用到数的集合，而不仅仅是一个数上面。例如，对于欧几里得算法，我们的仪器要作用到一对数A和B上面。图灵机可以很容易地写下执行该算法的程序。作为一个练习，某些勤奋的读者也许介意去验证下面的一台图灵机（我将称它为EUC）的显明的描述，当应用到一对由0分隔的一进制数时，的确会执行欧几里得算法：

然而，任何读者在进行此事之前，从某种简单得多的东西，譬如图灵机UN+1开始将更为明智：

它简单地把1加到一个一进制数上。为了检查UN+1刚好做到这点，让我们想象，譬如讲把它应用到代表数4的磁带上去：

我们使仪器在开始时从某处向左为一些1。它处于内态0并且读到0。根据第一条指令，它仍保留为，向右移动一格，而且停在内态0上，在它遇到第一个1之前，它不断地这么进行并向右移动。然后第二条指令开始作用：它把1留下来不变并且再向右移动，但是现在处于内态1上。按照第四条指令，它停在内态1上，不改变这些1，一直向右移动，一直达到跟在这些1后面的第一个0为止。第三条指令接着告诉它把那个0改变成1，向右再移一步（记住STOP是表示R, STOP），然后停机。这样，另一个1已经加到这一串1上。正如所要求的，我们例子中的4已经变成了5。

作为更费神的练习，人们可以验证，下面所定义的机器UN×2，正如它所希望的，把一个一进制数加倍：

在EUC的情形中，为了得到有关的概念，人们可用一些明显的数对譬如6和8来试验。正如以前一样，阅读机处于态0，并且初始时处在左边，而现在磁带从一开始的记号是这样的：

……0000000000011111101111111100000……

在许多步之后，图灵机停止，我们得到了具有如下记号的磁带：

……0000110000000000000……

而阅读机处于这些非零位数的右边。这样，所需的最大公约数正是所需要的（正确的）2。

要完全解释为何EUC（或者UN×2）在实际上完成所预想的，牵涉许多微妙之处，而且解释本身比机器更复杂，这是电脑程序的通常特征！（为了完全理解一个算法步骤为何能做到所预想的，牵涉到洞察。“洞察”本身是算法的吗？这是一个对我们以后颇为重要的问题。）我不想在这里为EUC或UN×2提供解释。真正做过检验的读者会发现，为了在所需的方案中把事情表达得更精密一些，我自作主张地对欧几里得算法作了一些不重要的变通。EUC的描述仍然有些复杂，对于11种不同的内态包含有22条基本指令，大部分复杂性是纯粹组织形式的。例如，可以看到在22条指令中，只有3条真正涉及在磁带上改变记号！（甚至对于UN×2用了12条指令，其中只有一半涉及改变记号。）

数据的二进制码

用一进制表示大数极端无效率。正如早先描述的，我们将相应地用二进制数系。然而，不能直接地把磁带当作二进制数来读。如果这样做的话，就没有办法告知一个数的二进制表示何时结束，以及无限个的序列是否代表右端开始的空白。我们需要某种终结一个数的二进制描述的记号。此外，我们还经常要输进几个数。正如欧几里得算法需要一对数 [2] 那样。问题在于，我们不能把数之间的间隔和作为单独的一个数的二进制表示中的一部分的0或一串0区分开来。此外，我们或许在输入磁带中包括所有种类复杂的指令和数。为了克服这些困难，让我们采用一种我称之为收缩的步骤。按照该步骤，任何一串0或一串1（共有有限个）不是简单地被当作二进制数来读，而是用一串0，1，2，3等来取代。其做法是，第二个序列的每一数字就是在第一个序列中的连续的0之间的的1个数。例如序列

01000101101010110100011101010111100110

就可被取代成下面的形式：

我们现在可以把数2，3，4，……当作某种记号或指令来读。让我们把2简单地当作表示两个数之间间隔的“逗号”，而根据我们的愿望，3，4，5，……可以代表我们关心的各种指令或记号，诸如“负号”、“加”、“乘”“到具有下面号码的位置”，“将前述运算迭代如下多次”，等等。我们现在有了由高阶数分开的各种和的串。后者代表写成二进制的通常的数。这样上面可读成（“逗号”为2）：

（二进制数1001）逗号（二进制数11）逗号……

使用标准的阿拉伯数字“9”，“3”，“4”，“0”来写相应的二进制数1001，11，100，0，我们就得到整个序列：

9，3，4（指令3）3（指令4）0，

特别是，这一步骤给了我们一种简单地利用在结尾处逗号终结描述一个数的手段（并因此把它和在右边的无限长的空白带区分开来）。此外，它还使我们能对以二进制记号写成和的单独序列的自然数的任何有限序列编码。让我们看看在一特定情形下这是怎么进行的。例如，考虑序列

5，13，0，1，1，4，

在二进制记数法中这是

101，1101，0，1，1，100，

它可用扩展（也就是和上面收缩相反）的步骤在磁带上编码成

＜p＞

为了直截了当地得到这个码，我们可对原先的二进制数列作如下代换：

然后在两端加上无限个0。如果我们把它列出，就能更清楚地看出，如何把这个应用到上面的磁带上：

000010010110101001011001101011010110100011000

我将把这种数（的集合）的记号称为扩展二进制记号（这样，例如13的扩展二进制形式为1010010）。

关于这种编码还有最后一点必须提及。这只不过是个技巧，但是为了完备起见是需要的 [3] 。在自然数的二进制（或十进制）表示中，处于表式最左端的0是不“算”的，它通常可被略去，这里有些多余。例如00110010和110010是两个相同的二进制数（而0050和50为相同的十进制数）。这一多余可适合于数0本身，它也可写成000或00。一个空白的空间的确也应该逻辑地表示0！在通常的记号下这会导致巨大的混淆，但是它和上面刚描述的记号可相安无事。这样，在两个逗号之间的0可只写成两个连在一起的逗号（，），它在磁带上被编码成两对由单独的0隔开的11：

……001101100……

这样，上面的6个数的集合也可用二进制记号写成：

101，1101，1，1，100，

而且在磁带上可以扩展的二进制方式编码成：

……00001001011010100101101101011010110100011000……（有一个0已从我们以前的序列中略去）。

现在我们可以考虑让一台图灵机，譬如讲欧几里得算法，把它应用到以扩展二进制记数法写出的一对数上。例如，这一对数是我们早先考虑的6，8，不用以前用的：

……0000000000011111101111111100000……

而考虑6和8的二进制表示，也就是分别为110和1000。这一对为6，8，用二进制记数法也就是110，1000扩展后在磁带上编码成：

……00000101001101000011000000……

对于这一对特殊的数，并没有比一进制形式更紧凑。然而，譬如说我们取（十进制数）1583169和8610。在二进制记数法中它们是：

110000010100001000001，10000110100010，

这样，我们在磁带上把这一对编码成：

……001010000001001000001000000101101000001010 010000100110……

只要用一行就可将其全部写出，而如果用一进制记数法的话，表示“1583169，8610”的磁带用这一整本书都写不下。

当数用扩展二进制记数法表示时，一台执行欧几里得算法的图灵机，如果需要的话，可以简单地把适当的一对在一进制和扩展二进制之间互相翻译的子程序算法接到EUC上去而得到。然而，由于一进制编数系统的低效率仍在“内部”存在，并且在仪器的迟缓以及需要大量的外部“粗纸”（它是磁带的右手部分）方面表现出来，实际上这是极其低效率的。可以给出全部用扩展二进制运算的、更有效率的、欧几里得算法的图灵机，但是它在这里对我们并无特别启发之处。

相反地，为了阐明如何使一台图灵机能对扩展二进制数运算，让我们尝试某种比欧几里得算法简单得多的东西，即是对一个自然数加1的过程。这可由（我称之为XN+1的）图灵机来执行：

某些勤奋的读者可把它应用到，譬如讲数167上去，以再次验证这一台图灵机在实际上做到了所预想的。这一个数的二进制表示可由下面的磁带给出：

……0000100100010101011000……

为了把1加到这个二进制数上，我们简单地找到最后的那个0，并把它改成1，然而用0来取代所有跟在后面的1。例如167+1=168在二进制记数法下写成：

10100111+1=10101000

这样，我们的“加1”图灵机应把前面的磁带用

……0000100100100001100000……

来取代，它的确做到了这一点。

我们注意到，甚至这种简单加1的非常基本的运算在用这种记数法时都会显得有些复杂，它使用了15条指令和8种不同的内态！由于在一进位系统中“加1”只是把1的串再延长1个而已，事情当然是简单得多。所以我们的机器UN+1更为基本，这一点也不奇怪。然而，对于非常大的数，由于所需的磁带非同寻常地长，UN+1就会极慢。而用更紧凑的扩展二进制记号运算的更复杂的机器XN+1就会更好。

作为旁白，我愿意指出对于扩展二进制比一进制图灵机显得更简单的一个运算，这就是乘二。在这里由

给出的图灵机XN×2能在扩展的二进制上实现这个运算，而前面描述的相应于一进制的机器UN×2就要复杂得多！

我们从这里得到了，关于图灵机在非常基础水平上可做到的一些事情的概念。正如所预料的，当进行某些复杂的运算时，它们会变得极为复杂。这种仪器的终极能力是什么呢？让我们在下面讨论这一个问题。

丘奇—图灵论题

人们一旦对建造简单的图灵机稍有一些熟悉，下面这些事实就很容易使他们感到满意。特殊的图灵机的确能执行各种基本的算术运算，诸如把两个数加到一起，或把它们相乘，或求一个数到另一个数的方次。显明地给出这种机器不是太啰唆的事，但是我不想在这里着手这么做。也可以提供其结果为一对自然数的运算，譬如带有余数的除法，或者其结果为任意大数目的数的有限集合。此外，可以这样地建造图灵机，即预先没有必要指定它要做何种运算，其运算的指令由磁带提供。需要实行的特定运算也许在某一阶段依赖于该机器在某个更早阶段的需要进行的某个计算的结果。（“如果那个计算的结果比某数大，则做这个；否则就做那个。”）一旦人们理解到，他可制造实现算术或简单的逻辑运算的图灵机，则很容易想象如何使之执行具有算法性质的更复杂的任务。在他们捣弄了好一阵之后，很容易坚信，这类机器的确能执行不管什么样的机械运算！在数学上，可以很合情合理地把机械运算定义为可被这样的一台机器所执行的运算。数学家用名词“算法”以及形容词“可计算的”、“递归的”和“有效的”来表示能由这类理论机器——图灵机实行的机械运算。一个步骤只要是足够清楚并且机械的，则可合理地相信能找到一台执行它的图灵机。这正是我们（也就是图灵）引进图灵机概念本身的初步讨论的全部要点。

另一方面，人们仍会感到，这些机器的设计不必这么局限。初看起来，只允许仪器在一个时刻读一个二进制数字（0或1），并且一次沿着一个单独的一维磁带只移动一格似乎是限制。为什么不允许大数目或相互联结的阅读机一下子跑过4条或5条甚至1000条分开的磁带呢？为什么不允许0和1的方格的整个平面（或者甚至一个三维的阵列），而坚持只用一维的磁带呢？为什么不允许从某种更复杂的计数系统或字母来的其他符号呢？事实上，虽然这些改变中的一些会对运算的经济性造成一定程度的不同（正如允许用多于一条的磁带一定会是这种情形那样），但是所有这一切都不会对我们在原则上要得到的东西造成丝毫的影响。即使我们在所有这些方面一下子推广该定义，这种归于“算法”的名下（或“计算”、“有效步骤”或“递归运算”）所实现的运算种类刚好和推广以前的完全相同！

我们可以看到，没有必要有多余一条的磁带，只要该仪器需要时总能在给定的磁带不断地找到新的空白。为此，也许必须不断地把数据从磁带的一处往另一处调度。这也许是“低效率的”，但是它不限制在原则上可以得到的极限 [4] 。类似地，利用多于一台并行动作的图灵机——这在近年来由于尝试更精密地模仿人脑而变得很时髦——不能在原则上得到任何新东西（虽然在某种情形下可改善动作的速度）。拥有两台分开的、不直接相互联络的仪器并不比两台相互联络的得到更多，而且如果它们联络，则实际上只不过是一台单独的仪器！

关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带代表“环境”，也许宁愿把它当作一个平面或许一个三维空间，而不当做一维磁带。一个平面似乎比一维磁带更接近于一个“流程图”（正如在上面对欧几里得算法运算的描述）所需要的 。然而，在原则上以“一维的”形式（也就是利用流程图的通常术语来描述）写出流程图的运行并没有困难。在二维平面上显示只是为了我们的便利和容易理解，它对原则上能得到的并没造成什么影响。人们总能把一个二维平面上甚至三维空间上的一个记号或对象的地址，直截了当地在一维磁带上编码。（事实上，使用一个二维平面完全等效于用两条磁带。这两条磁带提供为在二维平面上指明一点所需的两个“坐标”；正如3条磁带可作为一个三维空间的一点的“坐标”一样。）这一维的编码又可能是“低效率的”，但是它在原则上不限制我们的目标。

尽管所有这一切，我们仍然可心存质疑，图灵机的概念是否真的和我们希望叫作“机械的”每一逻辑或数学运算相统一。在图灵写他的开创性文章的时候，这一点比今天模糊得多，所以他觉得有必要把情形解释得更清楚一些。图灵的严密论证从以下事实得到了额外的支持，这就是美国逻辑学家阿伦佐·丘奇（在S.C.克林的协助下）完全独立地（并实际上稍早一些）提出了一种方案，也是旨在解决希尔伯特的判定问题的λ演算。尽管它不如图灵的那么明显地为一种完全广泛的机械的方案，但在数学结构上的极端经济性方面有些优点。（我将在本章的结尾描述丘奇的杰出的计算。）还存在其他一些解决希尔伯特问题的和图灵相独立的设想（见 Gandy 1988 ），尤其是波兰——美国逻辑学家爱弥尔·波斯特的设想（比图灵稍晚些，但其思想与图灵比和丘奇更相像许多）。所有这些方案很快就被证明是完全等效的。这就给现在称作丘奇—图灵论题的观点增加了许多分量，即图灵机（或等效的）概念实际在数学上定义了我们认为是算法（或有效或递归或机械的）步骤的东西。现在，高速电脑已变成我们生活中如此熟悉的部分，很少人似乎觉得有必要去问这些论题的原始形式。相反地，已有不少人转去注意真正的物理系统（假定包括人脑）——精确服从物理定律的东西——是否能够执行比图灵机更多、更少或刚好一样多的逻辑和数学运算。我本人是非常喜欢丘奇—图灵论题的原先的数学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本书主要关注的另外一个单独的问题。

不同于自然数的数

我们在上述的讨论中考虑了自然数的运算，并且注意到了这一显著的事实，即尽管每台图灵机只有固定的有限数目的不同内态，它却可能处理任意大小的自然数。然而，人们经常需要使用比这更复杂的其他种类的数，例如负数、分数或无理数。图灵机可以容易地处理负数和分数（例如像-597/26的数），而且我们可取任意大的分母和分子。我们所要做的全部是对“-”和“/”作适当的编码。这可容易地利用早先描述的扩展二进制记数法做到（例如，“3”表示“-”以及“4”表示“/”，它们分别在扩展二进制记数法中编码成1110和11110）。人们就是这样地按照自然数的有限集合来处理负数和分数的。这样，就可计算性的一般问题而言，它们没有告诉我们什么新的东西。

类似地，由于长度不受限制的有尽小数表式仅仅是分数的特殊情形，它们并没给我们带来什么新问题。例如，无理数π的由3.14159265给出的有尽小数近似，简单地就是分数314159265/100000000。然而，无尽小数表式，譬如完全无尽展开

π=3.14159265358979……

出现了一定的困难。严格地讲，无论是图灵机的输入或者输出都不是无尽小数。人们也许会想到，我们可以找到一台图灵机，在其输出磁带上产生由π的小数展开的、所有的一个接一个位数3，1，4，1，5，9，……，我们就简单地让机器一直开下去好了。但这对于一台图灵机来讲，是不允许的。我们必须等待机器停了以后（铃声响过！）才允许去检查输出。只要机器还没有到达停止命令，其输出就可能要遭受到改变，所以不能对它信任。另一方面，在它到达停止时，其输出必须是有限的。

然而，存在一种合法地使图灵机以与此非常类似的方法，一个跟着一个地产生数字的步骤。如果我们希望展开一个无尽小数，譬如讲π，我们可以让一台图灵机作用于0上以产生整数部分3；然后使机器作用到1上，产生第一小数位1；然后使其作用于2上，产生第二小数位4；然后作用于3上，产生1，这样不断地下去。事实上，一定存在在这个意义上产生π的全部小数展开的图灵机，尽管要把它明显地造出来颇费一点周折。类似的评论也适用于许多其他无理数，譬如 =1.414213562……。然而，正如在下一章将要看到的，人们发现有些无理数（非常引人注目地）根本不能由任何图灵机产生。能以这种方式产生的数叫作可计算的（ Turing 1937 ）。那些不能的（实际上是绝大多数！）是叫作不可计算的。我们将在后面的章节中回到这件事体及有关的问题上来。按照物理理论，用可计算的数学结构能否足够地描述实在的物理对象（也就是人脑），是我们要关心的问题。

一般地讲，可计算性是数学中的一个重要问题。人们不应该将其当成只适合于这类数的事体。人们可有直接作用于诸如代数或三角的数学公式上的图灵机，或可进行微积分的形式运算的图灵机。人们所需的一切是某种准确地把所有涉及的数学符号编码成0和1序列的形式，然后再利用图灵机的概念。这毕竟是图灵在着手解决判定问题时心里所想的，即寻求回答具有一般性质的数学问题的算法步骤。我们将很快地回到这上面来。

通用图灵机

我还未描述通用图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分复杂。它的基本思想是把任意一台图灵机T的指令的表编码成在磁带上表示成0和1的串。然后这段磁带被当作某一台特殊的被称作通用图灵机U的输入的开始部分，接着这台机器正如T所要进行的那样，作用于输入的余下部分。通用图灵机是万有的模仿者。“磁带”的开始部分赋予该通用机器U需要用以准确模拟任何给定机器T的全部信息！

为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方式。考虑定义某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我们必须按照某种准确的方案把这表编码成0和1的串。我们可借助于以前采用的“收缩”步骤来办到。因为，如果我们用数2，3，4，5和6来分别代表符号R、L、STOP、箭头（→）以及逗点，那么我们就可以用110、1110、11110、111110以及1111110的收缩把它们编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成0和10的位数0和1。由于在该图灵机的表中，在二进制记数的结尾大写的数的位置足以把大写的0和1从其他小写的阿拉伯数字中区分开来，所以我们不需要用不同的记号。这样，110将被读成二进制数1101，而在磁带上被编码成1010010。特别是，0读作00，它可毫不含糊地被编码成0，或者作为被完全省略的符号。实际上我们可以不必对任何箭头或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些符号必须是什么。尽管在采用这个步骤时，在必要之处要提供一些额外的“虚”指令，以保证在这个顺序中没有缝隙。这样的做法具有相当好的经济性。（例如，图灵机XN+1没有告诉我们对110要做什么的命令，这是因为这条指令在机器运行时从不发生，所以我们应该插入一条“虚”指令，譬如讲1100→00R，它可合并到表中而不改变任何东西。类似地，我们应该把101→00R插入到XN×2中去。）若没有这些“虚的”，表中后面的指令的编码就会被糟蹋了。因为在结尾处的符号L或R足以把一条指令和另一条隔开，所以我们在每一指令中实际不需要逗号。因此，我们采用下面的编码：

0表示0或0，10表示1或1，110表示R，1110表示L，11110表示STOP。

作为一个例子，让我们为图灵机XN+1编码（插入指令1100→00R）。在去掉箭头和在它们紧前面的位数以及逗号之后。我们得到：

为了和早先说的相一致，我们可以去掉每一个00，并把每一个01简单地用1来取代，这样得到：

如下是在磁带上的相应的码：

我们总是可以把开始的110（以及它之前的无限的空白磁带）删去。由于它表示00R，这代表开头的指令00→00R。而我已隐含地把它当作所有图灵机共有的。这样仪器可从磁带记号左边任意远的地方向右跑到第一个记号为止。而且，由于所有图灵机都应该把它们的描述用最后的110结束（因为它们所有都用R、L或STOP来结束），所以我们也可把它（以及假想跟在后面的0的无限序列）删去。这可以算作两个小节约。所得到的二进制数是该图灵机的号码，它在XN+1的情况下为：

这一特殊的数在标准十进制记数法中为：

450813704461563958982113775643437908.

我们有时不严格地把号码为n的图灵机称为第n台图灵机，并用T n 来表示。这样，XN+1是第450813704461563958982113775643437908台图灵机！

我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如此平凡的（在扩展二进制记数法中）对自然数加一的运算，这真使人印象深刻！（尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN+1的二进制号码为：

101011010111101010

它只是十进制的177642！这样，只不过是把一个附加的1加到序列1的尾巴上的特别平凡的图灵机UN+1是第177642台图灵机。为了好奇的原因，我们可以注意在任一种进位制中“乘二”是在图灵机表中这两个号码之间的某处。我们找到XN×2的号码为10389728107，而UN×2的号码为

14929234

20919872026917547669.

人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的13台图灵机列出来：

其中，T 0 简单地就是向右移动并且抹去它所遇到的每一件东西，永不停止并永不往回退。机器T 1 最终得到同样的效应。但它是以更笨拙的方法，在它抹去磁带上的每个记号后再往后跳回。机器T 2 也和机器T 0 一样无限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T 3 是第一台可敬的机器，它的确是在改变第一个（最左边）的1为0后便谦虚地停止。

T 4 遭遇了严重的问题。它在磁带上找到第一个1后就进入了一个没有列表的内态，所以它没有下一步要做什么的指令。T 8 、T 9 和T 10 遇到同样的问题。T 7 的困难甚至更基本，把它编码的0和1的串涉及5个接续的1的序列：110111110。对于这种序列不存在任何解释，所以只要它在磁带上发现第一个1就被绊住。（我把T 7 或其他任何机器T n ，它的n的二进制展开包含多于4个1的序列称为不是正确指明的。）机器T 5 、T 6 和T 12 遭遇到和T 0 、T 1 和T 2 类似的问题。它们简单地、无限地、永远不停地跑下去。所有T 0 、T 1 、T 2 、T 4 、T 5 、T 6 、T 7 、T 8 、T 9 、T 10 和T 12 都是伪品！只有T 3 和T 11 是可工作的，但不是非常有趣的图灵机。T 11 甚至比T 3 更谦虚，它在第一次遇到1时就停止，并且没有改变任何东西！

我们应该注意到，在表中还有一个多余。由于T 6 和T 12 从未进入内态1，机器T 12 和T 6 等同，并在行为上和T 0 等同。无论这个多余还是表中的图灵机伪品我们都不必为之烦恼。人们的确可以改变编码以摆脱许多伪品和大大减少重复。所有这些都是以使我们可怜的通用图灵机变得更复杂作为代价。通用图灵机必须把所读到的号码n解码并假装成图灵机T n 。如果我们可以把所有伪品（或者多余量）取走，这还是值得做的。但是，我们很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。

例如，可方便地把具有

……0001101110010000……

接续记号的磁带解释成某个数字的二进制表示。我们记得0在两端会无限地继续下去，但是只有有限个1。我还假定1的数目为非零（也就是说至少有一个1）。我们可以选择去读在第一个和最后一个1（包括在内）之中的有限的符号串，在上述的情况是为一自然数的二进制写法：

110111001，

它在十进制表示中为441。然而，这一过程只能给我们奇数（其二进制表示以1结尾的数）。而我们要能表示所有的自然数。这样，我们采取移走最后的1的简单方案（这个1仅仅被当作表示这一程序的终止记号），而把余下来的当成二进制数来读 [5] 。因此，对于上述的例子，我们有二进制数：

11011100，

它是十进制的220。这个步骤具有零也用磁带上的记号代表的好处，也就是：

……0000001000000……

我们考虑图灵机T n 对我们从右边提供给它的磁带上（有限的）0和1的串的作用。根据上面给出的方案，可方便地把这串也考虑作某一个数，譬如m的二进制代表。我们假定，机器T n 在进行了一系列的步骤后最终到达停止（即到达STOP）。现在机器在左边产生的二进制数串是该计算的答案。让我们也以同样方式把这当作，譬如是p的二进制代表来读。我们把表达当第n台图灵机作用到m上时产生p的关系写成：

T n （m）=p.

现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一对数n和m以得到数p的一个特别运算。（这样，若给定两个数n和m，视第n台图灵机对m作用的结果而得出p。）这一特别运算是一个完全算法的步骤。所以它可由一台特殊的图灵机U来执行。也就是说，U作用到一对（n, m）上产生p。由于机器U必须作用于n和m两者以产生单独结果p，我们需要某种把一对（n, m）编码到一条磁带上的方法。为此，我们可假定n以通常二进制记数法写出并紧接着以序列111110终结。（我们记得，任一台正确指明的图灵机的二进制数都是仅仅由0，10，110，1110和11110组成的序列，因此它不包含比4个1更多的序列。这样，如果T n 是正确指明的机器，则111110的发生的确表明数n的描述已终结。）按照我们上面的规定，跟着它的每一件东西简单地是代表m的磁带（也就是，紧跟二进制数m的是1000……）。这样，这第二个部分简单地就是T n 假设要作用的磁带。

作为一个例子，如果我们取n=11和m=6当做U要作用的磁带，其记号序列为：

……000101111111011010000……

这是由以下

……0000（开始的空白带）

1011（11的二进制表示）

111110（终结n）

110（6的二进制表示）

10000……（余下的磁带）

组成的。

在T n 作用到m上的运算的每一接续的步骤，图灵机U要做的是去考察n的表达式中的接续数位的结构，以使得在m的数位（也就是T n 的磁带）上可进行适当的代换。在原则上（虽然在实践中肯定很繁琐）不难看到人们实际如何建造这样的一台机器。它本身的指令表会简单地提供一种，在每一阶段读到被编码到数n中的“表”中，应用到m给出的磁带的位数时，合适元素的手段。肯定在m和n的数位之间要有许多前前后后的进退，其过程会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把它称为通用图灵机。把该机器对一对数n和m的作用表为U（n, m），我们得到：

U（n, m）=T n （m）.

这里T n 是一台正确指明的图灵机 [6] 。当首先为U提供数n时，它准确地模拟第n台图灵机！

因为U为一台图灵机，它自身也必须有一号码；也就是说，我们有：

U=T u ，

此处号码u待定。u究竟是多少呢？事实上，我们可以准确地给出：

u=72448553353393175771983950396157112379523606725565596311 08144796606505059404241090310483613632359365644443458382226 88327876762655614469281411771501784255170755408565768975334 63569424784885970469347257399885822838277952946834605210611 69835945938791885546326440925525505820555989451890716537414 89603309675302043155362503498452983232065158304766414213070 88193297172341510569802627346864299218381721573334828230734 5371342147505974034518437235959309064002432107734217885149276079759763441512307958639635449226915947965461471134570014 50481673375621725734645227310544829807849651269887889645697 60906634204477989021914437932830019493570963921703904833270 88259620130177372720271862591991442827543742235135567513408 42222998893744105343054710443686958764051781280194375308138 70639942772823156425289237514565443899052780793241144826142 35728619311833261065612275553181020751108533763380603108236 16750456358521642148695423471874264375444287900624858270912 40422076538754264454133451748566291574299909502623009733738 13772416217274772361020678685400289356608569682262014198248 62169890260913094029857060017430067008689675903447341741278 7425581201549366393899690581773859165405535670409282133222 16314109787108145997866959970450968184190629944365601514549 0488092208448003482249207730403043188429899393135266882349 66210194716191070146196852319284748203449589770955356110702 75817487333272966789987984732840981907648512726310017401667 8736347760585724503696443489799203448999745566240293748766 88397514044516657077500605138839916688140725455446652220507 24262392379211525318162512536305093172863142200406457130527 58023076651833519956891397481375049264296050100136519801869 45639498

（或者至少是这等数量级的其他的可能性）。这个数无疑是极其巨大，但是我似乎没有办法使它变小许多。虽然我的图灵机编码步骤和号码指定是相当合理和简单的，但是在一台实际的通用图灵机的编码中仍然不可避免地导向这么大的一个数 [7] 。

我曾说过，实际上所有现代通用电脑都是通用图灵机。我并不是说，这种电脑的逻辑设计必须在根本上和我刚刚给出的通用图灵机的描述非常相似。其要点可以简述为，首先为任一台通用图灵机提供一段适当的程序（输入磁带的开始部分）可使它模拟任何图灵机的行为！在上面的描述中，程序简单地采取单独的数（数n）的形式。但是，其他的步骤也是可能的，图灵原先方案就有许多种变化。事实上，在我自己的描述中，已经有些偏离图灵的原型。但是对于我们当前的目的，这些差别中没有一个是重要的。

希尔伯特问题的不可解性

我们现在回到当初图灵提出其观念的目的，即解决希尔伯特的范围广泛的判定问题：是否存在某种回答属于某一广泛的，但是定义得很好的集合的所有数学问题的机械步骤？图灵发现，他可以把这个问题重述成他的形式，即决定把第n台图灵机作用于数m时实际上是否会停止的问题。该问题被称作停机问题。很容易建造一个指令表使该机器对于任何数m不停。（例如，正如上面的n=1或2或任何别的在所有地方都没有STOP指令的情形）。也有许多指令表，不管给予什么数它总停（例如n=11）；有些机器对某些数停，但对其他的数不停。人们可以公正地讲，如果一个想象中的算法永远不停地算下去，则并没有什么用处。那根本不够格被称作算法。所以一个重要的问题是，决定T n 应用在m时是否真正地给出答案！如果它不能（也就是该计算不停止），则就把它写成：

T

n

（m）=□。

[在这记号中还包括了如下情形，即图灵机在某一阶段由于它找不到合适的告诉其下一步要做什么的指令而遇到麻烦，正如上面考虑的伪品机器T 4 和T 7 。还有不幸的是，我们粗看起来似乎成功的机器T 3 现在也必须被归于伪品：T 3 （m）=□，这是因为T 3 作用的结果总是空白带，而为使计算的结果可赋予一个数，在输出上至少有一个1！然而，由于机器T 11 产生了单独的1，所以它是合法的。这一输出是编号为0的磁带，所以对于一切m，我们都有T 11 （m）=0。]

能够决定图灵机何时停止是数学中的一个重要问题。例如，考虑方程：

（如果专门的数学方程使你忧虑，不要退缩！这一方程只不过是作为一个例子，没有必要详细地理解它。）这一特殊的方程和数学中著名的或许是最著名的未解决的问题相关。该问题是：存在任何满足这方程的自然数集合w, x，y, z吗？这个著名的称作“费马大定理”的陈述被伟大的17世纪法国数学家皮埃尔·德·费马（1601—1665）写在丢番图的《代数》一书空白的地方。费马宣布这方程永远不能被满足 [7] [8] 。虽然费马以律师作为职业（并且是笛卡儿的同时代人）。他却是那个时代最优秀的数学家。他宣称得到了这一断言的“真正美妙的证明”，但那里的空白太小写不下。可惜迄今为止既没有人能够重新证明之，也没有人能找到任何和费马断言相反的例子 ！

很清楚，在给定了4个数（w, x，y, z）后，决定该方程是否成立是计算的事体。这样，我们可以想象让一台电脑的算法一个接一个地跑过所有的四数组，直到方程被满足时才停下。（我们已经看到，存在于一条单独磁带上，把数的有限集合以一种可计算方式编码成为一个单独的数的方法。这样，我们只要跟随着这些单独的数的自然顺序就能“跑遍”所有的四数组。）如果我们能够建立这个算法不停的事实，则我们就有了费马断言的证明。

可以用类似的办法把许多未解决的数学问题按图灵机停机问题来重述。“哥德巴赫猜想”即是这样的一个例子，它断言比2大的任何偶数都是两个素数之和 。决定给定的自然数是否为素数是一个算法步骤，由于人们只需要检验它是否能被比它小的数整除，所以这只是有限计算的事体。我们可以设计跑遍所有偶数6，8，10，12，14，……的一台图灵机，尝试把它们分成奇数的对的所有不同的方法：

6=3+3，8=3+5，10=3+7=5+5，12=5+7，

14=3+11=7+7，……

对于这样的每一个偶数检验并确认其能分成都为素数的某一对数。（我们显然不需要去检验除了2+2之外的偶的被加数对，由于除了2之外所有素数都是奇的。）只有当我们的机器达到一个由它分成的所有的任何一对数都不是素数对的偶数为止才停止。我们在这种情形就得到了哥德巴赫猜想的反例，也就是说一个（比2大的）偶数不是两个素数之和。这样，如果我们能够决定这台图灵机是否会停，我们也就有了判定哥德巴赫猜想真理性的方法。

这里自然地产生了这样的问题：我们如何判定任何特殊的图灵机（在得到特定输入时）会停止否？对于许多图灵机回答这个问题并不难：但是偶尔地，正如我们上面得到的，这答案会涉及一个杰出的数学问题的解决。这样，存在某种完全自动地回答一般问题，即停机问题的算法步骤吗？图灵指出这根本不存在。

他的论证的要点如下所述，我们首先假定，相反的，存在这样的一种算法 。那么必须存在某台图灵机H，它能“判定”第n台图灵机作用于数m时，最终是否停止。我们假定，如果它不停的话，其输出磁带编号为0，如果停的话为1：

在这里人们可采取对通用图灵机U用过的同样规则给对（n, m）编码。然而，这会引起如下技术问题，对于某些数n（例如n=7），T n 不是正确指定的，而且在磁带上记号111101不足以把n从m分开。为了排除这一个问题，让我们假定n是用扩展二进制记数法而不仅仅是二进制记数法来编码，而m正和以前一样用通常的二进制记数法。那么记号110实际上将足以把n和m区分开来。在H（n；m）中用分号，而在U（n, m）中用逗号就是为了表明这个改变。

现在让我们想象一个无穷阵列，它列出所有可能的图灵机作用于所有可能的不同输入的所有输出。阵列的n行展现当第n台图灵机应用于不同的输入0，1，2，3，4，……时的输出：

我在此表中稍微搞了点欺骗，并且没有把图灵机按它们的实际编号列出。由于所有n比11小的机器除了□外没有得到任何东西，而对于n=11只得到0，所以那样做的话就会得到一张一开始就显得过于枯燥的表。为了使此表一开始就显得更有趣，我假定已得到某种更有效得多的编码。事实上我只是相当随机地捏造这张表的元素，仅仅是为了给出有关它的外表的大体印象。

我不要求用某一个算法实际计算过这一个阵列。（事实上，正如我们很快就要看到的，不存在这样的算法。）我们仅仅是假想，真正的表不知怎么搞的已经摆在我们面前。如果我们试图计算这一个阵列，正是□的发生引起了困难。因为既然那些计算简单地一直永远算下去，我们也许弄不清什么时候把□放在某一位置上！

然而，如果我们允许使用假想的H，由于H会告诉我们□实际上在什么地方发生，我们就可以提供一种产生该表的计算步骤。但是相反的，我们用0来取代每一次□的发生，就这样利用H把□完全除去。这可由把计算H（n；m）放在T n 对m作用之前而做到；然后只有如果H（n；m）=1时（也就是说，只有如果计算T n （m）实际上给出一个答案时），我们才允许T n 作用到m上，而如果H（n；m）=0（也就是如果T n （m）=□），则简单地写为0。我们可把新的步骤（也就是把H（n；m）的作用放在T n （m）之前得到的）写成：

T n （m）×H（n；m）.

（我在这里使用数学运算顺序的普通习惯：在右边的先进行。请注意，我们在符号运算上有：□×0=0。）

现在这张表变成：

我们注意到，假定H存在，该表的行由可计算的序列组成。（我用一个可计算序列表明一个其接连的值可由一个算法产生出来的一个无限序列；也就是存在一台图灵机，当它依序地应用于自然数m=0，1，2，3，4，5，……上时，就得到了这个序列的接续元素。）现在，我们从该表中可以注意到两个事实。首先自然数的每一可计算序列必须在它的行中出现在某处（也许出现好几回）。这个性质对于原先的带有□的表已经是真的。我们只不过是简单地加上一些行去取代“伪品”的图灵机（也就是至少产生一个□的那些）。其次，我们已经假定，图灵机H实际上存在，该表已被计算地（也就是用某个确定的算法）由步骤T n （m）×H（n；m）产生。换言之，存在某一台图灵机Q，当它作用于一对数（n；m）时就会在表中产生合适的元素。为此我们可以在Q的磁带上以和在H中一样的方式对n和m编码。我们得到：

Q（n；m）=T n （m）×H（n；m）.

现在我们应用乔治·康托尔的“对角线方法”的天才的和强有力的技巧的变种。（下一章将看到康托尔对角线方法的原型。）考虑现在用粗体字标明的对角线元素：

这些元素提供了某一序列0，0，1，2，1，0，3，7，1，……，现在把它的每一元素都加上1就得到

1，1，2，3，2，1，4，8，2，……

假设我们的表是计算地产生的，那么这就清楚地是一个可计算的步骤，而且它为我们提供了某一个新的可计算的序列。事实上为1+Q（n；n），也就是：

1+T n （n）×H（n；n）

（由于对角线是令m等于n而得到的）。但是，我们的表包括了每一可计算的序列，所以我们新的序列必须在表中的某一行。然而，这是不可能的！由于我们新序列和第一行在第一元素处不同，和第二行在第二元素处不同，和第三行在第三元素处不同，等等。这是一个明显的冲突。正是这个冲突，建立了我们所要证明的，即在事实上图灵机H不存在！不存在决定一台图灵机将来停止与否的通用算法。

另一种重述这个论证的方法是注意到，在假定H存在时，对于算法1+Q（n；n）（对角线步骤！）存在某一图灵机号码，譬如k，这样我们有：

1+T n （n）×H（n；n）=T k （n）.

但是，如果我们在这个关系中代入n=k就得到：

1+T k （k）×H（k；k）=T k （k）.

因为如果T k （k）停止，我们就得到了不可能的关系式：

1+T k （k）=T k （k），

[由于H（k；k）=1]，而如果T k （k）不停止[这样H（k；k）=0]，我们有同样不协调的结果：

1+0=□，

所以前面的假定导致一个矛盾。

一台特定的图灵机是否停止是一个定义完好的数学问题（反过来，我们已经看到，各种有意义的数学问题可被重述成图灵机的停机问题）。这样，依靠显示不存在决定图灵机停机问题的算法，图灵（正如丘奇用自己十分不同的手段）指出，不存在决定数学问题的一般算法。希尔伯特判定问题没有解答！

这不是说，在任何个别的情形下，我们不可能决定某些特殊数学问题的真理或非真理；或者决定某一台给定的图灵机是否会停止。我们可以利用一些技巧或者仅仅是常识，就能在一定情况下决定这种问题。（例如，如果一台图灵机的程序表中不包括STOP指令。或者只包含STOP指令，那么常识就足以告诉我们它会不会停止！）但是，不存在一个对所有的数学问题，也不存在对所有图灵机以及所有它们可能作用的数都有效的一个算法。

我们似乎现在已经建立了，至少存在某些非决定的数学问题。然而，我们从未做过这种事！我们还没有展示过，存在某种特别尴尬的数时，它在某种绝对的意义上，不可能决定该机器是否停止。的确，正如我们很快就要看到的，情况刚好相反。我们关于单独问题的不可解性一点也没提，仅仅是说关于问题的族的算法的不可解性。在任何单独的情形下，答案或者为“是”或者为“非”，所以肯定存在一个决定那个特定情形的算法，也就是在它面临该问题时，依情况而定，会简单地讲“是”或“非”。当然，困难在于我们可能不知道用这些算法中的哪一个。那就是决定一个单独陈述而不是决定一族陈述的数学真理的问题。重要的是要意识到，算法本身不能决定数学真理。一个算法的成立总是必须由外界的手段来建立起来。

如何超越算法

我们在以后论及哥德尔定理时再回到决定数学陈述的真理性问题（参阅第4章）。我希望在此刻指出，图灵的论证比我迄今所暗示的更具建设性而更少负面性。我们肯定还没有展示出一台特殊的图灵机，它在某种绝对的意义上不能决定其是否停止的问题。的确，如果我们仔细地考察该论证就会发现，我们的步骤本身实际上已经隐含地告诉我们，对这利用图灵步骤建造的似乎“极端荒谬”的机器的答案！

我们看看这是怎么来的。假定我们有某一个算法，它有时有效地告诉我们什么时候一台图灵机将不停止。正如在上面概述的，图灵步骤将明白地展现了一台图灵机计算，对这计算那个特殊算法不能决定其是否停止。然而，在这样做的同时，它实际上使我们在这种情况下看到了答案！我们展现的特殊的图灵机计算的确不会停止。

为了仔细考查这是怎么引起的，假定我们具有一个这样有时有效的算法。正如以前那样，我们用H来标志这个算法（图灵机），但是现在允许该算法有时不能告诉我们一台图灵机在实际上将不停止：

这样，当T n （m）=□时H（n；m）=□是一种可能性。实际上存在许多这种算法H（n；m）。[例如，只要T n （m）一停止，H（n；m）就能简单地产生1，尽管那个特殊的算法几乎没有什么实际的用处！]

除了不把所有的□用0来取代而留下一些以外，我们可以像上述那样仔细地顺着图灵的步骤。正如以前那样，对角线过程提供了对角线上的第n个元素

1+Tn（n）×H（n；n）.

[只要H（n；m）=□，我们就将得到一个□。注意□×□=□，1+□=□。]这是一个完好的计算，所以它是由某一台，譬如讲第n台图灵机得到的，而且现在我们确实有：

1+T n （n）×H（n；m）=T k （n）.

我们看第k个对角元素，也就是n=k，就会得到：

1+T k （k）×H（k；k）=T k （k）.

如果计算T k （k）停止，我们就有了一个矛盾[由于假定只要T k （k）停止H（k, k）就为1，则方程导致不协调性：1+T k （k）=T k （k）。所以T k （k）不能停止，也就是：

T k （k）=□。

但是，算法不能“知道”这个。因为如果该算法给出H（k, k）=0，则我们应该又导致矛盾（我们得到了在符号上不成立的关系：1+0=□）。

这样，如果我们能找到k，就将知道如何去建造击败我们知道其答案的算法的特别计算！我们怎么找到k呢？这是一项艰巨的工作。我们需要做的是仔细考察H（n；m）和T n （m）的构造，然后仔细弄清1+T n （n）×H（n；n）作为一台图灵机是如何动作的。我们发现这台图灵机的号码为k。要把这一切弄透彻肯定是复杂的。但它是可以办得到的 [11] 。由于这种复杂性，若不是因为我们为了击败H而特地制造T k （k）的这个事实，我们对计算T k （k）毫无兴趣！重要的是，我们有了定义很好的步骤，不管我们的H是哪一个，该步骤都能找到合适的k，使得T k （k）击败H，因此这样我们可以比该算法做得更好。如果我们认为自己仅仅比算法更好些，也许会给我们带来一些小安慰！

事实上，该过程被定义得如此之好，以至于在给定的H下，我们可找到产生k的一个算法。这样，在我们过于得意之前必须意识到，由于这个算法事实上“知道”T k （k）=□，所以它能改善 [9] H，是不是？在上面提到一个算法时，用拟人化的术语“知道”是有助的。然而，该算法仅仅是跟随我们预先告诉它去跟随的法则，这难道不是我们在“知道”吗？或者我们自己，仅仅是在跟随我们的头脑的构造和我们的环境所预先编排我们去跟随的规则？这问题实在不只是简单的算法问题，而且是人们如何判断何为真何为伪的问题。这是我们必须重新讨论的中心问题。数学真理（及其非算法性质）的问题将在第4章考虑。现在我们至少对术语“算法”和“可计算性”的意义以及某些相关的问题已有些领略。

丘奇的λ计算法

可计算性的概念是一个非常重要和漂亮的数学观念。它又是相当近代的，具有这样基本性质的事体进入数学的王国是20世纪30年代的事。这个观念已经渗透到数学的所有领域中去（虽然这一点确实是真的，但是大多数数学家通常不去忧虑可计算性的问题）。该观念的威力有一部分来自于这一个事实，即数学中一些定义得很好的运算实际上不是可计算的（例如图灵机的停机问题；第4章还可以看到其他例子）。因为如果不存在这种不可计算的事体，则可计算性的概念便没有多少数学的兴趣。数学家毕竟喜欢困惑的东西。让他们决定某些数学运算是否为可计算的可能是非常迷人的困惑。因为那个困惑的一般解答本身是不可计算的，这一点尤其迷人！

有一件事要弄清楚。可计算性是一个真正“绝对的”数学概念。它是一种抽象的观念，它完全超越按照我们描述的“图灵机”的任何特别实现之外。正如我在以前所评论的，我们不必对为表征图灵的天才而采用特别的手段的“磁带”和“内态”等赋予任何特别的意义。还有表达可计算性观念的其他方法，历史上最早的是美国逻辑学家阿伦佐·丘奇在斯蒂芬·C.克林协助下提出的杰出的“λ计算法”。丘奇的步骤和图灵的完全不同，并且更为抽象得多。事实上，在丘奇陈述他观念的形式中，在它们和任何可以称作“机械的”东西之间只有一点明显的连接。丘奇步骤背后的关键观念在其最本质上的确是抽象的，实际上丘奇把这步骤称为“抽象化”的一个数学运算。

不仅是因为丘奇方案强调可计算性是一个独立于计算机器的任何特别概念的数学观念，而且它阐明了在数学中抽象观念的威力，所以我感到值得花一点时间来简要地描述它。对数学观念不熟悉或者对这件事本身不感好奇的读者，在这一阶段可以跳到下一章去，这不会对论证的过程产生多少损失。尽管如此，这样的读者若愿意和我多忍受一阵会得到好处，并且能见证丘奇方案的某些魔术般的经济性（参见 Church 1941 ）。

人们在此方案中关心的是，譬如由以下表示的对象的“宇宙”：

a, b，c, d，……，z, a'，b'，……，z'，a''，b''，……，

a'''，……，a''''，……，

其中每一元素代表一个数学运算或函数。（之所以用带撇的字母，只不过是便于无限地给出这些符号以表示这种函数。）这些函数的“自变量”，即它们所作用的东西，是同一类型的其他东西。也就是函数。此外，一个这种函数作用于另一个函数的结果（或“值”）仍是一个函数。（在丘奇的系统中的确具有美妙的概念经济性。）这样，当我们写

a=bc

时，我们是指函数b作用于函数c的结果为另一函数a。要在这个方案中表达两个或更多变量的函数的观念并没有困难。如果我们希望把f认为两个变量，譬如讲p和q的函数，我们可以简单地写：

（fp）q

（这是函数fp作用于q的结果）。对于三变量函数我们考虑：

（（fp）q）r，

等等。

让我们引进抽象化的有力的运算。为此我们使用希腊字母λ（拉姆达），而且直接再加上一个字母如x，以代表一个丘奇函数，我们把它当成“虚变量”。任何发生于紧跟在这后面的方括号内的表达式中的变量x是仅仅被当作一个“插口”，可以往里面代入任何跟在整个表达式后的任何东西。这样，如果我们写：

λx.[fx]，

我们是说，当它作用到譬如讲函数a上时，就产生结果fa。那就是：

（λx.[fx]）a=fa。

换言之，λx.[fx]简单地就是函数f，即：

λx.[fx]=f。

这里只用一点思维就够了。数学的一个美妙在于，初看起来是如此卖弄学识的、琐碎的东西，也是人们非常容易完全失去要点的东西。让我们考虑从中学数学拿来的一个熟悉的例子。我们取函数f为对一个角度取正弦的三角运算，这样抽象的函数“sin”被定义为：

λx.[sinx]=sin。

（不必为何以“函数”x可当作一个角度而忧虑。我们很快就会看到数可被当成函数的某种方法；而一个角度只是一个数。）迄今为止的一切的确是相当无聊的。让我们设想，记号“sin”还没被发明，但是我们熟悉sinx的级数展开表达式：

然后我们可以定义：

请注意，我们甚至可以更简单地定义，譬如讲“六分之一立方”的运算，而它是没有标准的“函数”记号的：

而且我们发现，例如：

从丘奇的基本函数运算简单构造的表达式对于现在的讨论更为贴切，例如：

λf.[f（f x）]。

这是一个函数，当它作用于另一函数，譬如讲g时，产生g两次迭代地作用于x上的函数，也就是：

（λf.[f（f x）]）g=g（gx）。

我们也可以首先“抽象化走”x以得到：

λf.[λx.[f（f x）]]，

此式可以缩写成：

λfx[f（fx）]。

这是当作用于g时产生“g被迭代两次”的函数。事实上，这正是丘奇将其和自然数2相等同的函数。

=λf x.[f（fx）]，

这样，（2g）y=g（gy）。它类似地定义：

=λf x.[f（f（fx））]，

=λfx[f（f（f（fx）））]，等等，

以及

=λf.[fx]，0=λfx.[x]。

丘奇的“2”真的更像“两次”，它的“3”是“3次”等。这样3在一个函数f上的作用也就是3f，是“把f迭代3次”的运算。因此，3f在y上的作用是（3f）y=f（f（f（y）））。

让我们看一个非常简单的算术运算，也就是如何把加到一个数上的运算在丘奇方案中表达出来。定义

S=λabc.[b（（ab）c）]。

为了阐明S的确简单地把加到用丘奇记号表示的一个数上，让我们做这样的验算：

这是由于（3b）c=b（b（bc））。很清楚，这可同样好地适用于任何其他自然数。（事实上λabc.[（ab）（bc）]可以和S一样好地做到。）

把一个数乘二又如何呢？这种加倍可由

D=λabc.[（ab）（（ab）c）]

获得，它可再次由作用于3上而得到验证：

事实上，加法、乘法和自乘的基本算术运算可分别定义为：

A=λfgxy.[（（fx）（gx））y]，

M=λfgx.[f（gx）]，

P=λfg.[fg]。

实际上，读者可以确信——要不就不加考察信以为真，即：

其中m和是n丘奇的两个自然数的函数，m+n是它们和的相应函数，等等。最后那个公式是最令人惊异的。让我们仅仅验证其m=2，n=3的情形：

减法和除法不是这么容易定义的（我们的确需要某种当m比n小时“m-n”以及当m不能被n整除时“m÷n”的约定。事实上，20世纪30年代早期，克林发现如何在丘奇的方案中表达减法运算就被认为是这一学科的重要里程碑！后来接着又有其他的运算。最后，丘奇和图灵在1937年独立地指出，不管什么样的可计算的（或算法的）运算（现在在图灵机的意义上）都可以按照丘奇的一种表达式获得（而且反之亦然）。

这是一个真正惊人的事实，它被用来强调可计算性思想的基本客观性以及数学特征。初看起来，丘奇的可计算性概念和计算机器没有什么关系。然而，它和实际计算具有某些基本关系。尤其是，有力而灵活的电脑LISP语言以一种根本的方式参与到丘奇计算法的基本结构中来。

正如我早先指出的，还有其他定义可计算性概念的方法。波斯特的计算机器的概念和图灵的非常接近，并且几乎是同时独立提出的。近世还有更有用的可计算性（递归性）的定义，这是J.赫伯拉德和哥德尔提出的。H.B.邱雷在1929年，以及M.轩芬克勒在1924年稍早些时候提出了不同的方法，丘奇计算法就是部分地由此发展而来（参见 Gandy 1988 ）。现在研究可计算性的手段（诸如在 Cutland 1980 中描述的一台无限记录机器）在细节上和图灵原先的相差甚多，而且它们更实用得多。然而，不管采用那种不同的手段，可计算性的概念仍然相同。

正如许多其他的数学观念，尤其是更漂亮的、更基本的那些，可计算性的观念似乎自身具有某种柏拉图的实在性。在下面两章，我们应该探讨的正是数学概念的柏拉图实在性的这个神秘问题。

[7] 记住我说的自然数是指0，1，2，3，4，5，6，……。我写成“x+1”和“w+3”等，而不写成费马断言的更熟知的形式（x w +y w =z w ；x, y，z＞0，w＞2）的原因是，我们允许x, w等为从零开始的所有自然数。

[11] 事实上，由于在上面建造通用图灵机U已使我们能把T n （n）写成作用于n上的一台图灵机，所以已经得到这个最难的部分。 5a8RpGFUFOZ/IVfqHgaMWxxyFBt6+M/gE7hvv1BIZIQW//iJVknUB2CV/ijqsX3u