6，8，
在二进位记号也就是１１０，１０００扩展后在磁带上编码成
.０００００１０１００１１０１００００１１００００００.
对于这一对特殊的数，并没有比一进位形式更紧凑。然而，譬如说我们取
（十进位数）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就会更好。
作为旁白，我愿意指出对于扩展二进位比一进位图灵机显得更简单的
一个运算，这就是乘二。在这里由
一个运算，这就是乘二。在这里由
机
XN×2能在扩展的二进位上实现这个运算，而前面描述的相
应于一进位的机器
UN×2就要复杂得多！
我们从这里得到了，关于图灵机在非常基础水平上可做到的一些事情
的概念。正如预料得到的，当进行某些复杂的运算时，它们会变得极为复
杂。这种仪器的终极能力是什么呢？让我们在下面讨论这一个问题。
撤屈——图灵主题
撤屈——图灵主题
提供其结果为一对自然数的运算，譬如带有余数的除法，或者其结果为任
意大数目的数的有限集合。此外，可以这样地建造图灵机，即预先没有必
要指定它要做何种运算，其运算的指令由磁带提供。需要实行的特定运算
也许在某一阶段依赖于该机器在某个更早阶段的需要进行的某个计算的结
果。（“如果那个计算的结果比某数大，则做这个；否则就做那个。”）
一旦人们理解到，他可制造实现算术或简单的逻辑运算的图灵机，则很容
易想象如何使之进行具有算法性质的更复杂的任务。在他们捣弄了好一阵
之后，很容易坚信，这类机器的确能实行不管什么样的机械运算！在数
学上，可以很合情合理地把机械运算定义为可被这样的一台机器所执行的
运算。数学家用名词“算法”以及形容词“可计算的”、“递归的”和“有
效的”来表示能由这类理论机器——图灵机实行的机械运算。一个步骤只
要是足够清楚并且机械的，则可合理地相信能找到一台执行它的图灵机。
这正是我们（也就是图灵）引进图灵机概念本身的初步讨论的全部要点。
另一方面，人们仍会感到，这些机器的设计不必这么局限。初看起来，
只允许仪器在一个时刻读一个二进位位数（０或１），并且一次沿着一个
单独的一维磁带只移动一格似乎是限制。为什么不允许大数目或相互联结
的阅读机一下子跑过四条或五条甚至一千条分开的磁带呢？为什么不允许
０和１的方格的整个平面（或者甚至一个三维的阵列），而坚持只用一维
的磁带呢？为什么不允许从某种更复杂的计数系统或字母来的其他符号
呢？事实上，虽然这些改变中的一些会对运算的经济性造成一定程度的不
同（正如允许用多于一条的磁带一定会是这种情形那样），但是所有这一
切都不会对我们在原则上要得到的东西造成丝毫的影响。即使我们在所有
这些方面一下子推广该定义，这种归于“算法”的名下（或“计算”、“有
效步骤”或“递归运算”）所实现的运算种类刚好和推广以前的完全相同！
我们可以看到，没有必要有多余一条的磁带。只要该仪器需要时总能
在给定的磁带不断地找到新的空白。为此，也许必须不断地把数据从磁带
的一处往另一处调度。这也许是“低效率的”，但是它不限制在原则上可
以得到的极限
4。类似地，利用多于一台并行动作的图灵机——这在近年
由于和想更接近地仿照人脑试图相关联而变得很时髦——不能在原则上
得到任何新东西（虽然在某种情形下可改善动作的速度）。拥有两台分开
的、不直接相互联络的仪器并不比两台相互联络的得到更多，而且如果它
们联络，则实际上只不过是一台单独的仪器！
关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带
关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带
一维磁带。一个平面似乎比一维磁带更接近于一个“流程图”（正如在上
面对欧几里德算法运算的描述）所需要的
①。然而，在原则上没有困难以“一
维的”形式（也就是利用流程图的通常术语来描述）写出流程图的运行。
在二维平面上显示只是为了我们的便利和容易理解，它对原则上能得到的
并没造成什么影响。人们总能把一个二维平面上甚至三维空间上的一个记
号或对象的地址，直截了当地在一维磁带上编码。（事实上，使用一个二
维平面完全等效于用两根磁带。这两根磁带提供为在二维平面上指明一点
所需的两个“座标”；正如三根磁带可作为一个三维空间的一点的“座标”
一样。）这一维的编码再次可能为“低效率的”，但是它在原则上不限制
我们的目标。
尽管所有这一切，我们仍然可心询问，图灵机的概念是否真的和我们
希望叫做“机械的”每一逻辑或数学运算相统一。在图灵写他的开创性文
章的时候，这一点比今天模糊得多，所以他觉得有必要把情形解释得更清
楚一些。图灵的严密论证从以下事实得到了额外的支持，这就是美国逻辑
学家阿伦佐·撤屈（在
S.C.克利涅的协助下）完全独立地（并实际上稍早
一些）提出了一种方案，也是旨在解决希尔伯特的判决问题的拉姆达计
算。尽管它不如图灵的那么明显地为一种完全广泛的机械的方案，但在数
学结构上的极端经济性方面有些优点。（我将在本章的结尾描述撤屈的杰
出的计算。）还存在其他一些解决希尔伯特问题的和图灵相独立的设想（见
甘迪
1988），尤其是波兰——美国逻辑学家爱弥尔·波斯特的设想（比图
灵稍晚些，但其思想和图灵比和撤屈更相像许多）。所有这些方案很快就
被证明是完全等效的。这就给现在称作撤屈——图灵主题的观点增加了许
多份量，即图灵机（或等效的）概念实际在数学上定义了我们认为是算法
（或有效、或递归、或机械的）步骤的东西。现在，高速电脑已变成我们
生活中如此熟悉的部分，很少人似乎觉得有必要去问这些主题的原始形
式。相反地，已有不少人转去注意真正的物理系统（假定包括人脑）——
精确服从物理定律的东西——是否能够实行比图灵机更多、更少或刚好一
样多的逻辑和数学运算。我本人是非常喜欢撤屈——图灵主题的原先的数
学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本书主
要关注的另外一个单独的问题。
①正如这里所描述的，这一流程图本身实际上是“仪器”的一部分，而不是外部环境的“磁带”。我们在
磁带上表示的正是实际的数
A，B，A-B等等。然而，我们还要以一个线性的一维形式来表达该仪器的详细
指明。正如我们将要看到的，和普适图灵机相关的，在一台特殊仪器的详细指明和对该仪器可能的“资料”
（或“程序”）的详细指明之间有个密切关系。所以，使这两者都处于一维形式是方便的。
不同于自然数的数
不同于自然数的数
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，这样不断地下去。事实上，一定存
在在这个意义上产生π的全部小数展开的图灵机，尽管要把它明显地造出
来颇费一点周折。类似的评论也适用于许多其他无理数，譬如
2
=1.414213562.。然而，正如在下一章将要看到的，人们发现有些无理数
（非常引人注目地）根本不能由任何图灵机产生。能以这种方式产生的数
叫作可计算的（图灵
1937）。那些不能的（实际上是绝大多数！）是叫作
不可计算的。我们将在后面的章节中回到这件事体及有关的问题上来。按
照物理理论，用可计算的数学结构能否足够地描述实在的物理对象（也就
是人脑），是我们要关心的问题。
一般地讲，可计算性是数学中的一个重要问题。人们不应该只将其当
成只适合于这类数的事体。人们可有直接作用于诸如代数或三角的数学公
式上的图灵机，或可进行微积分的形式运算的图灵机。人们所需的一切是
某种准确地把所有涉及的数学符号编码成
0和
1序列的形式，然后再利用
图灵机的概念。这毕竟是图灵在着手解决判决问题时心里所想的，即寻求
回答具有一般性质的数学问题的算法步骤。我们将很快地回到这上面来。
普适图灵机
普适图灵机
为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方
式。考虑定义某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我
们必须按照某种准确的方案把这表编码成.. 0和.. 1的串。我们可借助于以前
采用的“收缩”步骤来办到。因为，如果我们用数.. 2，3，4，5和.. 6来分别
代表符号.. R、L、STOP、箭头（→）以及逗点，那么我们就可以用１１０、
１１１０、１１１１０、１１１１１０以及１１１１１１０的收缩把它们
编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成０
和１０的位数.. 0和１。由于在该图灵机的表中，在二进位计数的结尾大写
的数的位置足以把大写的０和１从其他小写的阿拉伯数字中区分开来，所
以我们不需要用不同的记号。这样，110１将被读成二进位数.. 1101，而在
磁带上被编码成１０１００１０。特别是，0０读作.. 00，它可毫不含糊地
被编码成０，或者作为被完全省略的符号。实际上我们可以不必对任何箭
头或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些
符号必须是什么。尽管在采用这个步骤时，在必要之处要提供一些额外的
“哑”指令，以保证在这个顺序中没有缝隙。这样的做法具有相当好的经
济性。（例如，图灵机XN+1没有告诉我们对.. 110０要做什么的命令，这是
因为这条指令在机器运行时从不发生，所以我们应该插入一条“哑”指令，
譬如讲.. 110０→0０R，它可合并到表中而不改变任何东西。类似地，我们
应该把.. 10１→0０R插入到.. XN×2中去。）若没有这些“哑的”，表中后面
的指令的编码就会被糟蹋了。因为在结尾处的符号.. L或.. R足以把一条指令
和另一条隔开，所以我们在每一指令中实际不需要逗号。因此，我们采用
下面的编码：
０表示.. 0或０，１０表示1或１，１１０表示R，１１１０表示L，１１１１０表示.. stop。
作为一个例子，让我们为图灵机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简单地
用
用
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台图灵机，并用
T
n来表
示。这样，XN+1是第
450813704461563958982113775643437908台图灵机！
我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如
此平凡的（在扩展二进位记号上）对自然数加一的运算，这真使人印象深
刻！（尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得
相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN+1的二
进位号码为
１０１０１１０１０１１１１０１０１０
它只是十进位制的
177642！这样，只不过是把一个附加的
1加到序列
1的
尾巴上的特别平凡的图灵机
UN+1是第
177642台图灵机。为了好奇的原因，
我们可以注意在任一种进位制中“乘二”是在图灵机表中这两个号码之间
的某处。我们找到
XN×2的号码为
10389728107，而
UN×2的号码为
1492923420919872026917547669。
人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数
根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的十三台
图灵机列出来：
T0：0０→0０R，0１→0０R，
TT：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，
