的时间越长。但在任何特定的情形下，该步骤最后会终结，并在有限的步
骤内得到一个确定的答复。每一步骤所要进行的运算都是非常明了的。此
外，尽管它可应用到大小没有限制的自然数上去的这个事实，但是可以用
1
有限的术语来描述整个过程。 （“自然数”简单地就是通常的非负 整数
0，1，2，3，4，5，6，7，8，9，10，11……）。的确很容易建立一个 （有
限的）描述欧几里德算法全部逻辑运算的 “流程图”。
应该提到，我们在这里隐含地假定，已经 “知道”如何实行从两个任
意自然数A 和 B 的除法中得到余数的必须的基本运算，所以这一步骤还未
完全被分解成最基本的部分。那种运算又是算法的，是用我们在小学学到
的除法的非常熟悉的步骤来进行的。在实际上，这个步骤比欧几里德的其
他部分更复杂不少，但是可以再为它建立一个流程图。其复杂性主要起源
于这个事实，即我们是 （假定）对自然数用标准的“十进位”记号，这样
子我们需要列出全部的乘法表和忧虑移位等等。如果我们简单地用一连串
某种 n个记号来代表数 n，例如……代表五，那么可从非常初等的算法运
算看到余数的形成。为了得到当A 被 B 除时的余数，可以简单地从代表A
的记号中不断取走代表B 的符号串，直到最后余下的记号不够再进行这种
运算为止。最后剩下的符号串提供了所需的答案。例如，为了得到十七被
五除的余数，我们可以简单地从……………不断地取走五的序列……正如
下面所示：
………………
……………
…………
．．
----------------------- Page 44-----------------------
由于我们不能再继续这种运算，所以很清楚，其答案是二。
用这种连续减法找到除法余数的流程图可由下图给出：
为了使欧几里德算法的全部流程图完整，我们把上面形成余数的流程
图代入到原先流程图的中右部的盒子中去。这种把一个算法向另一个代入
是一种普遍的编电脑程序的步骤。上述寻求余数的算法是一道子程序的例
子，也就是说，它是由主程序当作它的运算的一部分 （通常是预先知道的）
召来使用的算法。
当然，把数n简单地用 n个斑点来表示，在涉及到大数时效率非常低，
这就是为什么我们通常用更紧凑的诸如标准的 （十进位）系统的原因。然
而，我们在这里并不特别关心运算或记号的效率。我们所关心的是运算在
原则上是否可被算法地实行的问题。如果我们用一种数的记号是算法的东
西，则用另一种记号也是算法的。两种情况中只有在细节上和复杂性上有
差别。
欧几里德算法只是在整个数学中可找到的大量的经典算法步骤之一。
尽管算法的这一特殊例子的历史渊源，一般算法概念的准确表达只从本世
纪起才有记载，也许这是令人印象深刻的。事实上，这一概念的各种不同
描述都是在本世纪三十年代给出的。称作图灵机的概念是最直接的、最有
说服力的、也是历史上最重要的。相当仔细地考查这些 “机器”将是很适
当的。
关于图灵“机”有一件事必须记在心里，就是说它是一段“抽象数学”，
而不是一个物理对象。这一概念是由英国数学家、非凡的破码专家兼电脑
科学的开山鼻祖阿伦·图灵在 1935—1936年间提出的 （图灵1937）。其
目的是为了解决称为判决问题的一个范围广阔的问题。它是由伟大的德国
数学家大卫·希尔伯特部分地于 1900年巴黎国际数学家会议上 （“希尔伯
特第十问题”），更完整地于 1928年玻罗那国际会议上提出的。希尔伯特
不多不少地要求解决数学问题的一般算法步骤，或者不如讲，是否在原则
上存在这样步骤的问题。希尔伯特还有一个要把数学置于无懈可击的坚固
基础上的宏伟规划，其中公理和步骤法则一旦定下就不能变。但是在图灵
----------------------- Page 45-----------------------
完成其伟大的工作之际，这个规划已经遭受到由奥地利才气焕发的逻辑学
家库尔特·哥德尔在1931年证明的令人吃惊的定理的粉碎性打击。我们将
在第四章考虑哥德尔定理及其意义。图灵关心的希尔伯特问题 （判决问
题）超越出任何按照公理系统的特殊的数学形式。问题在于，是否存在能
在原则上一个接一个地解决所有 （属于某种适当定义的族的）数学问题的
某种一般的机械步骤？
回答这一问题的部分困难在于决定什么叫做 “机械过程”。这概念处
于当时正常的数学概念之外。为了掌握它，图灵设想如何才能把 “机器”
的概念表达出来，它的动作被分解成基本的项目。这一些似乎是清楚的，
图灵也把人脑当成在他意义上的 “机器”的例子。这样，由人类数学家在
解决数学问题时进行的任何活动，都可以被冠以 “机械步骤”之名。
虽然这一有关人类思维的观点似乎对于图灵发展他的极重要概念很有
价值，我们却绝没有必要去附和它。的确，图灵在把机械过程的含义弄精
确时，向我们展示出存在一些完好定义的数学运算，在任何通常的意义上，
都不能被称为机械的！图灵本人的这一方面工作现在可间接地为我们提供
了他自己有关精神现象性质观点的漏洞。这个事实也许不无讽刺意味。然
而，这不是我们此刻所关心的。我们首先要弄清图灵心目中的机械过程究
竟是什么。
----------------------- Page 46-----------------------
图灵概念
我们设想实现某种 （可以有限地定义的）计算步骤的一台仪器。这样
仪器会采取什么样的一般形式呢？我们必须准备理想化一些，而且不必为
实用性过份担心：我们是真正地考虑一台数学上理想化的 “机器”。我们
要求该仪器具有有限 （虽然也许非常大的）数目的不同可能态的分立集合。
我们把这些称作仪器的内态。但是我们不限制该仪器在原则上要实现的计
算的尺度。回顾一下上述的欧几里德算法。在原则上不存在被该算法作用
的数的大小的限制。不管这些数有多大，算法或者一般计算步骤都是同样
的。对于非常大的数，该步骤的确要用非常长的时间，而且需要在数量可
观的 “粗纸”上面进行实际的计算。但是不管这些数有多大，该算法是指
令的同一有限集合。
这样，虽然我们仪器只有有限个内态，它却能够处理大小不受限制的
输入。此外，为了计算应允许该仪器召来无限的外存空间（我们的“粗纸”）；
而且能够产生大小不受限制的输出。由于该仪器只有有限数目的不同的内
态，不能指望它把所有外部数据和所有自己计算的结果 “内化”。相反地，
它必须只考察那些立即处理的数据部分或者早先的计算，然后进行需要对
它们进行的任何运算。也许可在外存空间把那个运算的相关结果记下来，
然后以一种精确决定的方式进行下一个阶段的运算。正是输入、计算空间
和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，
而不是在实际上可真正建造的某种东西 （见图2.1）。但这是极其关键的
理想化。对于大多数实用目的而言，当代电脑技术的奇迹为我们提供了无
限的电子存储仪器。
事实上，在上述讨论中称为 “外部的”存储空间的类型，可实际
上被认为是现代电脑的内部工作的一部分。存储空间的某一确定部分是否
被当作内部的或外部的，也许只是术语的问题。按照硬件和软件是划分“仪
器”和 “外部”的一种方法。内部可当成硬体，而外部为软体。我将不必
拘泥于此，但是不管从那个角度看，当代电子电脑是图灵的理想化的极好
近似。
图2.1 一台严格的图灵机需要无限的磁带
图灵是按照在上面作记号的“磁带”来描述其外部数据和存储空间的。
一旦需要，仪器就会把该磁带召来 “阅读”，而且作为其运算的一部分，
磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号，允许
同一磁带像外存 （也就是“粗纸”）以及输入那样动作。因为在许多运算
中，一个计算的中间结果起的作用正如同新的数据，所以事实上在“外存”
和 “输入”之间不做任何清楚的区分也许是有益的。我们记得在欧几里德
----------------------- Page 47-----------------------
算法中，不断地用计算不同阶段的结果去取代原先的输入 （数A 和 B）。
类似地，这同一磁带可被用作最后输出 （也就是“答案”）。只要必须进
行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最
后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上
显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所
有数据以及要解的问题的详细说明总是由右边进去。
让我们有限的仪器前后移动一条潜在地无穷长的磁带，我自己觉得有
点不舒服。不管其材料是多么轻，移动无限长的磁带是非常困难的！相反
地，我宁愿把磁带设想成代表某一外部环境，我们有限的仪器可以通过这
环境进行移动。 （当然用现代电子学，既不需要“磁带”也不需要“仪器”
作实际的、在通常物理意义上的 “运动”，但是这种“运动”是一种描述
事体的便利方法。）依此观点，该仪器完全是从这个环境接受它的输入。
它把环境当成它的 “粗纸”。最后将其输出在这同一个环境中写出。
在图灵的描述中， “磁带”是由方格的线性序列所组成，该序列在两
个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个
①
单独的记号 。我们可利用有记号或者没有记号的方格来阐释，我们的环境
（也就是磁带）可允许被细分并按照分立 （和连续相反的）元素来描述。
如果希望仪器以一种可靠并绝对确定的方式工作。这似乎是合情理的要做
的事。然而，我们允许该 “环境”是（潜在地）无限的，把这作为我们使
用的数学理想化的特征。但是，在任何特殊的情形下，输入、计算和输出
必须总是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该
有有限数目的实在的记号。磁带在每一个方向的一定点以外必须是空白
的。
我们用符号 “0”来表示空白方格，用符号 “1”来代表记号方格，例
如：
0 0 0 1 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0
我们要求该仪器 “读”此磁带，并假定它在一个时刻读一个方格，在每一
步运算后向右或向左移动一个方格。这里没有损失任何涉及到的一般性。
可以容易地由另一台一次只读和移动一个方格的仪器去仿照一台一次可读
n个方格或者一次可移动 k个方格的仪器。k方格的移动可由一个方格的 k
次移动来积累，而存储一个方格上的n种记号的行为正和一次读 n个方格
一样。
这样的一台仪器在细节上可做什么呢？什么是我们描述成 “机械的”
东西作用的最一般方式呢？我们记得该仪器的内态在数目上是有限的。除
了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态
① 事实上，图灵在他原先的描述中允许磁带有更复杂的记号，但这并没有什么本质上的差别。更复杂的记
号总能被细分成记号和空白的序列。我将随意地对他原先的详细说明作各种不重要的变通。
----------------------- Page 48-----------------------
和输入所确定。我们已把输入简化成只是两个符号 “0”或 “1”之中的一
个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内
态改变成某种其他 （或可能是同样的）内态，它用同样的或不同的符号0
或 1来取代它刚读过的0 或 1；它向右或向左移动一个方格；最后它决定
是继续还是终止计算并停机。
为了以明白的方式定义该仪器的运算，我们首先，譬如讲用标号0，1，
2，3，4，5，……，来为不同的内态编号；那么，用一张显明的代换表可
以完全指定该仪器或图灵机的运行，譬如：
00→00
R
01→131
L
10→651
R
11→10
R
20→01R STOP
21→661
L
30→370
R
··
··
··
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，但这是低效率的。相反地，
----------------------- Page 49-----------------------
我们使用现在人们很熟悉的二进位记数系统：
0→0，
1→1，
2→10，
3→11，
4→100，
5→101，
6→110，
7→111，
8→1000，
9→1001，
10→1010，
11→1011，
