图
图系
y＞e
x定义的集合也必须被当作“递归的”。
一些非递归数学的例子
一些非递归数学的例子
列的问题，它们答案或者为“是”或者为“非”，但是不存在决定究竟是
什么答案的一般算法。在这类问题中有一些显得非常简单。
首先考虑求整系数代数方程组的整数解的问题。这种方程称为丢番都
方程（以希腊数学家丢番都来命名，他的生活年代为公元前三世纪，他研
究了这一类方程）。这样的一组方程可为
z3－y－1=0，yz
2－2x－2=0，y
2－2xz+1=0，
问题在于决定它们是否有
x，y，z的整数值的解。在给定的特殊情况下，
事实上存在
X＝13，y＝7，z＝2
的解。然而，不存在决定任意丢番都方程集合①的这一问题的算法：尽管丢
番都算术是这么初等，它却是非算法数学的一部分！
（另一个稍微高等的例子是流形的拓朴等价。这里我仅仅简略地提
及，因为它和第八章要讨论的问题有某种可以预料到的相关性。为了理解
何为“流形”，先考虑一个线圈，它是仅仅为一维的流形。然后考虑一个
闭合面，这是二维的流形。再摹想具有三维或更高维的“表面”。两个流
形的“拓朴等价”表明其中一个可以连续运动地变形成另一个——不能撕
裂，也不能粘住。这样，一个球面和一个立方体的表面就是拓朴等价的，
同时它们和一个环或茶杯的表面不是拓朴等价的——后两者实际上是相
互拓朴等价的。现在，对于二维流形，存在一种决定其是否拓朴等价的算
法——事实上可归结为计算每一曲面所具有“把柄”的数目。在写此书时，
对于三维这问题的答案还没有得到，但是对于四维或更高维的情况，已经
知道不存在决定等价类的算法。四维情形和物理有些相关是可以理解的。
这是由于按照爱因斯坦的广义相对论，空间和时间一起组成了一个四流形
（见第五章
238页）。格罗许和哈特尔在
1987年提出，这个非算法性质可
能和“量子引力”有关；还可参阅第八章。）
现在我们考虑一个被称作词语问题
11的不同种类的问题。假定我们有
某些符号字母，考虑把这些符号连成各种称作词的串。词本身可以不具有
意义，但是我们有一张（有限的）在它们之间“等价”的表，可用此表来
推导出更多这样的“等价”。这可以用如下办法做到，在较长的词中找出
和表中某个词相同的部分，这一部分可用表中认为是相等的另一个词来取
代。现在问题就归结为，对某一对给定的词，按照这些规则决定它们是否
“相等”。
①允许发生这种不幸的可能性实际上是重要的，这样使得能有描述任何算法运算的潜力。我们记得，为了
一般地描述图灵机，我们必须允许实际上永远不停止的图灵机。
例如，我们原始的表为..
例如，我们原始的表为..
T
ATE=A
LATER=LOW
PAN=PILLOW
CARP=ME。
例如，从这些我们可以推出..
LAP=LEAP
这可由连续地利用原表中的第二、第一以及再次第二个关系而得到：
LAP=LATEP=LEATEP=LEAP。
现在的问题在于，给定某一对词，我们能简单地用这种叠代法从一个
词得到另一个词吗？例如，我们能从.. CATERPILLAR得到.. MAN，或从.. CARPET
得到.. MEAT吗？在第一种情形下的答案恰好为“是”，而在第二种情况下则
为“非”。当答案为“是”时，通常显示这一点的方法是简单地写出一串
等式，每一个词都是用允许的关系从前面的词得出。这样（要改变的字母
用粗体印出，刚被置换的用斜体印出）：..
CATERPILLAR=CARPILLAR=CARPILLATER=CARPILLOW=CARPAN=EAN=MEATEN=MATEN=MAN按照允许的法则，我们何以得知不能从CARPET得到MEAT呢？
对此问题，我们要稍微多想片刻，但是用各种不同的方法不难看到。最简
单的方法如下：在我们原始表上的每个“等式”中，A加上.. W再加.. M出现
的总次数在两边是相等的。这样，在所有允许替代的系列中.. A，W和.. M的总
数目不应改变。然而，对于.. CARPET这个数为.. 1，而 NEAT为 2。所以靠允
许的替换不可能从.. CARPET得到.. MEAT。
请注意，当两个词“相等”时，我们可简单地使用所给定的规则，写
出一串允许的形式符号串来显示这一点；而在“不相等”的情形，我们必
须求助于关于给定规则的论证。只要两个词事实上是“相等”的时候，我
们就有清楚的算法可用来在它们之间建立起“相等”。我们所要做的是，
把所有可能的词的序列作字典式的列表。如果序列中含有接连的两个词，
其中第二个词不能按允许的规则从第一个词得出的，就从这表中删去这样
的序列。余下的序列就提供了所有要寻找的词之间的“等价类”。然而，
一般地不存在这样明显的算法，它能决定两个词不“相等”。为了建立这
个事实，我们必须求助于“智慧”。（我的确花了好一阵时间才注意到上
面的“技巧”，它可用来建立.. CARPET和.. MEAT的不“相等”。对于其他例
子，也许需要完全不同的“技巧”。顺便提及，对于建立“等式”的存在，
智慧虽然不是必要的，却是有助的。）
事实上，在上述情况中对于包含五个“等式”的特殊的表，当两个词
的确“不等”时，提供一种去确定其“不等”的算法并不特别困难。但是，
为了找到对这种情况起作用的算法，我们必须使用一些的智慧！人们发
现，并不存在任何单独算法可普遍地应用于所有原始表的选择。在这个意
义上讲，词语问题不存在算法解。一般词语问题是属于非递归数学的范畴！
现，并不存在任何单独算法可普遍地应用于所有原始表的选择。在这个意
义上讲，词语问题不存在算法解。一般词语问题是属于非递归数学的范畴！
是
AH=HA
OH=HO
AT=TA
OT=TO
TAI=IT
HOI=IH
THAT=ITHT。
（这表采用自
G．S．蔡亭和丹娜·斯各特(1955)；参阅伽特纳
1958，
第
144页。）这样，这个特殊的词语问题本身就是一个非递归数学的例子。
也就是说，利用这张特殊的初始表，我们不能算法地决定两个给定的词是
否“相等”。
从形式化数学逻辑的考虑（正如我们早先考虑过的“形式系统”等等）
中产生了一般的词语问题。初始表起着公理系统的作用，词的替代规则起
着步骤的形式法则的作用。从这种考虑引起了词语问题的非递归性的证
明。
作为非递归数学问题的最后一个例子，现在我们考虑一个用多边形来
覆盖欧几里德平面的问题。这里我们只允许用有限种不同形状的花砖，看
看是否能将整个平面既没有裂缝又没有重叠地覆盖住。这种用多边形来铺
满平面的方法称为平面的镶嵌。我们都对如下事实很熟悉，可以只用正方
形或正三角形或正六边形来镶嵌（正如第十章图
10.2所示的），但是不能
只用正五边形。还有许多其他的单独形状可以用来镶嵌平面，正如画在图
4.6中的两种不规则五边形。用两个形状来镶嵌，结果就更精巧。图
4.7
画出了两个简单的例子。迄今为止所有的例子都具有称为周期性的性质。
这表明它们在两个独立的方向上完全重复。按照数学语言，我们说存在一
个周期的平行四边形——一个平行四边形，如果我们用某种方法将其标
出，并在平行于它的边的两个方向上不断地重复，则能重新产生给定的镶
嵌花样。图
4.8即为一个例子，在左面画出了用刺状的花砖进行的周期镶
嵌，而在右面则画出与此周期性镶嵌相关的周期平行四边形。
存在许多不是周期性的平面镶嵌。图
4.9画出了三种，这是用图
4.8
所示的同一种刺状花砖组成的非周期性的“螺旋”状镶嵌。这一种特别的
花砖形状（由于明显的原因）被叫做“万能的”，它是由
B·格吕堡和
G.C.
谢发德设计的(1981，1987)，这明显地是基于
H·冯德堡的更早的形状。
值得注意的是，用这种花砖既可以构成周期性的也可以构成非周期性的镶
嵌。许多其他单独花砖形状和花砖集合也具有这种性质。现在我们要问，
是否存在一种花砖或一组花砖，只能非周期性地镶嵌平面呢？答案是肯定
的。在图
4.10中我画出了一族由美国数学家拉飞逸·罗宾逊(1971)建造的
六个花砖，它们只能够非周期性地镶嵌整个平面。
图
4.6平面周期镶嵌的两个例子，每一种情形都只用单独的花砖(1976
年由马约里·赖斯发现)。
图
4.7平面周期镶嵌的两个例子，每一种情形都用两种花砖。
图
4.8一个周期性镶嵌，并标出和它的周期平行四边形的关系。
值得稍微了解一下这种非周期性的花砖族由来的历史。（参阅格吕堡
和谢发德
1987）。1961年美籍华人逻辑学家王浩提出了对于镶嵌问题是否
存在一个决定步骤的问题，也就是说，是否存在一种算法，它可以决定给
定的不同多边形的有限集合能否将整个平面镶嵌①！他指出，如果每一个
以某种方式镶嵌平面的不同花砖的集合，还能把这平面周期性地镶嵌的
话，则的确存在这样的决定步骤。我想，可能那时人们感到，不太会有违
反这种条件的集合——亦即会存在“非周期性”的花砖集合。然而，1966
年在王浩的建议指导下，罗伯特·伯格能够指出，镶嵌问题的决定步骤实
际上不存在：镶嵌问题也是非递归数学的一部分
12！
图
4.9三个非周期性的“螺旋”镶嵌，使用了图
4.8中的同样的“万
能”的形状。
这样，我们从王浩的早期结果得知。必然存在非周期性的花砖集合，
而且伯格也确实找到了第一族非周期性花砖。但是，由于这些论证脉络之
复杂性，他的集合涉及到了非同小可的大数目的不同花砖——最初有
20426个。伯特又用了许多技巧才将其数目减少到
104个。然后到
1971年，
拉飞逸·罗宾逊将此数目减少到图
4.10所示的六个。
图
4.10拉飞逸·罗宾逊的只能把平面非周期性镶嵌的六种花砖。
图
4.11另一种只能非周期性地把平面镶嵌的六种花砖的集合。
①事实上，该证明可由一系列步骤组成，这些步骤反映了直到停止以前的机器的动作。机器一旦停止则证
明即告完成。
图
图
图
4.11中还画出了另外一种非周期性的六种花砖的集合。这是大约在
1973年我自己沿着完全不同的思路得到的。（在第十章中我还将提及，图
10.3画出了用这些形状铺就的排列。）我注意到罗宾逊的非周期性的六集
合后，开始设法减少此数目；试着拼拼凑凑，能够将其减少到两个。图
4.12
中画出了另个两种方案。这些完整的镶嵌显示出的必须为非周期性的花
样，具有许多显著的性质，包括了似乎在结晶学上不可能的五重对称的准
周期结构。以后我还会提及。
令人吃惊的是，数学中这么明显地“无聊的”领域——也就是用全等
的形状去覆盖平面——初看起来像是“小孩游戏”，实际上应该是非递归
数学的一部分。实际上，在这领域中还有许多未解决的困难问题。例如，
我们还不知道，是否存在只包括单独花砖的非周期性集合。
王浩、伯格和罗宾逊处理镶嵌问题时，所用的花砖是以方块为基础的。
我这里允许用一般形状的多边形，而且为了展现单独的花砖，人们需要某
种可胜任的计算方法。一种方法是将其顶点当成复平面上的点，也许这些
点只要是代数数就完全足够了。
孟德勒伯洛特集像非递归数学吗？
孟德勒伯洛特集像非递归数学吗？
回到第三章遇到的图
3.2。我们注意到，集合的大部分似乎都由一个
大的心状的区域所充满，在图
4.13中用
A来表示该区域。这个形状称为
心脏线，它的内部区域可以定义为阿伽德平面的点
C的集合。该集合是由
c=z-z2
的形式产生的，z是离原点距离小于
1/2的复数。这一集合在早先提出的
意义上肯定是递归可列的：即存在一个算法，把它应用于区域的内部的一
点时，将会断定这一点的确是在区域的内部。很容易从上述的公式得到实
际的算法。
图
4.13可用简单的算法方程来定义孟德勒伯洛特集内部的主要部
分。
现在考虑刚好处于心脏线左边的圆盘状的区域（图
4.13中的区域
B）。
它的内部区域为点
c=z-1
的集合，这儿
z离开原点距离小于
1/4。这一区域的确是圆盘的内部
——在一个准确圆的内部的点集合。这一区域又是在上面意义下递归可列
的。关于心脏线上其他“瘤”的情况又如何呢？考虑余下的两个最大的瘤。
这是大致圆形的斑点，近似地处于图
3.2心脏线的上顶和底下图
4.13中用
C1，C
2表示。它们可按
c3+2c2+(1-z)c+(1-z)2=0
的集合给出，这儿
z的范围是离开原点距离小于
1/8的区域。这个方程事
实上不仅为我们提供了两个斑点（在一起的），而且还提供一个“婴儿”
心脏线形状，后者出现在图
3.2的左边的地方——也就是图
3.1的主要区
域——在图
4.13中标作
C
3的区域。这些（一起或分开的）区域由于上述
公式的存在又组成了递归可列集。
尽管我已经做过假设，即孟德勒伯洛特集可能是非递归的，我们运用
某些定义完好的以及不过于复杂的算法，可以清理出该集合的最大面积。
这个步骤似乎应该继续下去。集合中所有最明显的、肯定占满了它面积的
绝大部分（如果不是所有的话）的区域，可以被算法地处理。如果正如我
所设想的那样，这集合全体不是递归的，则我们的算法不能达到的区域必
须是非常精巧的，并且很难找到。而且，当我们已经定位了这样的一个区
域，看看有无机会改善我们的算法，使那些特殊的区域也能达到。然而（如
果我关于非递归性的假设是正确的），还会有其他这类区域躲藏在微妙
的、复杂的、模糊的深处，甚至于用我们改善了的算法都达不到。我们再
次可能利用直觉、天才和勤奋的巨大努力，将这样的一个区域定位，但是
还会有其他的会逃脱掉，等等。
须是非常精巧的，并且很难找到。而且，当我们已经定位了这样的一个区
域，看看有无机会改善我们的算法，使那些特殊的区域也能达到。然而（如
果我关于非递归性的假设是正确的），还会有其他这类区域躲藏在微妙
的、复杂的、模糊的深处，甚至于用我们改善了的算法都达不到。我们再
次可能利用直觉、天才和勤奋的巨大努力，将这样的一个区域定位，但是
还会有其他的会逃脱掉，等等。
在上面考虑的词语及镶嵌问题中，人们可以对这一类事稍有了解（虽
然在这些领域中数学工具还未发展得非常远）。我们在一个非常特殊的情
形下能用非常简单的论证去显示，某一词不能用允许的规则从另一词得
到。不难想象，更复杂得多的推理可在处理更古怪的情形时起作用。很可
能这些新的推理可发展成算法步骤。我们知道，不存在一个可以足够应付
词语问题的所有情况的步骤，但是逃脱的例子需要非常仔细和精巧地去构
造。的确，只要我们肯定知道躲开我们算法的例子，只要我们知道如何构
造这些例子，则我们可以改善我们的算法以包括这种情形。只有不“相等”
的配对词会逃脱，故一旦我们知道它们逃脱，我们就知道它们不“相等”，
这一事实可添加到我们算法上去。我们改善了的洞察就导致一个改善了的
算法！
复杂性理论
复杂性理论
复杂性理论并不这么关心算法地解决单独问题的困难，而是关心无限
个问题的族，找到解决一个单独族的所有问题的一般算法。族中的不同问
题会有不同的“尺度”。问题的尺度是由某一自然数
n来测量。（关于这
一个数
n实际上如何表征问题的尺度，我一会儿还要再说。）算法对于每
类中的每一特别问题所需的时间长度——或更正确地说，基本步骤的数目
——是依赖于
n的某一自然数
N。稍微精确一点讲，我们讲在所有具有某
一特别尺度
n的问题中算法采用的最大的步骤数目为
N。现在，当
n变得
越来越大，N也似乎变得越来越大。事实上，N似乎增加得比
n快速得多。
例如，N可以近似地和
n
2，n
3或许
2
n成比例（对于大的
