些不精确。我把诸如 “递归可列的”和“递归的”这样的术语应用于阿伽
德平面也就是复数的集合上。严格地讲，这些术语只能适用于自然数或其
他可列的集合。我们已经在第三章 （98 页）看到实数是不可列的，所以复
数也不是可列的——由于实数可考虑作特殊种类的复数，也就是虚部为零
的复数。事实上，刚好存在和实数 “一样多”数目的复数，也就是C 那么
----------------------- Page 126-----------------------
多。 （粗略地讲，为了建立复数和实数之间的一一对应，我们可以把每一
复数的实虚部各作小数展开，然后将其交叉地塞到相应实数的奇数和偶数
位上去：例如复数 3.6781…+i512.975…对应于实数50132.6977851…。）
逃避这个问题的一种办法是只管可计算的复数。我们在第三章看到，
可计算的实数——并因此可计算的复数——的确是可列的。然而，这里有
严重的困难：事实上不存在决定两个按照它们相应的算法给出的可计算数
是否相等的一般算法！ （我们可以算法地形成它们的差，但我们不能算法
地决定这个差是否为0。想象两个分别产生0.99999…和1.00000…的算
法，我们也许永远不会知道这些9和0 是否无限地继续下去，因此这两个
数相等，或最终某些其他的数会出现，因此这两个数不等。）这样，我们
也许永远不能知道这些数是否相等。其中的一个含义是，甚至对诸如阿伽
德平面上的单位圆盘这么简单的集合 （所有到原点的距离不大于一个单位
的点的集合，也就是图4.4 中的黑的区域）都没有决定复数是否实际上处
于圆上的算法。当点在内部 （或在外部）时不会引起这个问题，但点处于
圆盘的边缘时，也就是在单位圆本身上时就有了问题。单位圆被认为是圆
盘的部分。假定我们简单地给出产生某复数的实部和虚部的位数的算法。
如果我们怀疑该复数实际上处于单位圆上，我们并不能肯定这个事实。不
存在去决定可计算数
2 2
x +y
是否实际上等于或不等于 1 的算法，也就是决定该可计算复数x+iy 是否在
单位圆上的判据。
图4.4 单位圆盘肯定被当作 “递归的”，但是这里需要一个适当的观
点。
这肯定不是我们所需要的。单位圆盘当然必须被当作递归的！没有很
多集合比单位圆盘更简单！一种躲避这一问题的办法是不理睬边界。对实
际上处于内部或外部的点肯定存在确认这些事实的算法。 （简单地一个接
2 2
一个地产生x +y 的数位，最终会发现在小数展开0.99999…后面出现非9
或 1.00000…后面出现非0）。在这个意义上讲，单位圆盘是递归的。但是，
这种观点是相当粗劣的，因为人们经常需要按照在边界上的行为来进行论
证。另一方面，这种观点或许对物理学是合适的。我们以后还要再考虑这
些问题。
人们或许还会采用另一种紧密相关的观点，它根本未涉及可计算复数
的问题。我们简单地要求可对给定的复数决定其是否在该集中或在补集中
的算法，而不试图去列举该问题的集外或集内的复数。我在这里的“给定”
的意义是，对于我们检验的每一个复数，也许用某种魔术的办法，实部和
虚部的连续位数可一个接一个地写出以供使用，要多长就有多长。我不要
----------------------- Page 127-----------------------
求存在任何已知或未知的把这些位数写出来的算法。对于一个复数的集
合，如果存在一个单独的算法，使得只要并且只要一个复数实际上在此集
中，一旦该数以这种方法用一串数位写出，就在有限的步骤后它最终会说
“是”，则该集合被认为是“递归可列的”。和上面提出的第一种观点一
样，这种观点 “不理睬”边界。这样，单位圆盘的内部和外部分别都在这
个意义上被当作递归可列的，而边界本身不是。
我一点也不清楚，这些观点是否真正必需 10。把它应用到孟德勒伯洛
特集时， “不理睬边界”的哲学可能将该集合的许多复杂性都损失了。该
集合一部分包括具有内部区域的 “点”，还有部分是 “卷须”。其极端复
杂性似乎存在于极其剧烈地弯曲的卷须之中。然而，卷须不在集合的内部，
所以如果我们采用了上述的任一种哲学，则这些卷须都被忽略了。尽管如
此，当只考虑斑点时，仍然不清楚孟德勒伯洛特集是否为 “递归的”。这
个问题似乎依赖于某个未被证明的有关孟德勒伯洛特集的猜测：它是所谓
的 “局部连通”的吗？我不想在此解释此术语的意义及其关联之处。我只
想指出这些是困难的问题，它们引起了有关孟德勒伯洛特集的未解决的问
题，而且其中一些正是当前某些数学研究的最前沿的问题。
为了绕过复数是不可列的问题，人们还可以采用其他的观点。人们不
去考虑所有可计算的复数，而去考虑这样的一个适当的子集，该子集的数
具有去决定其中两个数相等与否仍是可计算的问题的性质。 “有理”复数
即为这样的一种简单的子集，实部和虚部均为有理数的复数即为有理复
数。我认为它并不在孟德勒伯洛特集中占多少，而这种观点又是非常局限
的。考虑代数数也许会更令人满意些——这就是那些为整系数的代数方程
的解的那些复数。例如，方程
7 5 4 3
129z －33z +725z +16z －2z－3=0
所有 z 的解为代数数。代数数是可列的并且是可计算的。实际上去决定它
们中的两个是否相等正是可计算的问题。 （它们其中许多处于单位圆的边
界和孟德勒伯洛特集的须蔓上。）如果需要的话，我们可把这问题表述成，
孟德勒伯洛特集按照它们是否为递归的。
在刚才考虑的两个集合的情况下代数数也许是合适的，但它实在不能
一般地解决我们所有的困难。考虑由关系
y≥ex
所定义的集合（图4.5 中的黑的区域）。这里 z=x+iy 是阿伽德平面上的点。
按照上面所表述的任何观点，该集合的内部以及其补集的内部，都是递归
x
可列的。但是 （从F ·林德曼在1882年证明的一个著名定理）边界y=e ，
只包含一个代数点，即z=i。代数数对于这种情形下的边界的算法性质的
研究毫无用处！不难去寻找其他的可计算数的子集以对付这特殊情形，但
人们会强烈地感到，我们还没得到正确的观点。
----------------------- Page 128-----------------------
x
图4.5 由指数关系y＞e 定义的集合也必须被当作 “递归的”。
----------------------- Page 129-----------------------
一些非递归数学的例子
在许多数学分枝中产生了非递归的问题。也就是说，我们会遇到一系
列的问题，它们答案或者为 “是”或者为“非”，但是不存在决定究竟是
什么答案的一般算法。在这类问题中有一些显得非常简单。
首先考虑求整系数代数方程组的整数解的问题。这种方程称为丢番都
方程 （以希腊数学家丢番都来命名，他的生活年代为公元前三世纪，他研
究了这一类方程）。这样的一组方程可为
3 2 2
z －y－1=0，yz －2x－2=0，y －2xz+1=0，
问题在于决定它们是否有x，y，z 的整数值的解。在给定的特殊情况下，
事实上存在
X＝13，y＝7，z＝2
①
的解。然而，不存在决定任意丢番都方程集合 的这一问题的算法：尽管丢
番都算术是这么初等，它却是非算法数学的一部分！
（另一个稍微高等的例子是流形的拓朴等价。这里我仅仅简略地提
及，因为它和第八章要讨论的问题有某种可以预料到的相关性。为了理解
何为 “流形”，先考虑一个线圈，它是仅仅为一维的流形。然后考虑一个
闭合面，这是二维的流形。再摹想具有三维或更高维的 “表面”。两个流
形的 “拓朴等价”表明其中一个可以连续运动地变形成另一个——不能撕
裂，也不能粘住。这样，一个球面和一个立方体的表面就是拓朴等价的，
同时它们和一个环或茶杯的表面不是拓朴等价的——后两者实际上是相
互拓朴等价的。现在，对于二维流形，存在一种决定其是否拓朴等价的算
法——事实上可归结为计算每一曲面所具有 “把柄”的数目。在写此书时，
对于三维这问题的答案还没有得到，但是对于四维或更高维的情况，已经
知道不存在决定等价类的算法。四维情形和物理有些相关是可以理解的。
这是由于按照爱因斯坦的广义相对论，空间和时间一起组成了一个四流形
（见第五章238 页）。格罗许和哈特尔在1987年提出，这个非算法性质可
能和 “量子引力”有关；还可参阅第八章。）
现在我们考虑一个被称作词语问题 11 的不同种类的问题。假定我们有
某些符号字母，考虑把这些符号连成各种称作词的串。词本身可以不具有
意义，但是我们有一张 （有限的）在它们之间“等价”的表，可用此表来
推导出更多这样的 “等价”。这可以用如下办法做到，在较长的词中找出
和表中某个词相同的部分，这一部分可用表中认为是相等的另一个词来取
代。现在问题就归结为，对某一对给定的词，按照这些规则决定它们是否
“相等”。
① 允许发生这种不幸的可能性实际上是重要的，这样使得能有描述任何算法运算的潜力。我们记得，为了
一般地描述图灵机，我们必须允许实际上永远不停止的图灵机。
----------------------- Page 130-----------------------
例如，我们原始的表为
EAT=AT
ATE=A
LATER=LOW
PAN=PILLOW
CARP=ME。
例如，从这些我们可以推出
LAP=LEAP
这可由连续地利用原表中的第二、第一以及再次第二个关系而得到：
LAP=LATEP=LEATEP=LEAP。
现在的问题在于，给定某一对词，我们能简单地用这种叠代法从一个
词得到另一个词吗？例如，我们能从CATERPILLAR得到 MAN，或从CARPET
得到 MEAT 吗？在第一种情形下的答案恰好为“是”，而在第二种情况下则
为 “非”。当答案为“是”时，通常显示这一点的方法是简单地写出一串
等式，每一个词都是用允许的关系从前面的词得出。这样 （要改变的字母
用粗体印出，刚被置换的用斜体印出）：
CATERPILLAR=CARPILLAR=CARPILLATER=CARPILLOW=CARPAN=EAN=MEATE
N=MATEN=MAN按照允许的法则，我们何以得知不能从CARPET得到MEAT呢？
对此问题，我们要稍微多想片刻，但是用各种不同的方法不难看到。最简
单的方法如下：在我们原始表上的每个 “等式”中，A 加上W 再加M 出现
的总次数在两边是相等的。这样，在所有允许替代的系列中A，W 和M 的总
数目不应改变。然而，对于CARPET这个数为 1，而 NEAT 为 2。所以靠允
许的替换不可能从CARPET得到 MEAT。
请注意，当两个词 “相等”时，我们可简单地使用所给定的规则，写
出一串允许的形式符号串来显示这一点；而在 “不相等”的情形，我们必
须求助于关于给定规则的论证。只要两个词事实上是 “相等”的时候，我
们就有清楚的算法可用来在它们之间建立起 “相等”。我们所要做的是，
把所有可能的词的序列作字典式的列表。如果序列中含有接连的两个词，
其中第二个词不能按允许的规则从第一个词得出的，就从这表中删去这样
的序列。余下的序列就提供了所有要寻找的词之间的 “等价类”。然而，
一般地不存在这样明显的算法，它能决定两个词不 “相等”。为了建立这
个事实，我们必须求助于 “智慧”。（我的确花了好一阵时间才注意到上
面的 “技巧”，它可用来建立CARPET 和MEAT 的不 “相等”。对于其他例
子，也许需要完全不同的 “技巧”。顺便提及，对于建立“等式”的存在，
智慧虽然不是必要的，却是有助的。）
事实上，在上述情况中对于包含五个 “等式”的特殊的表，当两个词
的确 “不等”时，提供一种去确定其 “不等”的算法并不特别困难。但是，
为了找到对这种情况起作用的算法，我们必须使用一些的智慧！人们发
----------------------- Page 131-----------------------
现，并不存在任何单独算法可普遍地应用于所有原始表的选择。在这个意
义上讲，词语问题不存在算法解。一般词语问题是属于非递归数学的范畴！
甚至对于某种特别选取的初始表，不存在决定两个词语何时不相等的
算法。其中一例便是
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 ·冯德堡的更早的形状。
值得注意的是，用这种花砖既可以构成周期性的也可以构成非周期性的镶
嵌。许多其他单独花砖形状和花砖集合也具有这种性质。现在我们要问，
----------------------- Page 132-----------------------
