第二章 算法和图灵机 

算法概念的背景 
  
　 
  
　　算法、图灵机或者普适图灵机究竟是什么呢？为何这些概念在可以构成“思维仪器 
”的东西的现代观点中占有如此核心的地位呢？是否在原则上存在一个算法可达到的绝 
对极限呢？为了充分地讨论这些问题，我们必须比较细致地考察算法和图灵机的观念。 
  
　　我在下面的各种讨论中，有时将要用到一些数学表达式。我注意到有些读者排斥这 
类东西，或者觉得它们吓人。如果你是这种读者，那么我请你原谅，并请你按照我在“ 
敬启读者”中的建议。其实，这里论证所需的数学知识并不超过小学水平，但要仔细地 
弄通它们，则需要一些认真的思考。事实上，大部分描述是十分显明的，只要细心地跟 
随就能很好地理解。但是，如果人们只是为了稍微领略其风味而取其精华，也能有很大 
的收益。另一方面，如果你是一位专家，我还要请你原谅。我猜想，它仍然值得你花一 
段时间把我所说的看过一遍，并且可能会有一两件东西引起你的兴趣。 
  
　　“算法”这个词来自于九世纪波斯数学家阿布·雅发·穆罕默德·依伯恩·缪莎· 
阿勒��霍瓦里松，他在公元825年左右写了一本影响深远的《代数对话录》。“算 
法”这个字现在之所以被拼写成“algorithm”，而不是早先的更精确的“algorism”， 
似乎是由于和“算术”(arithmetic)相关联所引起的。（还值得指出的是，“代数”(al 
gebra)这个词来源于该书的题目的阿拉伯字“al jabr”。) 
  
　　然而，比阿勒��霍瓦里松的书早很多就知道了算法的实例。现在被称作欧几 
里德算法的找两个数最大公约数的步骤是在古希腊（公元前300年左右）即有记载的一个 
最熟知的例子。让我们看看这是如何进行的。随意取两个特定的数，譬如讲1365和3654 
。所谓的最大公约数是可以同时整除这两个数的最大的整数。在应用欧几里德算法时， 
我们让这两数中的一个被另一个除并取余数，在3654中取出1365的两倍，其余数为924（ 
=3654-2730）。我们现在用此余数即924以及我们刚用的除数即1365去取代原先的两个数 
。我们用这一对新的数重复上述步骤，用924去除1365，余数为441。这又得到新的一对4 
41和924，我们用441除924，得到余数42（=924-882），等等，直到能够被整除为止。我 
们把这一切如下列出： 
  
　　3654÷1365 给出余数924 
  
　　1365÷924 给出余数441 
  
　　924÷441 给出余数42 
  
　　441÷42 给出余数21 
  
　　42÷21 给出余数0。 
  
　　我们最后用于做除数的21即是所需要的最大公约数。 
  
　　欧几里德算法本身是我们寻找这一因子的系统步骤。我们刚才把这一步骤应用于特 
殊的一对数，但是这步骤本身可被十分广泛地应用于任意大小的数。对于非常大的数， 
要花很长时间来执行该步骤，数字越大则所花的时间越长。但在任何特定的情形下，该 
步骤最后会终结，并在有限的步骤内得到一个确定的答复。每一步骤所要进行的运算都 
是非常明了的。此外，尽管它可应用到大小没有限制的自然数上去的这个事实，但是可 
以用有限的术语来描述整个过程。（“自然数”简单地就是通常的非负1整数0，1，2，3 
，4，5，6，7，8，9，10，11……）。的确很容易建立一个（有限的）描述欧几里德算 
法全部逻辑运算的“流程图”。 
  
　 
  
　　应该提到，我们在这里隐含地假定，已经“知道”如何实行从两个任意自然数A和B 
的除法中得到余数的必须的基本运算，所以这一步骤还未完全被分解成最基本的部分。 
那种运算又是算法的，是用我们在小学学到的除法的非常熟悉的步骤来进行的。在实际 
上，这个步骤比欧几里德的其他部分更复杂不少，但是可以再为它建立一个流程图。其 
复杂性主要起源于这个事实，即我们是（假定）对自然数用标准的“十进位”记号，这 
样子我们需要列出全部的乘法表和忧虑移位等等。如果我们简单地用一连串某种n个记号 
来代表数n，例如……代表五，那么可从非常初等的算法运算看到余数的形成。为了得到 
当A被B除时的余数，可以简单地从代表A的记号中不断取走代表B的符号串，直到最后余 
下的记号不够再进行这种运算为止。最后剩下的符号串提供了所需的答案。例如，为了 
得到十七被五除的余数，我们可以简单地从……………不断地取走五的序列……正如下 
面所示： 
  
　　……………… 
  
　　…………… 
  
　　………… 
  
　　．． 
  
　　由于我们不能再继续这种运算，所以很清楚，其答案是二。 
  
　　用这种连续减法找到除法余数的流程图可由下图给出： 
  
　 
  
　　为了使欧几里德算法的全部流程图完整，我们把上面形成余数的流程图代入到原先 
流程图的中右部的盒子中去。这种把一个算法向另一个代入是一种普遍的编电脑程序的 
步骤。上述寻求余数的算法是一道子程序的例子，也就是说，它是由主程序当作它的运 
算的一部分（通常是预先知道的）召来使用的算法。 
  
　　当然，把数n简单地用n个斑点来表示，在涉及到大数时效率非常低，这就是为什么 
我们通常用更紧凑的诸如标准的（十进位）系统的原因。然而，我们在这里并不特别关 
心运算或记号的效率。我们所关心的是运算在原则上是否可被算法地实行的问题。如果 
我们用一种数的记号是算法的东西，则用另一种记号也是算法的。两种情况中只有在细 
节上和复杂性上有差别。 
  
　　欧几里德算法只是在整个数学中可找到的大量的经典算法步骤之一。尽管算法的这 
一特殊例子的历史渊源，一般算法概念的准确表达只从本世纪起才有记载，也许这是令 
人印象深刻的。事实上，这一概念的各种不同描述都是在本世纪三十年代给出的。称作 
图灵机的概念是最直接的、最有说服力的、也是历史上最重要的。相当仔细地考查这些 
“机器”将是很适当的。 
  
　　关于图灵“机”有一件事必须记在心里，就是说它是一段“抽象数学”，而不是一 
个物理对象。这一概念是由英国数学家、非凡的破码专家兼电脑科学的开山鼻祖阿伦· 
图灵在1935--1936年间提出的（图灵1937）。其目的是为了解决称为判决问题的一个范 
围广阔的问题。它是由伟大的德国数学家大卫·希尔伯特部分地于1900年巴黎国际数学 
家会议上（“希尔伯特第十问题”），更完整地于1928年玻罗那国际会议上提出的。希 
尔伯特不多不少地要求解决数学问题的一般算法步骤，或者不如讲，是否在原则上存在 
这样步骤的问题。希尔伯特还有一个要把数学置于无懈可击的坚固基础上的宏伟规划， 
其中公理和步骤法则一旦定下就不能变。但是在图灵完成其伟大的工作之际，这个规划 
已经遭受到由奥地利才气焕发的逻辑学家库尔特·哥德尔在1931年证明的令人吃惊的定 
理的粉碎性打击。我们将在第四章考虑哥德尔定理及其意义。图灵关心的希尔伯特问题 
（判决问题）超越出任何按照公理系统的特殊的数学形式。问题在于，是否存在能在原 
则上一个接一个地解决所有（属于某种适当定义的族的）数学问题的某种一般的机械步 
骤？ 
  
　　回答这一问题的部分困难在于决定什么叫做“机械过程”。这概念处于当时正常的 
数学概念之外。为了掌握它，图灵设想如何才能把“机器”的概念表达出来，它的动作 
被分解成基本的项目。这一些似乎是清楚的，图灵也把人脑当成在他意义上的“机器” 
的例子。这样，由人类数学家在解决数学问题时进行的任何活动，都可以被冠以“机械 
步骤”之名。 
  
　　虽然这一有关人类思维的观点似乎对于图灵发展他的极重要概念很有价值，我们却 
绝没有必要去附和它。的确，图灵在把机械过程的含义弄精确时，向我们展示出存在一 
些完好定义的数学运算，在任何通常的意义上，都不能被称为机械的！图灵本人的这一 
方面工作现在可间接地为我们提供了他自己有关精神现象性质观点的漏洞。这个事实也 
许不无讽刺意味。然而，这不是我们此刻所关心的。我们首先要弄清图灵心目中的机械 
过程究竟是什么。 
  
　 
  
图灵概念 
  
　 
  
　　我们设想实现某种（可以有限地定义的）计算步骤的一台仪器。这样仪器会采取什 
么样的一般形式呢？我们必须准备理想化一些，而且不必为实用性过份担心：我们是真 
正地考虑一台数学上理想化的“机器”。我们要求该仪器具有有限（虽然也许非常大的 
）数目的不同可能态的分立集合。我们把这些称作仪器的内态。但是我们不限制该仪器 
在原则上要实现的计算的尺度。回顾一下上述的欧几里德算法。在原则上不存在被该算 
法作用的数的大小的限制。不管这些数有多大，算法或者一般计算步骤都是同样的。对 
于非常大的数，该步骤的确要用非常长的时间，而且需要在数量可观的“粗纸”上面进 
行实际的计算。但是不管这些数有多大，该算法是指令的同一有限集合。 
  
　　这样，虽然我们仪器只有有限个内态，它却能够处理大小不受限制的输入。此外， 
为了计算应允许该仪器召来无限的外存空间（我们的“粗纸”）；而且能够产生大小不 
受限制的输出。由于该仪器只有有限数目的不同的内态，不能指望它把所有外部数据和 
所有自己计算的结果“内化”。相反地，它必须只考察那些立即处理的数据部分或者早 
先的计算，然后进行需要对它们进行的任何运算。也许可在外存空间把那个运算的相关 
结果记下来，然后以一种精确决定的方式进行下一个阶段的运算。正是输入、计算空间 
和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际 
上可真正建造的某种东西（见图2.1）。但这是极其关键的理想化。对于大多数实用目的 
而言，当代电脑技术的奇迹为我们提供了无限的电子存储仪器。 
  
　　事实上，在上述讨论中称为“外部的”存储空间的类型，可实际上被认为是现代电 
脑的内部工作的一部分。存储空间的某一确定部分是否被当作内部的或外部的，也许只 
是术语的问题。按照硬件和软件是划分“仪器”和“外部”的一种方法。内部可当成硬 
体，而外部为软体。我将不必拘泥于此，但是不管从那个角度看，当代电子电脑是图灵 
的理想化的极好近似。 
  
　 
  
　　图灵是按照在上面作记号的“磁带”来描述其外部数据和存储空间的。一旦需要， 
仪器就会把该磁带召来“阅读”，而且作为其运算的一部分，磁带可前后移动。仪器可 
把记号放到需要的地方，可抹去旧的记号，允许同一磁带像外存（也就是“粗纸”）以 
及输入那样动作。因为在许多运算中，一个计算的中间结果起的作用正如同新的数据， 
所以事实上在“外存”和“输入”之间不做任何清楚的区分也许是有益的。我们记得在 
欧几里德算法中，不断地用计算不同阶段的结果去取代原先的输入（数A和B）。类似地 
，这同一磁带可被用作最后输出（也就是“答案”）。只要必须进行进一步的计算，该 
磁带就会穿过该仪器而不断地前后移动。当计算被最后完成时，仪器就停止，而计算的 
答案会在停于仪器一边的磁带的部分上显示出来。为了确定起见，我们假定，答案总是 
在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。 
  
　　让我们有限的仪器前后移动一条潜在地无穷长的磁带，我自己觉得有点不舒服。不 
管其材料是多么轻，移动无限长的磁带是非常困难的！相反地，我宁愿把磁带设想成代 
表某一外部环境，我们有限的仪器可以通过这环境进行移动。（当然用现代电子学，既 
不需要“磁带”也不需要“仪器”作实际的、在通常物理意义上的“运动”，但是这种 
“运动”是一种描述事体的便利方法。）依此观点，该仪器完全是从这个环境接受它的 
输入。它把环境当成它的“粗纸”。最后将其输出在这同一个环境中写出。 
  
　　在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两个方向上都是 
无限的。在磁带的每一方格中或者是空白的或者包含有一个单独的记号①。我们可利用 
有记号或者没有记号的方格来阐释，我们的环境（也就是磁带）可允许被细分并按照分 
立（和连续相反的）元素来描述。如果希望仪器以一种可靠并绝对确定的方式工作。这 
似乎是合情理的要做的事。然而，我们允许该“环境”是（潜在地）无限的，把这作为 
我们使用的数学理想化的特征。但是，在任何特殊的情形下，输入、计算和输出必须总 
是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该有有限数目的实在的 
记号。磁带在每一个方向的一定点以外必须是空白的。 
  
　　我们用符号“0”来表示空白方格，用符号“1”来代表记号方格，例如： 
  
  
  
　　我们要求该仪器“读”此磁带，并假定它在一个时刻读一个方格，在每一步运算后 
向右或向左移动一个方格。这里没有损失任何涉及到的一般性。可以容易地由另一台一 
次只读和移动一个方格的仪器去仿照一台一次可读n个方格或者一次可移动k个方格的仪 
器。k方格的移动可由一个方格的k次移动来积累，而存储一个方格上的n种记号的行为正 
和一次读n个方格一样。 
  
　　这样的一台仪器在细节上可做什么呢？什么是我们描述成“机械的”东西作用的最 
一般方式呢？我们记得该仪器的内态在数目上是有限的。除了这种有限性之外，我们所 
需要知道的一切是该仪器的行为完全被其内态和输入所确定。我们已把输入简化成只是 
两个符号“0”或“1”之中的一个。仪器的初态和这一输入一给定，它就完全确定地运 
行；它把自己的内态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符 
号0或1来取代它刚读过的0或1；它向右或向左移动一个方格；最后它决定是继续还是终 
止计算并停机。 
  
　　为了以明白的方式定义该仪器的运算，我们首先，譬如讲用标号0，1，2，3，4，5 
，……，来为不同的内态编号；那么，用一张显明的代换表可以完全指定该仪器或图灵 
机的运行，譬如： 
  
　　00→00R 
  
　　01→131L 
  
　　10→651R 
  
　　11→10R 
  
　　20→01R STOP 
  
　　21→661L 
  
　　30→370R 
  
　　·· 
  
　　·· 
  
　　·· 
  
　　2100→31 
  
　　·· 
  
　　·· 
  
　　·· 
  
　　2580→00R.STOP 
  
　　2590→971R 
  
　　2591→00R.STOP 
  
　　箭头左边的大写的数字是仪器在阅读过程中磁带上的符号，仪器用右边中间的大写 
的数字来取代之。R告诉我们仪器要向右移动一个方格，而L告诉我们它要向左移动一个 
方格。（如果，正如图灵原先描述的那样，我们认为磁带而不是仪器在移动，那么我们 
必须将R解释成把磁带向左移动一个方格，而L为向右移动一个方格。）词STOP表示计算 
已经完成而且机器就要停止。特别是，第二条指令01→131L告诉我们，如果仪器内态为0 
而在磁带上读到1，则它应改变到内态13，不改变磁带上的1，并沿着磁带向左移一格。 
最后一条指令2591→00R.STOP告诉我们，如果仪器处于态259而且在磁带上读到1，那么 
它应被改变为态0，在磁带上抹去1而产生0，沿着磁带向右移一格，然后终止计算。 
  
　　如果我们只用由0到1构成的符号，而不用数字0，1，2，3，4，5……来为内态编号 
的话，则就和上述磁带上记号的表示更一致。如果我们有选择的话，可简单地用一串n个 
1来标号态n，但这是低效率的。相反地，我们使用现在人们很熟悉的二进位记数系统： 
  
　　0→0， 
  
　　1→1， 
  
　　2→10， 
  
　　3→11， 
  
　　4→100， 
  
　　5→101， 
  
　　6→110， 
  
　　7→111， 
  
　　8→1000， 
  
　　9→1001， 
  
　　10→1010， 
  
　　11→1011， 
  
　　12→1100，等等 
  
　　正如在标准的（十进位）记数中一样，这里最右边的数字代表“个位”，但是紧在 
它前面的位数代表“二”而不是“十”。再前面的位数代表“四”而不是“百”，更前 
面的是“八”而不是“千”等等。随着我们向左移动，每一接续的位数的值为接续的二 
的幂：1，2，4（=2×2），8（=2×2×2），16（=2×2×2×2），32（=2×2×2×2×2 
）等等。（为了将来的其他目的，我们有时发现用二和十以外的基来表示自然数是有助 
的：例如基数为三，则十进位数64就可被写成2101，现在每一位数都为三的幂：64=（2 
×33）+32+1；参阅第四章122页的脚注。） 
  
　　对上面图灵机的内态使用这种二进位记号，则原先的指令表便写成： 
  
　　00→00R 
  
　　0１→1101１R 
  
　　1０→1000001１L 
  
　　1１→1０R 
  
　　10０→0１STOPR 
  
　　10１→1000010１L 
  
　　11０→100101０R 
  
　　·· 
  
　　·· 
  
　　·· 
  
　　11010010０→11１L 
  
　　·· 
  
　　·· 
  
　　·· 
  
　　·· 
  
　　100000010１→0０STOP 
  
　　100000011０→1100001１R 
  
　　100000011１→0０STOP 
  
　　我还在上面把R.STOP简写成STOP，这是由于可以假定L.STOP从来不会发生，以使得 
计算的最后一步结果，作为答案的部分，总是显示在仪器的左边。 
  
　　现在假定我们的仪器处于由二进位序列1010010代表的特殊内态中，它处于计算的过 
程中，第43页给出了它的磁带，而且我们利用指令11010010０→11１L； 
  
　 
  
　　在磁带上被读的特殊位数（这里是位数“０”）由一个更大写的数字指示，符号串 
的左边表示内态。在由上面（我多多少少是随机造出的）部分地指定的图灵机例子中， 
读到的“０”会被“1”所取代，而内态变成‘11’，然后仪器向左移动一格： 
  
　 
  
　　该仪器现在已准备好读另一个数字，它又是“０”。根据该表，它现在不改变这个 
“０”，但是其内态由“100101”所取代，而且沿着磁带向右移回一格。现在它读到“ 
１”，而在表的下面某处又有如何进一步取代内态的指令，告诉它是否改变所读到的数 
，并向那个方向沿着磁带移动。它就用这种方式不断继续下去，直到达到STOP为止，在 
该处（在它向右再移一格之后）我们可以想象听到一声铃响，警告机器操作员计算完毕 
。 
  
　　我们将假定机器总是从内态“0”开始，而且在阅读机左边的磁带原先是空白的。所 
有指令和数据都是在右边输进去。正如早先提到的，被提供的这些信息总是采用０和１ 
的有限串的形式，后面跟的是空白带（也就是０）。当机器达到STOP时，计算的结果就 
出现在阅读机左边的磁带上。 
  
　　由于我们希望能把数字数据当作输入的一部分，这样就需要有一种描述作为输入部 
分的通常的数（我这里是说自然数0，1，2，3，4，…）的方法。一种方法可以是简单地 
利用一串n个1代表数n（尽管这会给我们带来和自然数0相关的困难）： 
  
　　1→1，2→11，3→111，4→1111，5→11111，等等。 
  
　　这一初等的记数系统（相当非逻辑地）被称作一进位系统。那么符号‘O’可用作不 
同的数之间的分隔手段。这种把数分隔开的手段是重要的，这是由于许多算法要作用到 
数的集合，而不仅仅是一个数上面。例如，对于欧几里德算法，我们的仪器要作用到一 
对数A和B上面。图灵机可以很容易地写下执行该算法的程序。作为一个练习，某些勤奋 
的读者也许介意去验证下面的一台图灵机（我将称它为EUC）的显明的描述，当应用到一 
对由０分隔的一进位数时，的确会执行欧几里德算法： 
  
　　0０→0０R，0１→1１L，1０→10１R，1１→1１L，10０→1010０R，10１→11０R， 
11０→100０R，11１→11１R，100０→100０R，100１→101０R，101０→111０L，101１ 
→110１L，110０→110０L，110１→1１L，111０→111０L，111１→1000１L，1000０→ 
1001０L，1000１→1000１L，1001０→10０R，1001１→1１L，1010０→0０STOP， 1010 
１→1010１R。 
  
　　然而，任何读者在进行此事之前，从某种简单得多的东西，譬如图灵机UN+1开始将 
更为明智： 
  
　　0０→0０R，0１→1１R，1０→0１STOP，1１→0１R。 
  
　　它简单地把一加到一个一进位数上。为了检查UN+1刚好做到这点，让我们想象，譬 
如讲把它应用到代表数4的磁带上去： 
  
　　…０００００１１１１０００００…。 
  
　　我们使仪器在开始时从某处向左为一些1。它处于内态０并且读到0。根据第一条指 
令，它仍保留为０，向右移动一格，而且停在内态0上，在它遇到第一个1之前，它不断 
地这么进行并向右移动。然后第二条指令开始作用：它把1留下来不变并且再向右移动， 
但是现在处于内态１上。按照第四条指令，它停在内态1上，不改变这些1，一直向右移 
动，一直达到跟在这些１后面的第一个０为止。第三条指令接着告诉它把那个０改变成 
１，向右再移一步（记住STOP是表示R，STOP），然后停机。这样，另一个１已经加到这 
一串１上。正如所要求的，我们例子中的4已经变成了5。 
  
　　作为更费神的练习，人们可以验证，下面所定义的机器UN×2，正如它所希望的，把 
一个一进位数加倍： 
  
　　0０→0０R，0１→1０R，1０→10１L，1１→1１R，10０→11０R10１→100０R，11 
０→0１STOP，11１→11１R，100０→101１L，100１→100１R，101０→10１L，101１→ 
101１L。 
  
　　在EUC的情形、为了得到有关的概念，人们可用一些明显的数对譬如6和8来试验。正 
如以前一样，阅读机处于态0，并且初始时处在左边，而现在磁带一开始的记号是这样子 
的： 
  
　　…０００００００００００１１１１１１０１１１１１１１１０００００… 
  
　　在许多步之后，图灵机停止，我们得到了具有如下记号的磁带： 
  
　　…００００１１００００００００００００… 
  
　　而阅读机处于这些非零位数的右边。这样，所需的最大公约数正是所需要的（正确 
的）2。 
  
　　要完全解释为何EUC（或者UN×2）在实际上完成所预想的，牵涉到许多微妙之处， 
而且解释本身比机器更复杂，这是电脑程序的通常特征！（为了完全理解一个算法步骤 
为何能做到所预想的，牵涉到洞察。“洞察”本身是算法的吗？这是一个对我们以后颇 
为重要的问题。）我不想在这里为EUC或UN×2提供解释。真正做过检验的读者会发现， 
为了在所需的方案中把事情表达得更精密一些，我自作主张地对欧几里德算法作了一些 
不重要的变通。EUC的描述仍然有些复杂，对于11种不同的内态包含有22条基本指令，大 
部分复杂性是纯粹组织形式的。例如，可以看到在22条指令中，只有三条真正涉及到在 
磁带上改变记号！（甚至对于UN×2用了12条指令，其中只有一半涉及到改变记号。） 
  
　 
  
数据的二进位码 
  
　 
  
　　用一进位系统表示大数极端无效率。正如早先描述的，我们将相应地用二进位计数 
系统。然而，不能直接地把磁带当作二进位数来读。如果这样做的话，就没有办法告知 
一个数的二进位表示何时结束，以及无限个０的序列是否代表右端开始的空白。我们需 
要某种终结一个数的二进位描述的记号。此外，我们还经常要输进几个数，正如欧几里 
德算法需要一对数2那样。问题在于，我们不能把数之间的间隔和作为单独的一个数的二 
进位表示中的一部分的０或一串０区分开来。此外，我们或许在输入磁带中包括所有种 
类复杂的指令和数。为了克服这些困难，让我们采用一种我称之为收缩的步骤。按照该 
步骤，任何一串０或一串１（共有有限个）不是简单地被当作二进位数来读，而是用一 
串0，1，2，3等来取代。其作法是，第二个序列的每一数字就是在第一个序列中的连续 
的０之间的１的个数。例如序列 
  
　　０１０００１０１１０１０１０１１０１０００１１１０１０１０１１１１００１ 
１０ 
  
　　就可被取代成： 
  
　 
  
　　我们现在可以把数2，3，4，…当作某种记号或指令来读。让我们把2简单地当作表 
示两个数之间间隔的“逗号”，而根据我们的愿望，3，4，5，…可以代表各种有兴趣的 
指令或记号，诸如“负号”、“加”、“乘”“到具有下面号码的位置”，“递归进行 
前面的运算如下面数目那么多次”等等。我们现在有了由更高的数分开的各种０和１的 
串。后者代表写成二进位的通常的数。这样上面可读成（“逗号”为2）： 
  
　　（二进位数１００１）逗号（二进位数11）逗号……。 
  
　　使用标准的阿拉伯记号“9”，“3”，“4”，“0”来写相应的二进位１００１， 
１１，１００，０，我们就得到整个序列： 
  
　　9，3，4（指令3）3（指令4）0， 
  
　　特别是，这一步骤给了我们一种简单地利用在结尾处逗号终结描述一个数的手段（ 
并因此把它和在右边的无限长的空白带区分开来）。此外，它还使我们能对以二进位记 
号写成０和丨的单独序列的自然数的任何有限序列编码。让我们看看在一特定情形下这 
是怎么进行的。例如，考虑序列 
  
　　5，13，0，1，1，4 
  
　　在二进位记号中这是 
  
　　１０１，１１０１，０，１，１，１００， 
  
　　它可用扩展（也就是和上面收缩相反）的步骤在磁带上编码成…００００１００１ 
０１１０１０１００１０１１００１１０１０１１０１０ 
  
１１０１０００１１０００…为了直截了当地得到这个码，我们可在原先的二进位数序 
列上作如下代换： 
  
 　。啊� 
  
 　。薄保� 
  
　　，→１１０ 
  
　　然后在两端加上无限个０。如果我们把它列出，就能更清楚地看出，如何把这个应 
用到上面的磁带上： 
  
　　００００１００１０１１０１０１００１０１１００１１０１０１１０１ 
  
０１１０１０００１１０００ 
  
　　我将把这种数（的集合）的记号称为扩展二进位记号。（这样，例如13的扩展二进 
位形式为１０１００１０） 
  
　　关于这种编码还有最后一点必须提及。这只不过是个技巧，但是为了完备起见是需 
要的3。在自然数的二进位（或十进位）表示中处于表式最左端的0是不“算”的，它通 
常可被略去，这里有些多余。例如００１１００１０和１１００１０是两个相同的二进 
位数（而0050和50为相同的十进位数）。这一多余可适合于数0本身，它也可写成000或0 
0。一个空白的空间的确也应该逻辑地表示0！在通常的记号下这会导致巨大的混淆，但 
是它和上面刚描述的记号可相安无事。这样，在两个逗号之间的0可只写成两个连在一起 
的逗号（，，），它在磁带上被编码成两对由单独的０隔开的１１： 
  
　　…００１１０１１００… 
  
　　这样，上面的六个数的集合也可用二进位记号写成 
  
　　１０１，１１０１，，１，１，１００， 
  
　　而且在磁带上可以扩展的二进位方式编码成 
  
　　…００００１００１０１１０１０１００１０１１０１１０１０１１０１０１１０ 
  
１０００１１０００…（有一个０已从我们以前的序列中略去）。 
  
　　现在我们可以考虑让一台图灵机，譬如讲欧几里德算法，把它应用到以扩展二进位 
记号写出的一对数上。例如，这一对数是我们早先考虑的6，8，不用以前用的 
  
　　…０００００００００００１１１１１１０１１１１１１１１０００００… 
  
　　而考虑6和8的二进位表示，也就是分别为110和1000。这一对为6，8，在二进位记号 
也就是１１０，１０００扩展后在磁带上编码成 
  
　　…０００００１０１００１１０１００００１１００００００… 
  
　　对于这一对特殊的数，并没有比一进位形式更紧凑。然而，譬如说我们取（十进位 
数）1583169和8610。在二进位记号中它们是 
  
　　１１０００００１０１００００１０００００１，１００００１１０１０００１０ 
， 
  
　　这样，我们在磁带上把这一对编码成 
  
　　…００１０１００００００１００１０００００１００００００１０１１０１０ 
  
００００１０１００１００００１００１１０… 
  
　　只要用一行就可将其全部写出，而如果用一进位记号的话，表示“1583169，8610” 
的磁带用这一整本书都写不下。 
  
　　当数用扩展二进位记号表示时，一台执行欧几里德算法的图灵机，如果需要的话， 
可以简单地把适当的一对在一进位和扩展二进位之间互相翻译的子程序算法接到EUC上去 
而得到。然而，由于一进位计数系统的无效率仍在“内部”存在，并且在仪器的迟缓以 
及需要大量的外部“粗纸”（它是磁带的右手部分）方面表现出来，实际上这是极其无 
效率的。可以给出全部用扩展二进位运算的、更有效率的、欧几里德算法的图灵机，但 
是它在这里对我们并无特别启发之处。 
  
　　相反地，为了阐明如何使一台图灵机能对扩展二进位数运算，让我们尝试某种比欧 
几里德算法简单得多的东西，即是对一个自然数加一的过程。这可由（我称之为XN+1的 
）图灵机来执行： 
  
　　0０→0０R，0１→1１R，1０→0０R，1１→10１R， 
  
　　10０→11０L，10１→10１R，11０→0１STOP，11１→100０L， 
  
　　100０→101１L，100１→100１L，101０→110０R，101１→10１R， 
  
　　110１→111１R，111０→11１R，111１→111０R， 
  
　　某些勤奋的读者可把它应用到，譬如讲数167上去，以再次验证这一台图灵机在实际 
上做到了所预想的。这一个数的二进位表示可由下面的磁带给出： 
  
　　…００００１００１０００１０１０１０１１０００… 
  
　　为了把一加到这个二进位数上，我们简单地找到最后的那个0，并把它改成1，然而 
用0来取代所有跟在后面的1。例如167+1=168在二进位记号下写成 
  
　　１０１００１１１+１=１０１０１０００. 
  
　　这样，我们的“加一”图灵机应把前面的磁带用 
  
　　…００００１００１００１００００１１０００００… 
  
　　来取代，它的确做到了这一点。 
  
　　我们注意到，甚至这种简单加一的非常基本的运算在用这种记号时都会显得有些复 
杂，它使用了十五条指令和八种不同的内态！由于在一进位系统中“加一”只是把1的串 
再延长一个而已，事情当然是简单得多。所以我们的机器UN+1更为基本，这一点也不奇 
怪。然而，对于非常大的数，由于所需的磁带非同寻常地长，UN+1就会极慢。而用更紧 
凑的扩展二进位记号运算的更复杂的机器XN+1就会更好。 
  
　　作为旁白，我愿意指出对于扩展二进位比一进位图灵机显得更简单的一个运算，这 
就是乘二。在这里由 
  
　　0０→0０R，0１→1０R，1０→0１R，1１→10０R，10０→11１R，11０→0１STOP， 
  
　　给出的图灵机XN×2能在扩展的二进位上实现这个运算，而前面描述的相应于一进位 
的机器UN×2就要复杂得多！ 
  
　　我们从这里得到了，关于图灵机在非常基础水平上可做到的一些事情的概念。正如 
预料得到的，当进行某些复杂的运算时，它们会变得极为复杂。这种仪器的终极能力是 
什么呢？让我们在下面讨论这一个问题。 
  
　 
  
撤屈-----图灵主题 
  
　 
  
　　人们一旦对建造简单的图灵机稍有一些熟悉，下面这些事实就很容易使他们感到满 
意。特殊的图灵机的确能执行各种基本的算术运算，诸如把两个数加到一起，或把它们 
相乘，或求一个数的到另一个数的方次。显明 
  
　　　 
  
　　提供其结果为一对自然数的运算，譬如带有余数的除法，或者其结果为任意大数目 
的数的有限集合。此外，可以这样地建造图灵机，即预先没有必要指定它要做何种运算 
，其运算的指令由磁带提供。需要实行的特定运算也许在某一阶段依赖于该机器在某个 
更早阶段的需要进行的某个计算的结果。（“如果那个计算的结果比某数大，则做这个 
；否则就做那个。”）一旦人们理解到，他可制造实现算术或简单的逻辑运算的图灵机 
，则很容易想象如何使之进行具有算法性质的更复杂的任务。在他们捣弄了好一阵之后 
，很容易坚信，这类机器的确能实行不管什么样的机械运算！在数学上，可以很合情合 
理地把机械运算定义为可被这样的一台机器所执行的运算。数学家用名词“算法”以及 
形容词“可计算的”、“递归的”和“有效的”来表示能由这类理论机器－－图灵机实 
行的机械运算。一个步骤只要是足够清楚并且机械的，则可合理地相信能找到一台执行 
它的图灵机。这正是我们（也就是图灵）引进图灵机概念本身的初步讨论的全部要点。 
  
　　另一方面，人们仍会感到，这些机器的设计不必这么局限。初看起来，只允许仪器 
在一个时刻读一个二进位位数（０或１），并且一次沿着一个单独的一维磁带只移动一 
格似乎是限制。为什么不允许大数目或相互联结的阅读机一下子跑过四条或五条甚至一 
千条分开的磁带呢？为什么不允许０和１的方格的整个平面（或者甚至一个三维的阵列 
），而坚持只用一维的磁带呢？为什么不允许从某种更复杂的计数系统或字母来的其他 
符号呢？事实上，虽然这些改变中的一些会对运算的经济性造成一定程度的不同（正如 
允许用多于一条的磁带一定会是这种情形那样），但是所有这一切都不会对我们在原则 
上要得到的东西造成丝毫的影响。即使我们在所有这些方面一下子推广该定义，这种归 
于“算法”的名下（或“计算”、“有效步骤”或“递归运算”）所实现的运算种类刚 
好和推广以前的完全相同！ 
  
　　我们可以看到，没有必要有多余一条的磁带。只要该仪器需要时总能在给定的磁带 
不断地找到新的空白。为此，也许必须不断地把数据从磁带的一处往另一处调度。这也 
许是“低效率的”，但是它不限制在原则上可以得到的极限4。类似地，利用多于一台并 
行动作的图灵机－－这在近年由于和想更接近地仿照人脑试图相关联而变得很时髦---- 
不能在原则上得到任何新东西（虽然在某种情形下可改善动作的速度）。拥有两台分开 
的、不直接相互联络的仪器并不比两台相互联络的得到更多，而且如果它们联络，则实 
际上只不过是一台单独的仪器！ 
  
　　关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带代表“环境” 
，也许宁愿把它当作一个平面或许一个三维空间，而不当作一维磁带。一个平面似乎比 
一维磁带更接近于一个“流程图”（正如在上面对欧几里德算法运算的描述）所需要的 
①。然而，在原则上没有困难以“一维的”形式（也就是利用流程图的通常术语来描述 
）写出流程图的运行。在二维平面上显示只是为了我们的便利和容易理解，它对原则上 
能得到的并没造成什么影响。人们总能把一个二维平面上甚至三维空间上的一个记号或 
对象的地址，直截了当地在一维磁带上编码。（事实上，使用一个二维平面完全等效于 
用两根磁带。这两根磁带提供为在二维平面上指明一点所需的两个“座标”；正如三根 
磁带可作为一个三维空间的一点的“座标”一样。）这一维的编码再次可能为“低效率 
的”，但是它在原则上不限制我们的目标。 
  
　　尽管所有这一切，我们仍然可心询问，图灵机的概念是否真的和我们希望叫做“机 
械的”每一逻辑或数学运算相统一。在图灵写他的开创性文章的时候，这一点比今天模 
糊得多，所以他觉得有必要把情形解释得更清楚一些。图灵的严密论证从以下事实得到 
了额外的支持，这就是美国逻辑学家阿伦佐·撤屈（在S.C.克利涅的协助下）完全独立 
地（并实际上稍早一些）提出了一种方案，也是旨在解决希尔伯特的判决问题的拉姆达 
计算。尽管它不如图灵的那么明显地为一种完全广泛的机械的方案，但在数学结构上的 
极端经济性方面有些优点。（我将在本章的结尾描述撤屈的杰出的计算。）还存在其他 
一些解决希尔伯特问题的和图灵相独立的设想（见甘迪1988），尤其是波兰��美 
国逻辑学家爱弥尔·波斯特的设想（比图灵稍晚些，但其思想和图灵比和撤屈更相像许 
多）。所有这些方案很快就被证明是完全等效的。这就给现在称作撤屈－图灵主题的观 
点增加了许多份量，即图灵机（或等效的）概念实际在数学上定义了我们认为是算法（ 
或有效、或递归、或机械的）步骤的东西。现在，高速电脑已变成我们生活中如此熟悉 
的部分，很少人似乎觉得有必要去问这些主题的原始形式。相反地，已有不少人转去注 
意真正的物理系统（假定包括人脑）��精确服从物理定律的东西－－是否能够实 
行比图灵机更多、更少或刚好一样多的逻辑和数学运算。我本人是非常喜欢撤屈－－图 
灵主题的原先的数学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本 
书主要关注的另外一个单独的问题。 
  
　 
  
不同于自然数的数 
  
　 
  
　　我们在上述的讨论中考虑了自然数的运算，并且注意到了这一显著的事实，即尽管 
每台图灵机只有固定的有限数目的不同内态，它却可能处理任意大小的自然数。然而， 
人们经常需要使用比这更复杂的其他种类的数，诸如负数、分数或无理数。图灵机可以 
容易地处理负数和分数（例如像-597/26），而且我们可取任意大的分母和分子。我们所 
要做的全部是对“-”和“/”作适当的编码。这可容易地利用早先描述的扩展二进位记 
号做到（例如，“3”表示“-”以及“4”表示“/”，它们分别在扩展二进位记号中编 
码成1110和11110）。人们就是这样地按照自然数的有限集合来处理负数和分数的。这样 
，就可计算性的一般问题而言，它们没有告诉我们什么新的东西。 
  
　　类似地，由于长度不受限制的有限小数表式仅仅是分数的特殊情形，它们并没给我 
们带来什么新问题。例如，无理数π的由3.14159265给出的有限小数近似，简单地就是 
分数314159265/100000000。然而，无限小数表式，譬如完全无限展开 
  
　　π=3.14159265358979… 
  
　　出现了一定的困难。严格地讲，无论是图灵机的输入或者输出都不是无限小数。人 
们也许会想到，我们可以找到一台图灵机，在其输出磁带上产生由π的小数展开的、所 
有的一个接一个位数3，1，4，1，5，9，…。我们就简单地让机器一直开下去好了。但 
这对于一台图灵机来讲，是不允许的。我们必须等待机器停了以后（铃声响过！）才允 
许去检查输出。只要机器还没有到达停止命令，其输出就可能要遭受到改变，所以不能 
对它信任。另一方面，在它到达停止时，其输出必须是有限的。 
  
　　然而，存在一种合法地使图灵机以与此非常类似的方法，一个位数跟着另一个位数 
产生位数的步骤。如果我们希望产生一个数，譬如讲π的无限小数展开，我们可以让一 
台图灵机作用于0上以产生整数部分了；然后使机器作用到1上，产生第一小数位1；然后 
使其作用于2上，产生第二小数位4；然后作用于3上，产生1，这样不断地下去。事实上 
，一定存在在这个意义上产生π的全部小数展开的图灵机，尽管要把它明显地造出 
  
  
  
　　=1.414213562…。然而，正如在下一章将要看到的，人们发现有些无理数（非常引 
人注目地）根本不能由任何图灵机产生。能以这种方式产生的数叫作可计算的（图灵193 
7）。那些不能的（实际上是绝大多数！）是叫作不可计算的。我们将在后面的章节中回 
到这件事体及有关的问题上来。按照物理理论，用可计算的数学结构能否足够地描述实 
在的物理对象（也就是人脑），是我们要关心的问题。 
  
　　一般地讲，可计算性是数学中的一个重要问题。人们不应该只将其当成只适合于这 
类数的事体。人们可有直接作用于诸如代数或三角的数学公式上的图灵机，或可进行微 
积分的形式运算的图灵机。人们所需的一切是某种准确地把所有涉及的数学符号编码成0 
和1序列的形式，然后再利用图灵机的概念。这毕竟是图灵在着手解决判决问题时心里所 
想的，即寻求回答具有一般性质的数学问题的算法步骤。我们将很快地回到这上面来。 
  
　 
  
普适图灵机 
  
　 
  
　　我还未描述普适图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分 
复杂。它的基本思想是把任意一台图灵机T的指令的表编码成在磁带上表示成0和1的串。 
然后这段磁带被当作某一台特殊的被称作普适图灵机U的输入的开始部分，接着这台机器 
正如T所要进行的那样，作用于输入的余下部分。普适图灵机是万有的模仿者。“磁带” 
的开始部分赋予该普适机器U需要用以准确模拟任何给定机器T的全部信息！ 
  
　　为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方式。考虑定义 
某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我们必须按照某种准确的方案 
把这表编码成0和1的串。我们可借助于以前采用的“收缩”步骤来办到。因为，如果我 
们用数2，3，4，5和6来分别代表符号R、L、STOP、箭头（→）以及逗点，那么我们就可 
以用１１０、１１１０、１１１１０、１１１１１０以及１１１１１１０的收缩把它们 
编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成０和１０的位数0 
和１。由于在该图灵机的表中，在二进位计数的结尾大写的数的位置足以把大写的０和 
１从其他小写的阿拉伯数字中区分开来，所以我们不需要用不同的记号。这样，110１将 
被读成二进位数1101，而在磁带上被编码成１０１００１０。特别是，0０读作00，它可 
毫不含糊地被编码成０，或者作为被完全省略的符号。实际上我们可以不必对任何箭头 
或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些符号必须是什么 
。尽管在采用这个步骤时，在必要之处要提供一些额外的“哑”指令，以保证在这个顺 
序中没有缝隙。这样的做法具有相当好的经济性。（例如，图灵机XN+1没有告诉我们对1 
10０要做什么的命令，这是因为这条指令在机器运行时从不发生，所以我们应该插入一 
条“哑”指令，譬如讲110０→0０R，它可合并到表中而不改变任何东西。类似地，我们 
应该把10１→0０R插入到XN×2中去。）若没有这些“哑的”，表中后面的指令的编码就 
会被糟蹋了。因为在结尾处的符号L或R足以把一条指令和另一条隔开，所以我们在每一 
指令中实际不需要逗号。因此，我们采用下面的编码： 
  
　　０表示0或０，１０表示1或１，１１０表示R，１１１０表示L，１１１１０表示sto 
p。 
  
　　作为一个例子，让我们为图灵机XN+1编码（插入指令110０→0０R）。在去掉箭头和 
在它们紧前面的位数以及逗号之后，我们得到 
  
　　0０R 1１R 0０R 10１R 11０L 10１R 0１STOP 
  
　　100０L 101１L 100１L110０R10１R0０R111１R 
  
　　11１R 111０R 
  
　　为了和早先说的相一致，我们可以去掉每一个００，并把每 
  
一个01简单地用1来取代，这样得到 
  
　　R1１RR10１R11０L10１R１STOP100０L101１L1 
  
　　00１L110０R10１RR111１R11１R111０R 
  
　　如下是在磁带上的相应的码： 
  
　　１１０１０１０１１０１１０１００１０１１０１０１００１ 
  
１１０１００１０１１０１０１１１１０１００００１１１０１０ 
  
０１０１０１１１０１０００１０１１１０１０１０００１１０１ 
  
００１０１１０１１０１０１０１０１０１１０１０１０１０１１ 
  
０１０１０１００１１０ 
  
　　我们总是可以把开始的１１０（以及它之前的无限的空白磁带）删去。由于它表示0 
０R，这代表开头的指令0０→0０R。而我已隐含地把它当作所有图灵机共有的。这样仪 
器可从磁带记号左边任意远的地方向右跑到第一个记号为止。而且，由于所有图灵机都 
应该把它们的描述用最后的１１０结束（因为它们所有都用R、L或STOP来结束），所以 
我们也可把它（以及假想跟在后面的０的无限序列）删去。这可以算作两个小节约。所 
得到的二进位数是该图灵机的号码，它在XN+1的情况下为： 
  
　　１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０ 
  
１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０ 
  
１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１１ 
  
０１０１０１００。 
  
　　这一特殊的数在标准十进位记号下为 
  
　　450813704461563958982113775643437908。 
  
　　我们有时不严格地把号码为n的图灵机称为第n台图灵机，并用Tn来表示。这样，XN+ 
1是第450813704461563958982113775643437908台图灵机！ 
  
　　我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如此平凡的（在 
扩展二进位记号上）对自然数加一的运算，这真使人印象深刻！（尽管在我的编码中还 
可以有很少的改善余地，但我认为自己进行得相当有效率。）实际存在某些更低号码的 
有趣的图灵机。例如，UN+1的二进位号码为 
  
　　１０１０１１０１０１１１１０１０１０ 
  
　　它只是十进位制的177642！这样，只不过是把一个附加的1加到序列1的尾巴上的特 
别平凡的图灵机UN+1是第177642台图灵机。为了好奇的原因，我们可以注意在任一种进 
位制中“乘二”是在图灵机表中这两个号码之间的某处。我们找到XN×2的号码为103897 
28107，而UN×2的号码为1492923420919872026917547669。 
  
　　人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数根本不是可工 
作的图灵机的号码。现在我们根据这种编号把最先的十三台图灵机列出来： 
  
　　T0：0０→0０R，0１→0０R， 
  
　　T1：0０→0０R，0１→0０L， 
  
　　T2：0０→0０R，0１→0１R， 
  
　　T3：0０→0０R，0１→0０STOP， 
  
　　T4：0０→0０R，0１→1０R， 
  
　　T5：0０→0０R，0１→0１L， 
  
　　T6：0０→0０R，0１→0０R，1０→0０R， 
  
　　T7：0０→0０R，0１→？？？， 
  
　　T8：0０→0０R，0１→10０R， 
  
　　T9：0０→0０R，0１→1０L， 
  
　　T10：0０→0０R，0１→1１R， 
  
　　T11：0０→0０R，0１→0１STOP， 
  
　　T12：0０→0０R，0１→0０R，1０→0０R。 
  
　　其中，T0简单地就是向右移动并且抹去它所遇到的每一件东西，永不停止并永不往 
回退。机器T1最终得到同样的效应。但它是以更笨拙的方法，在它抹去磁带上的每个记 
号后再往后跳回。机器T2也和机器T0一样无限地向右移动，但是它更有礼貌，简单地让 
磁带上的每一件东西原封不动。由于它们中没有一台会停下，所以没有一台可以合格地 
被称为图灵机。T3是第一台可敬的机器。它的确是在改变第一个（最左边）的１为０后 
便谦虚地停止。 
  
　　T4遭遇了严重的问题。它在磁带上找到第一个１后就进入了一个没有列表的内态， 
所以它没有下一步要做什么的指令。T8、T9和T10遇到同样的问题。T7的困难甚至更基本 
。把它编码的０和１的串涉及到五个接续的１的序列：１１０１１１１１０。对于这种 
序列不存在任何解释，所以只要它在磁带上发现第一个1就被绊住。（我把T7或其他任何 
机器Tn，它的n的二进位展开包含多于四个１的序列称为不是正确指明的。）机器T5、T6 
和T12遭遇到和T0、T1和T2类似的问题。它们简单地、无限地、永远不停地跑下去。所有 
T0、T1、T2、T4、T5、T6、T7、78、T9、T10和T12都是伪品！只有T3和T11是可工作的， 
但不是非常有趣的图灵机。T11甚至比T3更谦虚，它在第一次遇到1时就停止，并且没有 
改变任何东西！ 
  
　　我们应该注意到，在表中还有一个多余。由于T6和T12从未进入内态1，机器T12和T6 
等同，并在行为上和T0等同。我们既不必为这个多余，也不必为表中的图灵机伪品而烦 
恼。人们的确可以改善编码以摆脱许多伪品和大大减少重复。所有这些都是以使我们可 
怜的普适图灵机变得更复杂作为代价。普适图灵机必须把所读到的号码n解码并假装成图 
灵机Tn。如果我们可以把所有伪品（或者多余量）取走，这还是值得做的。但是，我们 
很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。 
  
　　例如，可方便地把具有 
  
　　…０００１１０１１１００１００００… 
  
　　接续记号的磁带解释成某个数字的二进位表示。我们记得０在两端会无限地继续下 
去，但是只有有限个１。我还假定１的数目为非零（也就是说至少有一个１）。我们可 
以选择去读在第一个和最后一个1（包括在内）之中的有限的符号串，在上述的情况是为 
一自然数的二进位写法 
  
　　１１０１１１００１， 
  
　　它在十进位表示中为441。然而，这一过程只能给我们奇数（其二进位表示以１结尾 
的数）。而我们要能表示所有的自然数。这样，我们采取移走最后的１的简单方案（这 
个１仅仅被当作表示这一程序的终止记号），而把余下来的当成二进位数来读5。因此， 
对于上述的例子，我们有二进位数 
  
　　１１０１１１００， 
  
　　它是十进位的220。这个步骤具有零也用磁带上的记号代表的好处，也就是 
  
　　…００００００１００００００… 
  
　　我们考虑图灵机Tn对我们从右边提供给它的磁带上（有限的）０和１的串的作用。 
根据上面给出的方案，可方便地把这串也考虑作某一个数，譬如m的二进位代表。我们假 
定，机器Tn在进行了一系列的步骤后最终到达停止（即到达STOP）。现在机器在左边产 
生的二进位数串是该计算的答案。让我们也以同样方式把这当作，譬如是p的二进位代表 
来读。我们把表达当第n台图灵机作用到m上时产生p的关系写成： 
  
　　Tn(m)=p。 
  
　　现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一对数n和m以得 
到数p的一个特别运算。（这样，若给定两个数n和m，视第n台图灵机对m作用的结果而得 
出p。）这一特别运算是一个完全算法的步骤。所以它可由一台特殊的图灵机U来执行。 
也就是说，U作用到一对(n，m)上产生p。由于机器U必须作用于n和m两者以产生单独结果 
p，我们需要某种把一对(n，m)编码到一条磁带上的方法。为此，我们可假定n以通常二 
进位记号写出并紧接着以序列１１１１１０终结。（我们记得，任一台正确指明的图灵 
机的二进位数都是仅仅由０，１０，１１０，１１１０和１１１１０组成的序列，因此 
它不包含比四个１更多的序列。这样，如果Tn是正确指明的机器，则１１１１１０的发 
生的确表明数n的描述已终结。）按照我们上面的规定，跟着它的每一件东西简单地是代 
表m的磁带（也就是，紧跟二进位数m的是１０００…）。这样，这第二个部分简单地就 
是Tn假设要作用的磁带。 
  
　　作为一个例子，如果我们取n=11和m=6当作U要作用的磁带，其记号序列为 
  
　　…０００１０１１１１１１１０１１０１００００… 
  
　　这是由以下组成的： 
  
　　…００００（开始的空白带） 
  
　　１０１１（11的二进位表示） 
  
　　１１１１１０（终结n） 
  
　　１１０…（6的二进位表示） 
  
　　１００００…（余下的磁带）。 
  
　　在Tn作用到m上的运算的每一接续的步骤，图灵机U要做的是去考察n的表达式中的接 
续数位的结构，以使得在m的数位（也就是Tn的磁带）上可进行适当的代换。在原则上（ 
虽然在实践中肯定很繁琐）不难看到人们实际如何建造这样的一台机器。它本身的指令 
表会简单地提供一种，在每一阶段读到被编码到数n中的“表”中，应用到m给出的磁带 
的位数时，合适元素的手段。肯定在m和n的数位之间要有许多前前后后的进退，其过程 
会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把它称为普适图灵机 
。把该机器对一对数n和m的作用表为U(n,m)，我们得到： 
  
　　U(n,m)=Tn(m)。 
  
　　这儿Tn是一台正确指明的图灵机6。当首先为U提供数n时，它准确地摸拟 
  
第n台图灵机！ 
  
　　因为U为一台图灵机，它自身也必须有一号码；也就是说，我们有 
  
　　U=Tu 
  
　　此处号码u待定。u究竟是多少呢？事实上我们可以准确地给出u=72448553353393175 
77198395039615711237952360672556559631108144 
  
7966065050594042410903104836136323593656444434583822268832787676 
  
2655614469281411771501784255170755408565768975334635694247848859 
  
7046934725739988582283827795294683460521061169835945938791885546 
  
3264409255255058205559894518907165374148960330967530204315536250 
  
3498452983232065158304766414213070881932971723415105698026273468 
  
6429921838172157333482823073453713421475059740345184372359593090 
  
6400243210773421788514927607975976344151230795863963544922691594 
  
7965461471134570014504816733756217257346452273105448298078496512 
  
6988788964569760906634204477989021914437932830019493570963921703 
  
9048332708825962013017737272027186259199144282754374223513556751 
  
3408422229988937441053430547104436869587640517812801943753081387 
  
06399427728231564252892375145654438990527807932411448261423572861 
  
93118332610656122755531810207511085337633806031082361675045635852 
  
16421486954234718742643754442879006248582709124042207653875426445 
  
41334517485662915742999095026230097337381377241621727477236102067 
  
86854002893566085696822620141982486216989026091309402985706001743 
  
00670086896759034473417412787425581201549366393899690581773859165 
  
40553567040928213322216314109787108145997866959970450968184190629 
  
94436560151454904880922084480034822492077304030431884298993931352 
  
66882349662101947161910701461968523192847482034495897709553561107 
  
02758174873332729667899879847328409819076485127263100174016678736 
  
34776058572450369644348979920344899974556624029374876688397514044 
  
51665707750060513883991668814072545544665222050724262392379211525 
  
31816251253630509317286314220040645713052758023076651833519956891 
  
39748137504926429605010013651980186945639498 
  
　　（或者至少是这等数量级的其他的可能性）。这个数无疑是极其巨大，但是我似乎 
没有办法使它变小许多。虽然我的图灵机编码步骤和号码指定是相当合理和简单的，但 
是在一台实际的普适图灵机的编码中仍然不可避免地导向这么大的一个数7。 
  
　　我曾说过，实际上所有现代通用电脑都是普适图灵机。我并不是说，这种电脑的逻 
辑设计必须在根本上和我刚刚给出的普适图灵机的描述非常相似。其要点可以简述为， 
首先为任一台普适图灵机提供一段适当的程序（输入磁带的开始部分）可使它摸拟任何 
图灵机的行为！在上面的描述中，程序简单地采取单独的数（数n）的形式。但是，其他 
的步骤也是可能的，图灵原先方案就有许多种变化。事实上，在我自己的描述中，已经 
有些偏离图灵的原型。但是对于我们当前目的，这些差别中没有一个是重要的。 
  
　 
  
希尔伯特问题的不可解性 
  
　 
  
　　我们现在回到当初图灵提出其观念的目的，即解决希尔伯特的范围广泛的判决问题 
：是否存在某种回答属于某一广泛的、但是定义得很好的集合的所有数学问题的机械步 
骤？图灵发现，他可以把这个问题重述成他的形式，即决定把第n台图灵机作用于数m时 
实际上是否会停止的问题。该问题被称作停机问题。很容易建造一个指令表使该机器对 
于任何数m不停。（例如，正如上面的n=1或2或任何别的在所有地方都没有STOP指令的情 
形）。也有许多指令表，不管给予什么数它总停（例如n=11）；有些机器对某些数停， 
但对其他的数不停。人们可以公正地讲，如果一个想象中的算法永远不停地算下去，则 
并没有什么用处。那根本不够格被称作算法。所以一个重要的问题是，决定Tn应用在m时 
是否真正地给出答案！如果它不能（也就是该计算不停止），则就把它写成 
  
　　Tn(m)=□。 
  
　　（在这记号中还包括了如下情形，即图灵机在某一阶段由于它找不到合适的告诉其 
下一步要做什么的指令而遇到麻烦，正如上面考虑的伪品机器T4和T7。还有不幸得很， 
我们粗看起来似乎成功的机器T3现在也必须被归于伪品：T3(m)=□，这是因为T3作用的 
结果总是空白带，而为使计算的结果可赋予一个数，在输出上至少有一个1！然而，由于 
机器T11产生了单独的1，所以它是合法的。这一输出是编号为0的磁带，所以对于一切m 
，我们都有T11(m)=0。） 
  
　　能够决定图灵机何时停止是数学中的一个重要问题。例如，考虑方程： 
  
　　(x+1)w+3+(y+1)w+3=(z+1)w+3。 
  
　　（如果专门的数学方程使你忧虑，不要退缩！这一方程只不过是作为一个例子，没 
有必要详细地理解它。）这一特殊的方程和数学中著名的或许是最著名的未解决的问题 
相关。该问题是：存在任何满足这方程的自然数集合w，x，y，z吗？这个著名的称作“ 
费马最后定理”的陈述被伟大的十七世纪法国数学家皮埃尔·德·费马(1601�1665) 
写在丢番都的《代数》一书空白的地方。费马宣布这方程永远不能被满足①8。虽然费马 
以律师作为职业（并且是笛卡尔的同时代人），他却是那个时代最优秀的数学家。他宣 
称得到了这一断言的“真正美妙的证明”，但那里的空白太小写不下。可惜迄今为止既 
没有人能够重新证明之，也没有人能找到任何和费马断言相反的例子①！ 
  
　　很清楚，在给定了四个数(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），Tn不是正确指定的，而且在磁带上记号11111 
0不足以把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)叫放在Tn对m作用之前而作到；然后 
只有如果H(n；m)=1时（也就是说，只有如果计算Tn(m)实际上给出一个答案时），我们 
才允许Tn作用到m上，而如果H(n；m)=0（也就是如果Tn(m)=□），则简单地写为0。我们 
可把新的步骤（也就是把H(n；m)的作用放在Tn(m)之前得到的）写成 
  
　　Tn(m)×H(n；m)。 
  
　　（我在这里使用数学运算顺序的普通习惯：在右边的先进行。请注意，我们在符号 
运算上有：□×0=0。） 
  
　　现在这张表变成： 
  
  
　 
  
　　我们注意到，假定H存在，该表的行由可计算的序列组成。（我用一个可计算序列表 
明一个其接连的值可由一个算法产生出来的一个无限序列；也就是存在一台图灵机，当 
它依序地应用于自然数m=0，1，2，3，4，5，…上时，就得到了这个序列的接续元素。 
）现在，我们从该表中可以注意到两个事实。首先自然数的每一可计算序列必须在它的 
行中出现在某处（也许出现好几回）。这个性质对于原先的带有□的表已经是真的。我 
们只不过是简单地加上一些行去取代“伪品”的图灵机（也就是至少产生一个□的那些 
）。其次，我们已经假定，图灵机H实际上存在，该表已被计算地（也就是用某个确定的 
算法）由步骤Tn(m)×H(n；m)产生。换言之，存在某一台图灵机Q，当它作用于一对数(n 
；m)时就会在表中产生合适的元素。为此我们可以在Q的磁带上以和在H中一样的方式对n 
和m编码。我们得到 
  
　　Q(n；m)=Tn(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+Tn(n)×H(n；n) 
  
　　（由于对角线是令m等于n而得到的）。但是，我们的表包括了每一可计算的序列， 
所以我们新的序列必须在表中的某一行。然而，这是不可能的！由于我们新序列和第一 
行在第一元素处不同，和第二行在第二元素处不同，和第三行在第三元素处不同等等。 
这是一个明显的冲突。正是这个冲突，建立了我们所要证明的，即在事实上图灵机H不存 
在！不存在决定一台图灵机将来停止与否的普适算法。 
  
　　另一种重述这个论证的方法是注意到，在假定H存在时，对于算法1+Q(n；n)(对角线 
步骤！)存在某一图灵机号码，譬如k，这样我们有 
  
　　1+Tn(n)×H（n；n）=Tn(n)。 
  
　　但是，如果我们在这个关系中代入n=k就得到 
  
　　1+Tk(k)×H(k；k)=Tk(k)。 
  
　　因为如果Tk(k)停止我们就得到了不可能的关系式 
  
　　1+Tk(k)=Tk(k)， 
  
　　(由于H(k；k)=1)，而如果Tk(k)不停止（这样H(k；k)=0)，我们有同样不协调的结 
果 
  
　　1+0=□， 
  
　　所以前面的假定导致一个矛盾。 
  
　　一台特定的图灵机是否停止是一个定义完好的数学问题（反过来，我们已经看到， 
各种有意义的数学问题可被重述成图灵机的停机问题）。这样，依靠显示不存在决定图 
灵机停机问题的算法，图灵（正如撤屈用自己十分不同的手段）指出，不存在决定数学 
问题的一般算法。希尔伯特的判决问题没有解答！ 
  
　　这不是说，在任何个别的情形下，我们不可能决定某些特殊数学问题的真理或非真 
理；或者决定某一台给定的图灵机是否会停止。我们可以利用一些技巧或者仅仅是常识 
，就能在一定情况下决定这种问题。（例如，如果一台图灵机的程序表中不包括STOP指 
令，或者只包含STOP指令，那么常识就足以告诉我们它会不会停止！）但是，不存在一 
个对所有的数学问题，也不存在对所有图灵机以及所有它们可能作用的数都有效的一个 
算法。 
  
　　我们似乎现在已经建立了，至少存在某些非决定的数学问题。然而，我们从未做过 
这种事！我们还没有展示过，存在某种特别尴尬的数时，它在某种绝对的意义上，不可 
能决定该机器是否停止。的确，正如我们很快就要看到的，情况刚好相反。我们关于单 
独问题的不可解性一点也没提，仅仅是说关于问题的族的算法的不可解性。在任何单独 
的情形下，答案或者为“是”或者为“非”，所以肯定存在一个决定那个特定情形的算 
法，也就是在它面临该问题时，依情况而定，会简单地讲“是”或“非”。当然，困难 
在于我们可能不知道用这些算法中的哪一个。那就是决定一个单独陈述而不是决定一族 
陈述的数学真理的问题。重要的是要意识到，算法本身不能决定数学真理。一个算法的 
成立总是必须由外界的手段来建立起来。 
  
　 
  
如何超过算法 
  
　 
  
　　我们在以后论及哥德尔定理时再回到决定数学陈述的真理性问题（参阅第四章）。 
我希望在此刻指出，图灵的论证比我迄今仿佛所暗示的更具建设性而更少负面性。我们 
肯定还没有展示出一台特殊的图灵机，它在某种绝对的意义上不能决定其是否停止的问 
题。的确，如果我们仔细地考察该论证就会发现，我们步骤本身实际上已经隐含地告诉 
我们，对这利用图灵步骤建造的似乎“极端荒谬”的机器的答案！ 
  
　　我们看看这是怎么来的。假定我们有某一个算法，它有时有效地告诉我们什么时候 
一台图灵机将不停止。正如在上面概述的，图灵步骤将明白地展现了一台图灵机计算， 
对这计算那个特殊算法不能决定其是否停止。然而，在这样做的同时，它实际上使我们 
在这情况下看到了答案！我们展现的特殊的图灵机计算的确不会停止。 
  
  
  
　　为了仔细考查这怎么引起的，假定我们具有一个这样有时有效的算法。正如以前那 
样，我们用H来标志这个算法（图灵机），但是现在允许该算法有时不能告诉我们一台图 
灵机在实际上将不停止： 
  
　　这样，当Tn(m)=□时H(n；m)=□是一种可能性。实际上存在许多这种算法H(n；m)。 
（例如，只要Tn(m)一停止，H(n；m)就能简单地产生1，尽管那个特殊的算法几乎没有什 
么实际的用处！） 
  
　　除了不把所有的□用0来取代而留下一些以外，我们可以像上述那样仔细地顺着图灵 
的步骤。正如以前那样，对角线过程提供了对角线上的第n个元素 
  
　　1+Tn(n)×H(n；n)。 
  
　　（只要H(n；m)=□，我们就将得到一个□。注意□×□=□，1+□=□。）这是一个 
完好的计算，所以它是由某一台，譬如讲第n台图灵机得到的，而且现在我们确实有 
  
　　1+Tn(n)×H(n；n)=Tk(n)。 
  
　　我们看第k个对角元素，也就是n=k，就会得到 
  
　　1+Tk(k)×H(k；k)=Tk(k)。 
  
　　如果计算Tk(k)停止，我们就有了一个矛盾（由于假定只要Tk(k)停止H(k；k)就为1 
，则方程导致不协调性：1+Tk(k)=Tk(k)。所以Tk(k)。不能停止，也就是 
  
　　Tk(k)=□。 
  
　　但是，算法不能“知道”这个。因为如果该算法给出H(k；k)=0，则我们应该又导致 
矛盾（我们得到了在符号上不成立的关系：1+0=□)。 
  
　　这样，如果我们能找到k，就将知道如何去建造击败我们知道其答案的算法的特别计 
算！我们怎么找到k呢？这是一项艰巨的工作。我们需要做的是仔细考察H（n；m）和Tn( 
m)的构造，然后仔细弄清1+Tn(n)×H(n；n)作为一台图灵机是如何动作的。我们发现这 
台图灵机的号码为k。要把这一切要弄透彻肯定是复杂的，但它是可以办得到的①。由于 
这种复杂性，若不是因为我们为了击败H而特地制造Tk(k)的这个事实，我们对计算Tk(k) 
毫无兴趣！重要的是，我们有了定义很好的步骤，不管我们的H是哪一个，该步骤都能找 
到合适的k，使得Tk(k)击败H，因此这样我们可以比该算法做得更好。如果我们认为自己 
仅仅比算法更好些，也许会给我们带来一些小安慰！ 
  
　　事实上，该过程被定义得如此之好，以至于在给定的H下，我们可找到产生k的一个 
算法。这样，在我们过于得意之前必须意识到，由于这个算法事实上“知道”Tk(k)=□ 
，所以它能改善9H，是不是？在上面提到一个算法时，用拟人化的术语“知道”是有助 
的。然而，该算法仅仅是跟随我们预先告诉它去跟随的法则，这难道不是我们在“知道 
”吗？或者我们自己，仅仅是在跟随我们的头脑的构造和我们的环境所预先编排我们去 
跟随的规则？这问题实在不只是简单的算法问题，而且是人们如何判断何为真何为伪的 
问题。这是我们必须重新讨论的中心问题。数学真理（以及其非算法性质）的问题将在 
第四章考虑。现在我们至少对术语“算法”和“可计算性”的意义以及某些相关的问题 
已有些领略。 
  
可计算性的概念是一个非常重要和美丽的数学观念。它又是相当近代的，具有这样基本 
性质的事体进入数学的王国是本世纪三十年代的事。这个观念已经渗透到数学的所有领 
域中去（虽然这一点确实是真的，但是大多数数学家通常不去忧虑可计算性的问题）。 
该观念的威力有一部分来自于这一个事实，即数学中一些定义得很好的运算实际上不是 
可计算的（例如图灵机的停机问题；第四章还可以看到其他例子）。因为如果不存在这 
种不可计算的事体，则可计算性的概念便没有多少数学的兴趣。数学家毕竟喜欢困惑的 
东西。让他们决定某些数学运算是否为可计算的可能是非常迷人的困惑。因为那个困惑 
的一般解答本身是不可计算的，这一点尤其迷人！ 
  
　　有一件事要弄清楚。可计算性是一个真正“绝对的”数学概念。它是一种抽象的观 
念，它完全超越按照我们描述的“图灵机”的任何特别实现之外。正如我在以前所评论 
的，我们不必对表征图灵的天才而特别的手段的“磁带”和“内态”等等赋予任何特别 
的意义。还有表达可计算性观念的其他方法，历史上最早的是美国逻辑学家阿伦佐·撤 
屈在斯蒂芬·C·克利涅协助下提出的杰出的“拉姆达计算法”。撤屈的步骤和图灵的完 
全不同，并且更为抽象得多。事实上，在 非 述他观念的形式� ，在它们和任何可以 
称作“机械的”东西之间只有一点明显的连接。 非 步骤背后的关键观念在其最本质上 
的确是抽象的，实际上撤屈把这步骤称为“抽象化”的一个数学运算。 
  
　　不仅是因为撤屈方案强调可计算性是一个独立于计算机器的任何特别概念的数学观 
念，而且它阐明了在数学中抽象观念的威力，所以我感到值得花一点时间来简要地描述 
它。对数学观念不熟悉或者对这件事本身不感好奇的读者，在这一阶段可以跳到下一章 
去，这不会对论证的过程产生多少损失。尽管如此，这样的读者若愿意和我多忍受一阵 
会得到好处，并且能见证撤屈方案的某些魔术般的经济性（参见撤屈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(fx)〕。 
  
　　这是一个函数，当它作用于另一函数，譬如讲g时，产生g两次递归地作用于x上的函 
数，也就是 
  
　　(λf.〔f(fx)〕)g=g(gx)。 
  
　　我们也可以首先“抽象化走”x以得到 
  
　　λf.〔λx.〔f(fx)〕〕, 
  
　　此式可以缩写成 
  
　　λfx〔f(fx)〕。 
  
　　这是当作用于g时产生“g被递归两次”的函数。事实上，这正是撤屈将其和自然数2 
相等同的函数。 
  
　　2=λfx．〔f(fx)〕， 
  
　　这样，(2g)y=g(gy)。他类似地定义： 
  
　　3=λfx．〔f(f(fx))〕，4 
  
　　=λfx〔f(f(f(fx))〕，等等， 
  
　　以及 
  
　　1=λfx．〔fx〕，0=λfx，〔x〕。 
  
   〕非摹�2”真的更像“两次”，它的“3”是“三次”等等。这样3在一个函数f上 
的作用，也就是3f是“把f递归三次”的运算。因此，3f在y上的作用是（3f)y=f(f(f（y 
)))。 
  
　　让我们看看，一个非常简单的算术运算，也就是如何把1加到一个数上的运算在撤屈 
方案中表达出来。定义 
  
　　S=λabc．〔b((ab)c)〕。 
  
　　为了阐明S的确简单地把１加到用撤屈记号表示的一个数上，让我们做这样的检验： 
  
　　S3=λabc．〔b((ab)c)〕3=λbc．〔b((3b)c)〕=λbc.〔b(b(b(bc)))〕=4， 
  
　　这是由于(3b)c=b(b(bc))。很清楚，这可同样好地适用于任何其他自然数。（事实 
上λabc．〔(ab)(bc)〕可以和S一样好地做到。） 
  
　　把一个数乘二又如何呢？这种加倍可由 
  
　　D=λabc．〔(ab)((ab)c)〕 
  
　　获得，它可再次由作用于３上而得到验证： 
  
　　D=λabc.〔(ab)((ab)c)〕3=λabc.〔(3b)((3b)c)〕 
  
　　=λabc.〔(3b)(b(b(bc)))〕=λabc.〔b(b(b(b(b(bc)))))〕=6。 
  
　　事实上，加法、乘法和升幂的基本算术运算可分别定义为 
  
　　A=λfgxy.〔((fx)(gx))y〕, 
  
　　M=λfgx.〔f(gx)〕, 
  
　　P=λfg.〔fg〕。 
  
　　读者也许介意使自己或他人信服，我们的确有如下结果： 
  
　　(Am)n=m+n，(Mm)n=M×n，(Pm)n=nm， 
  
　　这儿m是n是撤屈的两个自然数的函数，m+n是它们和的相应函数，等等。最后那个公 
式是最令人惊异的。让我们仅仅检验其m=2，n=3的情形： 
  
　　(p2)3=((λfg.〔fg〕)2)3=(λg.〔2g〕)3 
  
　　=(λg.〔λfx.〔f(fx)〕g〕)3 
  
　　=λgx.〔g(gx)〕3=λx.〔3(3x)〕 
  
　　=λx.〔λfy.〔f(f(fy))〕(3x)〕 
  
　　=λxy.〔(3x)((3x)((3x)y))〕 
  
　　=λxy.〔(3x)((3x)(x(x(xy)))))〕 
  
　　=λxy.〔(3x)(x(x(x(x(xy)))))〕 
  
　　=λxy.〔x(x(x(x(x(x(x(x(xy))))))))〕 
  
　　=9=32 
  
　　减法和除法不是这么容易定义的（我们的确需要某种当m比n小时“m-n”以及当m不 
能被n整除时“m÷n”的惯例。事实上，二十世纪三十年代早期克利涅发现如何在撤屈的 
方案中表达减法运算被认为是这一学科的重要里程碑！后来接着又有其他的运算。最后 
，撤屈和图灵在1937年独立地指出，不管什么样的可计算的（或算法的）运算（现在在 
图灵机的意义上）都可以按照撤屈的一种表达式获得（而且反之亦然）。 
  
　　这是一个真正惊人的事实，它被用来强调可计算性思想的基本客观性以及数学特征 
。初看起来，撤屈的可计算性概念和计算机器没有什么关系。然而，它和实际计算具有 
某些基本关系。尤其是，有力而灵活的电脑LISP语言以一种根本的方式参与到撤屈计算 
法的基本结构中来。 
  
　　正如我早先指出的，还有其他定义可计算性概念的方法。波斯特的计算机器的概念 
和图灵的非常接近，并且几乎是同时独立提出的。近世还有更有用的可计算性（递归性 
）的定义，这是J·赫伯拉德和哥德尔提出的。H·B·邱雷在1929年，以及M·轩芬克勒 
在1924年稍早些时候提出了不同的方法，撤屈计算法就是部分地由此发展而来（参见甘 
迪1988）。现在研究可计算性的手段（诸如在（卡特兰1980）中描述的一台无限记录机 
器）在细节上和图灵原先的相差甚多，而且它们更实用得多。然而，不管采用那种不同 
的手段，可计算性的概念仍然相同。 
  
　　正如许多其他的数学观念，尤其是更美丽的、更基本的那些，可计算性的观念似乎 
自身具有某种柏拉图的实在性。在下面两章，我们应该探讨的正是数学概念的柏拉图实 
在性的这个神秘问题。 
  
注 释 
  
　　1．我是采用当代通常的术语，它现在把零包括在“自然数”之中。 
  
　　2．还有许多把一对、三个等等数编码成单独一个数的其他方法。虽然它们对于我们 
现在的目的不甚方便，数学家却熟知这些方法。例如，公 
  
　　试试看！ 
  
　　3．我在上面没花工夫去引进某种表示起始一个数（或指令等等）的序列的记号。这 
对于输入没有必要，由于当遭遇到第一个1时事情刚刚开始。然而，对于输出需要某些其 
他东西，这是由于人们预先为了达到第一个（也就是最左边的）1不知道要沿着输出磁带 
看多远。尽管在往左看时会遇到0的很长的串，这并不能保证在左边更远处不再有1。人 
： 
  
　　1000000001011101001101000100101010110100011010001010000011010100110100010 
101001 
  
011010000110100010100101011010010011101001010010010111010l1001110101010010010 
10 
  
11101010100110100010100010101101001000000001011101001101000100101010110100011 
0 
  
10001010000011010100110100010101001011010000110100010100101011010010011101001 
01 
  
0010010111010l1001110101010010010101110101010011010001010001010110100 
  
　　1000000001011101001101000100101010110100011010001010000011010100110100010 
1 
  
01001011010000110100010100101011010010011101001010010010111010l10011101010100 
10