用于不同的简单的图灵机号码中验证上面的号码事实上的确给出了一台普
适图灵机的动作行为！
对图灵机的不同明记方法可使
u的值降低一些。例如，我们可以免除
stop，而相反地采取这样的规则，即只要机器在某个其他非
0的内态后重
新进入内态
0时它就停止。这样做没有太多收益（如果有的话）。如果我
们允许磁带有比仅仅
0和
1的更多的记号，则能得到更大的收益。在文献
中的确描述过显得非常简洁的普适图灵机。但是，由于它们一般地依赖于
图灵机描述的极其复杂的编码，所以这种简洁性是骗人的。
8．参阅德伏林(1988)的和这一著名断言相关事体的非技术性讨论。
9．我们再次简单地应用前面进行的步骤，当然也能击败这个改善了的
算法。然后我们可以用这新的知识去进一步改善我们的算法；但是我们又
可将其击败等等。这一递归步骤所导致的这类考虑将在第四章第
125页的
和哥德尔定理联系起来讨论。
第三章数学和实在
托伯列南国
托伯列南国
图.. 3.1 奇异世界之第一瞥。
它为何物？它是一只形状古怪的昆虫吗？也许它是一个深颜色的并有
许多山溪注入的湖泊。也许它是一座巨大的形状奇特的异国城市，公路沿
着不同方向散开到附近的小镇和乡村去。它也许为一个岛屿——让我们寻
找看在附近是否有和它相连接的陆地。我们可以后退一些，把我们的感觉
仪器的放大倍数减少十五倍左右。嗬，整个世界进入了我们的视界之内（图
3.2）。
图.. 3.2 整个“托伯列南国”。箭头这下标出了在图.. 3.1、图.. 3.3和图
3.4中的放大部分的位置。
我们在“岛”在图.. 3.2中看起来成为标记“图.. 3.1”下的小斑点。除
了一条连接到右手的裂缝上去的以外，从原先岛上出发的小片断（溪流、
路径、桥梁？）全部都终结了。该裂缝最终接到我们在图.. 3.2画出的大得
多的物体上去。这个更大的物体虽然和我们第一次看到的岛不完全一样，
但明显地相似。如果我们更仔细地审视这一物体和海岸线相像的东西，就
发现多得数不清的圆形的瘤状结构。每一结构自身又具有类似的瘤。似乎
每一小瘤都在某一微小的地方附在一个更大的瘤上，由此在大瘤上产生出
许许多多的小瘤。当图像变得更清楚时，人们就看到了从这个结构发出的
成千上万根的细丝。这些细丝在不同的地方分叉并常常剧烈地弯折。在细
丝的某些点，我们似乎看到了具有现有的放大倍数的感觉仪器所不能分析
的复杂扭结。很显然，这物体不是实际的岛屿或陆地，也不是任何风景。
或许我们看到了某种怪诞的甲虫。我们首先看到的是它的婴儿，它用某种
丝线状的脐带安静地把自己连接在母体上面。
让我们把感觉仪器的放大倍数提高十倍，再来考察这个怪物的一个瘤
的性质（图.. 3.3——其位置在图.. 3.2中的“图.. 3.3”的标志的下面）。这个
瘤本身和怪物整体非常相似——除了在接触点以外。请注意在图.. 3.3中的
不同地方五根细丝并到一块。这个特定的瘤似乎有一确定的“五性”（正
如在最上面的瘤具有“三性”一样）。如果我们考察下一个相当尺度的瘤，
在图.. 3.2中稍微向左下方一点，我们就会在附近发现“七性”，再下一点
为“九性”，并以此类推。当我们进入图.. 3.2中的两个最大区域之间的裂
缝，就会发现右边的瘤以奇数来表征，每回增加二。让我们钻到裂缝深处，
把图
3.2再放大十倍左右（图
3.4）。我们看到其他许多小瘤以及扭转的
结构。在右边称为“海马谷”的区域可鉴别出某些微小的涡旋状的“海马
尾巴”。——如果放大倍数足够大的话，我们就将看到不同的“海乌贼”
或者别具花样的区域。这也许的确是某种奇异的海岸线——也许是所有各
色各样生命产生的珊瑚。看起来像是花的东西在更高的放大倍数下显得是
由成千上万个微小，但同时却是不可思议的复杂的结构组成，每一结构都
有极多的丝状物和扭转的涡旋尾巴。让我们稍微仔细地考察一个较大的海
马的尾巴，也就是在图
3.4中刚好能见到标志为“图
3.5”的那个（它附
在具有“二十九性”的瘤上面！）。大约再放大
250倍左右，我们就得到
了画在图
3.5中的涡旋。我们发现这个尾巴非同寻常，它是由最复杂的、
前后扭曲的、无数的小涡旋以及像章鱼和海马那样的区域组成。
图
3.3一个具有“五性”的细丝的瘤。
图
3.4主狭缝：在右下方可见到“海马谷”。
图
3.5海马尾巴的近窥。
图
3.6两个涡旋会合处的进一步放大细节。在中心点处刚刚可以见到
一个小婴儿。
图
3.7婴儿在放大之后就显得和整个世界很相似。
在这个结构的许多地方刚好有两个涡旋碰到一起。让我们把放大倍数
增加三十倍左右，以考察其中一处（在图
3.5中的标志“图
3.6”的下面）。
请注意，我们是否发现了中间有个奇怪但非常熟悉的对象？再放大六倍左
右（图
3.7）就能揭示出一个怪物的小婴儿——它几乎和我们考察过的整
个结构完全一样！如果我们细看，就会发现从它那里出发的细丝和从主结
构那里出来的略有差别。它们扭曲并延伸到更远得多的距离去。然而比细
小结构本身几乎和它的上一代毫无差别，甚至在非常相应的地方拥有自己
的后代。如果我们还进一步放大，就能继续考察这些东西。孙子们又非常
类似于它们的共同祖先——人们很容易相信，这些现象会无限地延续下
去。只要不断地提高我们感觉仪器的放大倍数，就可随心所欲地探索托伯
列南的奇异世界。我们发现了无穷尽的变化：没有两个区域是完全相像的
——但是我们很快就会习惯于存在的一些普遍的风格。而熟知的类甲虫的
结构以越来越小的尺度重新出现。每一回它的附近的细丝结构都和早先看
到的不同，并以不可置信的复杂的美妙的新景象呈现在我们的面前。
使我们目瞪口呆地奇异的、变化多端的、美妙的、复杂的国土究竟为
何物呢？许多读者无疑已经知道。但还有一些读者不知道。这世界只不过
是一点抽象数学——称为孟德勒伯洛特集
1的集合。尽管它无疑是复杂
的，却是由极其简单的规则产生的！为了恰当地解释该规则，我首先得解
释什么是复数。除了这里以外，在将来还有用。它对于量子力学的结构，
所以也就是我们生活其中的世界的运行是绝对基本的。它们构成了数学中
的一个伟大奇迹。为了解释何为复数，首先得提醒读者何为“实数”。另
外，弄清概念和“真实世界”的实在的关系也是非常有益的。
实数
实数
0，1，2，3，4，5，6，7，8，9，10，11，.
这些是不同种类数中最初等和最基本的。任何分立的对象都可以用自然数
予以量化：我们可以讲田地里有二十七只绵羊，可以讲两次闪电，十二个
晚上，一千个词，四次谈话，零个新观念，一个错误，六位缺席者，两次
方向改变等等。自然数可以相加或相乘以得到新的自然数。它便是上一章
给出的关于算法的一般讨论的对象。
然而某些重要的运算会把我们带到自然数王国之外——最简单的是减
法。为了系统地定义减法，我们需要负数；为此目的我们建立了整数的整
个系统
.，-6，-5，-4，-3，-2，-1，0，1，2，3，4，5，6，7，.。
一定的事物，譬如电荷、银行的存款或者年份①可用这类数来量化。然而，
这些数的范围仍然过于局限。这是由于把一个数除以另一个数时，我们仍
然不能畅通无阻。相应地，我们需要分数或有理数。
0，1，-1，1/2，-1/2，2，-2，3/2，-3/2，1/3，.。
这一些对于有限算术的运算已经足够。但是为了许多更好的目的，我
们还得走得更远些，以包括无限或极限运算。例如，大家熟悉的在数学上
极其重要的量π就在许多这类无限的表式中出现。我们有如下特例：
π=2｛(2/1)(2/3)(4/3)(4/5)(6/5)(6/7)(8/7)(8/9).｝
以及
π=4(1-1/3+1/5-1/7+1/9-1/11+.)。
（这些是著名的表式。第一式是由英国数学家、语法学家兼速算家约翰·瓦
里斯在
1655年首次得到的；而第二式实际上是苏格兰数学家兼天文学家
（以及第一台反射望远镜的发明者）詹姆斯·格里高里在
1671年得到的。）
正如π那样，以这种方法定义的数不必是有理数（也就是不具有
n/m的形
式，这里
n和
m是整数，m不为零）。为了包括这样的量，数的系统必须
被推广。
这个推广的数的系统被称为“实”数系统——就是那些可以无限小数
展开的熟悉的数，譬如
-583.70264439121009538.
按照这样的表述，π可写成众所周知的表式
π=3.14159265358979323846.
正有理数的平方根（或立方根或四次方根等等）是还能以这种方法表达的
数的类型，例如
①实际上，关于年份的通常惯例并不与此完全相符，这是因为零年被忽略去了。
或者任何正实数的平方根（或立方根等等），正如伟大的瑞士数学家列纳
多·欧拉发现的π的表示：
π=
{6(1+1 ／4 +1 ／9 +1 ／16 +1 ／25 +1 ／36 + .)}。
实数实际上是我们日常必须打交道的数的种类，虽然通常我们仅仅关
心它们的近似值，只要展开到很少的几位小数位就满意了。然而，在数学
的陈述中我们要准确地指定实数，要求某种无限的诸如整个无穷小数展开
的描述，或者也许如上述由瓦里斯、格里高里和欧拉给出的π的其他的无
限的数学表达式。（我将通常用小数展开，只是因为这些是最熟悉的。对
于数学家而言，存在不同的令人更满意的表达实数的办法，但我们在这里
不必为之忧虑。）
人们也许会感到处理全部的无限展开是不可能的。但事情并非如此。
简单的反例是
1/3=0.333333333333333.
这儿的点表明
3的序列将无限地延伸下去。为了处理这个展开，我们所需
要知道的是，只要肯定这个展开以同样的
3的方式无限地继续下去就行
了。任何有理数都有重复（或有限）的小数展开，例如
93/74=1.2567567567567567.
此处序列
567无限地重复下去，而这可以被完全地处理。而表式
0.220002222000002222220000000222222220.
定义一个无理数，也一定可以被完全处理（每一次
0序列和
2序列都增加
一位）。还能给出许多熟知的例子。在每一种情形下，只要我们知道展开
所根据的法则也就满意了。如果有某种产生连续位数的算法，则该算法就
提供我们处理整个无限小数展开的方法。其展开可被算法产生的实数称为
可计算数（还可参见第
59页）。（在这里使用十进位，而不用譬如讲二
进位展开，并没有什么深意。）刚才考虑的π和
2是可计算数的例子。
在每一种情况下，仔细叙述这些规则是稍微有些复杂，但在原则上并不难。
然而，在这个意义上还有许多不可计算的实数。我们在上一章已经看
到，存在不可计算的但仍为完好定义的序列。例如，我们可取一个小数展
开，其
n位数取
1或取
0依图灵机作用到
n时停止或不停止而定。一般地
讲，对于一个实数，我们仅仅要求必须有某种无限的小数展开。我们不要
求是否有一产生第
n位数的算法。我们甚至也不要知道在原则上实际定义
该
n位数的规则
2。可计算数是很难纠缠的东西。即使只处理可计算数，
人们也不能够使它的所有运算保持为可计算的。例如，甚至一般地去决定
两个可计算数是否相等也不是可计算的事体！由于这类原因，我们宁愿处
理所有的实数。在这里小数展开可以是任意的，而不必只是可计算序列等
等。
最后，我应指出，在结尾以无限个接续的
9和无限个接续的
0展开的
实数之间有一等同；例如
-27.1860999999.=-27.1861000000.。
有多少个实数？
有多少个实数？
前的十七世纪初叶，伟大的意大利物理学家和天文学家伽利雷·伽利略也
部分地预料到这一类思想。在第五章将会提到伽利略的其他一些成就。）
人们可用如下建立的“一一对应”的办法来显示整数和自然数具有同样的
数目：
请注意，每一整数（在左列）和每一自然数（在右列）在表中出现一次并
只有一次。在康托的理论中像这样的一一对应的存在建立了左列物体的数
目和右列的是一样的命题。这样，整数的数目的确和自然数的数目一样。
在这种情形下数目为无限，但这没关系。（发生在无限数中的仅有的古怪
事情是，我们可以从一个表上取走一些数而仍然能找到两个表之间的一一
对应！）以某种类似的但更复杂的形式，人们可在分数和整数之间建立起
一一对应（为此我们可似采用把一对自然数（分子和分母）代表为一个单
独自然数的方法；参阅第二章
47页。）可以和自然数建立一一对应关系的
整数是可列的，所有的分数也是如此。
有没有不可列的集合呢？虽然我们进行了自然数首先到整数、然后到
有理数的推广，但是我们实际上并没有增加所处理对象的总数。也许读者
已得到印象，以为所有无限集都是可列的。不对，在推广到实数时情况就
变得非常不同。康托的一个最重大的成就是，他指出了，在实际上实数比
有理数有更多的数目。康托进行论证的办法在第二章被称为“对角线删除
法”。这个方法被图灵用来表示图灵机的停机问题是不可解的。康托的论
证，正如图灵的办法，是用反证法的步骤。假定我们所要建立的结果是错
误的，也就是所有的实数的集是可列的。那么在
0和
1之间的实数肯定为
可列的，而我们存在某种列表，可将实数和自然数之间进行一一配对，譬
如
我已把对角线上的位数用黑体字写出。对于这一特殊的表，这些位数分别
为
1，4，1，0，0，3，1，4，8，5，1，.
而对角线删除步骤是（在
0和
1之间）构造一个实数，其小数展开（在小
数点后）在每一对应的位数上和这些位数都不同。为了确定起见，让我们
讲，只要对角线位数和
1不同的都为
1，而对角线位数为
1的都为
2。我们
在现在情况下就得到了
0.21211121112.
的实数。这个实数不可能出现在我们的表上。这是因为它在（小数点后的）
第一位数上和第一个数不同，在第二位数上和第二个数不同，在第三位数
上和第三个数不同等等。由于我们假定这个表包含所有在
0和
1之间的实
数，所以这是一个矛盾。这一矛盾导致我们所要证明的，也就是说，在实
数和自然数之间没有一一对应。相应地，实数的数目实际上比有理数的数
目更大，因而不是可列的。实数的数目是标为
C的无限数。（C的意思是
连续统，这是实数系统的另一名字。）人们会问，譬如讲，为何这一个数
顺便可以提及，可计算数是可列的。为了数这些数，我们只要顺序列
出那产生实数的图灵机（也就是产生实数连续位数的机器）。我们可望从
这表中除去产生任何早先出现在表中的实数的图灵机。由于图灵机是可列
的，所以可计算的实数也一定是可列的。我们为何不能把对角线删除法应
用到该表上以产生一个不在该表的新的可计算数呢？回答是基于这样的
一个事实，即我们不能一般地可计算地确定，一台图灵机是否在这表上。
为了做到这一点，事实上也就涉及到我们能够解决停机问题。有的图灵机，
可以开始产生一个实数的数位，然而停住而永远不再产生另一数位（因为
它“不停止”）。没有可计算的方法去决定哪一台图灵机会以这种方法卡
住。这基本上是停机问题。这样，我们对角步骤会产生某实数，这数不是
可计算的。这个论证事实上可用于表明不可计算数的存在。图灵用于显示
不能算法地解决的，正如在上一章所罗列的各类问题的存在，正是精确地
沿用了这种推理方法。我们在后面还会看到对角线删除法的其他应用。
实数的“实在性”
实数的“实在性”
时间、能量、温度或者许多其他几何和物理量的大小，所以被叫作“实”
的。然而在抽象定义的“实”数和物理量之间的关系，不像人们所想象的
那么一目了然。实数点被当成数学的理想化，而不是任何实际物理客观的
量。例如，实数系统具有如下物质，在任何两个实数之间必有另一个实数，
而不管该两数靠得多近。人们根本就不清楚，物理的距离或时间是否现实
上具有这一性质。如果我们不断地对分两点之间的物理距离，最后就会到
达这样微小的尺度，以至于在通常意义下的距离概念本身不再具有意义。
人们预料在次原子粒子的
10
20分之一的“量子引力”尺度下
①，这的确会
发生。但是为了和实数相匹配，我们就必须走到比它小得任意多的尺度：
例如
10
200分之一，10
2000分之一或
10
10200分之一的粒子尺度。人们一点也
