是否存在一种花砖或一组花砖，只能非周期性地镶嵌平面呢？答案是肯定
的。在图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 另一种只能非周期性地把平面镶嵌的六种花砖的集合。
① 事实上，该证明可由一系列步骤组成，这些步骤反映了直到停止以前的机器的动作。机器一旦停止则证
明即告完成。
----------------------- Page 133-----------------------
图4.12 （彭罗斯镶嵌）两对花砖，每对都只能非周期性地镶嵌平面。
还有对每对花砖镶嵌的平面区域。
图4.11 中还画出了另外一种非周期性的六种花砖的集合。这是大约在
1973年我自己沿着完全不同的思路得到的。 （在第十章中我还将提及，图
10.3 画出了用这些形状铺就的排列。）我注意到罗宾逊的非周期性的六集
合后，开始设法减少此数目；试着拼拼凑凑，能够将其减少到两个。图4.12
中画出了另个两种方案。这些完整的镶嵌显示出的必须为非周期性的花
样，具有许多显著的性质，包括了似乎在结晶学上不可能的五重对称的准
周期结构。以后我还会提及。
令人吃惊的是，数学中这么明显地 “无聊的”领域——也就是用全等
的形状去覆盖平面——初看起来像是 “小孩游戏”，实际上应该是非递归
数学的一部分。实际上，在这领域中还有许多未解决的困难问题。例如，
我们还不知道，是否存在只包括单独花砖的非周期性集合。
王浩、伯格和罗宾逊处理镶嵌问题时，所用的花砖是以方块为基础的。
我这里允许用一般形状的多边形，而且为了展现单独的花砖，人们需要某
种可胜任的计算方法。一种方法是将其顶点当成复平面上的点，也许这些
点只要是代数数就完全足够了。
----------------------- Page 134-----------------------
孟德勒伯洛特集像非递归数学吗？
让我们回到早先的关于孟德勒伯洛特集的讨论。为了阐释的目的，我
们假定，在某一适当的意义上，孟德勒伯洛特集是非递归的。由于它的补
集是递归可列的，这就表明集合本身不是递归可列的。我认为，关于非递
归集合和非递归数学方面，孟德勒伯洛特集的形式似乎对我们有许多教
益。
回到第三章遇到的图3.2。我们注意到，集合的大部分似乎都由一个
大的心状的区域所充满，在图4.13 中用A 来表示该区域。这个形状称为
心脏线，它的内部区域可以定义为阿伽德平面的点C 的集合。该集合是由
2
c=z-z
的形式产生的，z 是离原点距离小于 1/2 的复数。这一集合在早先提出的
意义上肯定是递归可列的：即存在一个算法，把它应用于区域的内部的一
点时，将会断定这一点的确是在区域的内部。很容易从上述的公式得到实
际的算法。
图4.13 可用简单的算法方程来定义孟德勒伯洛特集内部的主要部
分。
现在考虑刚好处于心脏线左边的圆盘状的区域（图4.13 中的区域B）。
它的内部区域为点
c=z-1
的集合，这儿z 离开原点距离小于 1/4。这一区域的确是圆盘的内部
——在一个准确圆的内部的点集合。这一区域又是在上面意义下递归可列
的。关于心脏线上其他“瘤”的情况又如何呢？考虑余下的两个最大的瘤。
这是大致圆形的斑点，近似地处于图3.2 心脏线的上顶和底下图4.13 中用
C ，C 表示。它们可按
1 2
3 2 2
c +2c +(1-z)c+(1-z) =0
的集合给出，这儿z 的范围是离开原点距离小于1/8 的区域。这个方程事
实上不仅为我们提供了两个斑点 （在一起的），而且还提供一个“婴儿”
心脏线形状，后者出现在图3.2 的左边的地方——也就是图3.1 的主要区
域——在图4.13 中标作C 的区域。这些 （一起或分开的）区域由于上述
3
公式的存在又组成了递归可列集。
尽管我已经做过假设，即孟德勒伯洛特集可能是非递归的，我们运用
某些定义完好的以及不过于复杂的算法，可以清理出该集合的最大面积。
这个步骤似乎应该继续下去。集合中所有最明显的、肯定占满了它面积的
绝大部分 （如果不是所有的话）的区域，可以被算法地处理。如果正如我
所设想的那样，这集合全体不是递归的，则我们的算法不能达到的区域必
----------------------- Page 135-----------------------
须是非常精巧的，并且很难找到。而且，当我们已经定位了这样的一个区
域，看看有无机会改善我们的算法，使那些特殊的区域也能达到。然而（如
果我关于非递归性的假设是正确的），还会有其他这类区域躲藏在微妙
的、复杂的、模糊的深处，甚至于用我们改善了的算法都达不到。我们再
次可能利用直觉、天才和勤奋的巨大努力，将这样的一个区域定位，但是
还会有其他的会逃脱掉，等等。
我想这就像用数学方式处理困难的问题，且假定为非递归性的。人们
在某些特别的领域遇到的最普遍问题可由简单的算法步骤——甚至是已经
知道了几世纪的步骤来解决。但是其中仍有漏网之鱼，要掌握它们就需要
更复杂的步骤。漏网之鱼当然特别刺激数学家们，并促使他们去发展更为
有力的方法。这些必须是基于对涉及的数学性质的越来越深刻的洞察之
上。在我们对物理世界的理解中也许存在某些这种东西。
在上面考虑的词语及镶嵌问题中，人们可以对这一类事稍有了解 （虽
然在这些领域中数学工具还未发展得非常远）。我们在一个非常特殊的情
形下能用非常简单的论证去显示，某一词不能用允许的规则从另一词得
到。不难想象，更复杂得多的推理可在处理更古怪的情形时起作用。很可
能这些新的推理可发展成算法步骤。我们知道，不存在一个可以足够应付
词语问题的所有情况的步骤，但是逃脱的例子需要非常仔细和精巧地去构
造。的确，只要我们肯定知道躲开我们算法的例子，只要我们知道如何构
造这些例子，则我们可以改善我们的算法以包括这种情形。只有不“相等”
的配对词会逃脱，故一旦我们知道它们逃脱，我们就知道它们不“相等”，
这一事实可添加到我们算法上去。我们改善了的洞察就导致一个改善了的
算法！
----------------------- Page 136-----------------------
复杂性理论
我在前面以及上一章关于算法的性质、存在和局限的论证是处于非常
“原则的”水平上。我根本就没有讨论到出现的算法是否在任何方面像是
可行的。即使对于算法存在并且该算法如何构造都很清楚的问题，也还需
要许多才干和勤勉，才能将此算法发展成有用的东西。有时小小的洞察和
才干就能可观地降低算法的复杂性，以及有时极大地加快其速度。这些问
题经常是非常细节和技术性的。近年人们在构造、理解和改善算法方面，
在不同的情况下做了大量的工作。这是一个快速扩大和发展的研究领域。
我不想对这些问题进行细致的讨论。然而，有关算法的速度可被增加的某
一绝对的极限有各种普遍知道或猜测的东西。人们发现，甚至在具有算法
性质的数学问题中，也存在种种内在地比其他问题更难于算法地解决的问
题。困难的问题只能用非常慢的算法 （或许，需要非同寻常地大量的存储
空间等）来解。有关这类问题的理论称为复杂性理论。
复杂性理论并不这么关心算法地解决单独问题的困难，而是关心无限
个问题的族，找到解决一个单独族的所有问题的一般算法。族中的不同问
题会有不同的 “尺度”。问题的尺度是由某一自然数n来测量。 （关于这
一个数n 实际上如何表征问题的尺度，我一会儿还要再说。）算法对于每
类中的每一特别问题所需的时间长度——或更正确地说，基本步骤的数目
——是依赖于 n 的某一自然数N。稍微精确一点讲，我们讲在所有具有某
一特别尺度n 的问题中算法采用的最大的步骤数目为N。现在，当n 变得
越来越大，N 也似乎变得越来越大。事实上，N似乎增加得比 n快速得多。
2 3 n 2 3
例如，N 可以近似地和n ，n 或许2 成比例 （对于大的n，它比n，n ，n ，
4 5 r
n 以及n 中的每一个都大多了，甚至比带有任何固定指数r 的n 都大），
或者譬如讲N 甚至近似地和22n （这又更大得多）成比例。
当然，这些 “步骤”的数目可依赖于实现该算法的电脑的类型。如果
电脑为第二章描述的图灵机，那儿只有一盘磁带——这是相当低效率的—
—那数目 N 就会比允许两盘或三盘磁带的增加得更快速 （也就是说机器会
运行得更慢）。为了避免这类不定性，按照N作为 n 的函数增加的可能方
式进行了宽广的分类，使得不管使用何种类型的图灵机，N 的增加率的度
量总是归到同一分类中去。一种称为P （说明“多项式时间”的分类包括
2 3 4 5 ①
了所有最多为n，n ，n ，n ，n ，…中的一个的固定倍数 的速率。也就
是说，对P分类中的任何问题 （这里我的“问题”的真正含义是具有解决
它们的一个一般算法的一族问题），我们有
r
N≤K×n ，
① 这是在39 页提到的希尔伯特第十问题的负面答案。 （例如，参见德弗林1988。）这里变量的个数是不
受限制的。然而人们知道，为了使这种非算法性质成立，实际上需要变量的个数不超过九就可以。
----------------------- Page 137-----------------------
这儿 K和 r为常数 （与n 无关）。这表明N 不比n 的某一固定方次的某一
倍数更大。
两个数相乘肯定是属于P 问题的简单类型。为了解释这一点，我必须
首先描述数目n如何表征一对特殊乘数的尺度。我们可以想象每一个数都
以二进位写出，而每一个数的二进位位数简单地为n/2，总共给出了n 二
进位数——也就是总共 n 比特。 （如果一个数比另一个短，可以简单地从
短的开始连续地在前头加上零使之和长的具有一样的长度。）例如，如果
n=14，我们可以考虑
1011010×0011011
（就是1011010×11011，但是在短的数上添了一些零）。最直接进行乘法
的方式是只要写出：
记住，在二进位系统中，0×0=0，0×1=0，1×0=0，1×1=1，0+0=0，0+1=1，
2
1+0=1，1+1=10。单独二进位乘法的次数为(n/2)×(n/2）=n /4，并且可具
2
有(n/4-(n/2)次的单独的二进位加法 （包括移位）。这样，总共有
2
(n/2)-(n/2)次的单独算术运算——我们必须包括一些涉及到移位的额外
2 13
的逻辑步骤。总的步骤数为N=n /2 （忽略低阶项），这肯定是多项式的 。
一般来说，对于一族问题，我们取这问题的 “尺度”的测度n 为需要
指明该特别尺度的问题的自由数据所需要的二进位位数 （或比特）的总
n
数。这意味着，对于给定的n，在给定的尺度下问题会有多到2 种不同的
情形 （因为每一位可有两种可能性中的任一个，0 或 1，而总共有n位数），
而这些都必须由算法在不多于N 步骤下被一致地处理好。
存在许多不属于 P 问题 （的族）的例子。例如，为了进行从自然数r
计算22 r ]的运算，甚至只要写出这一答案就大约需要2n 步骤，且不说进
r
行计算了。n为在r的二进位表示中的位数。计算222 的运算，只要写下就
需要22r 步骤等等！这些比多项式大多了，所以肯定不在P中！
在多项式时间内可以写下答案并甚至能检查正确与否的问题更为有
趣。由此性质表征的 （可算法地解出的）问题（的族）是一个重要的范畴。
它们被称为NP 问题 （的族）。更精确地讲，如果在NP 中的问题的族的个
别问题有一解，那么该算法将给出这个解，并且它必须能在多项式时间内
检验所设想的解确实是一个解。在问题没有解的情形下，算法会告诉我们
这个，人们不必在多项式或别的时间内去检验的确没有解 14。
----------------------- Page 138-----------------------
NP 问题既在数学本身，也在实在世界的许多范围内出现。我只给出一
个简单的数学例子：在一个图中寻找所谓的 “哈密顿线路”的问题（一个
极简单思想的吓唬人的名字）。用 “图”来表示点或“顶点”的有限集合，
一定数目的点对由称为图的 “边缘”的线连接起来。（我们在这儿并不对
几何或 “距离”性质感兴趣，只对由哪一顶点连接到哪一顶点感兴趣。这
样，所有顶点是否在一个平面上表出是无关紧要的，我们的边缘是否互相
穿越还是处于三维空间中都是无所谓的。）哈密顿线路简单地就是一个只
包括图的边缘的闭合圈，其中每一顶点只刚好通过一次。图 4.14 中画出了
一个在上面标出哈密顿线路的图。哈密顿线路问题是去决定，对于任何给
定的图是否存在哈密顿线路，只要存在就把它明了地画出来。
图4.14 带有 （用稍粗一些的黑线）标出的哈密顿线路的一个图。还只
存在另一条哈密顿线路，读者也许介意把它找出来。
可以按二进位用不同方式来表述一个图。用何种方法关系不大。一个
步骤是给顶点编上号 1，2，3，4，5，…，然后以某种适当的固定顺序列
出成对的顶点来：
(1，2)，(1，3)，(2，3)，(1，4)，(2，4)，(3，4)，(1，5)，(2，
5)，(3，5)，(4，5)，(1，6)，…
然后我们做一个准确的0 和 1 的搭配的表，当一对顶点对应于图的一个边
缘时写上 1，否则写0。这样二进位序列
10010110110…
表明顶点 1接到顶点 2、顶点4 以及顶点5，…顶点3接到顶点4 和顶点
