按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
0…后面出现非0）。在这个意义上讲，单位圆盘是递归的。但是，这种观点是相当粗劣的，因为人们经常需要按照在边界上的行为来进行论证。另一方面，这种观点或许对物理学是合适的。我们以后还要再考虑这些问题。人们或许还会采用另一种紧密相关的观点，它根本未涉及可计算复数的问题。我们简单地要求可对给定的复数决定其是否在该集中或在补集中的算法，而不试图去列举该问题的集外或集内的复数。我在这里的“给定”的意义是，对于我们检验的每一个复数，也许用某种魔术的办法，实部和虚部的连续位数可一个接一个地写出以供使用，要多长就有多长。我不要求存在任何已知或未知的把这些位数写出来的算法。对于一个复数的集合，如果存在一个单独的算法，使得只要并且只要一个复数实际上在此集中，一旦该数以这种方法用一串数位写出，就在有限的步骤后它最终会说“是”，则该集合被认为是“递归可列的”。和上面提出的第一种观点一样，这种观点“不理睬”边界。这样，单位圆盘的内部和外部分别都在这个意义上被当作递归可列的，而边界本身不是。
我一点也不清楚，这些观点是否真正必需10。把它应用到孟德勒伯洛特集时，“不理睬边界”的哲学可能将该集合的许多复杂性都损失了。该集合一部分包括具有内部区域的“点”，还有部分是“卷须”。其极端复杂性似乎存在于极其剧烈地弯曲的卷须之中。然而，卷须不在集合的内部，所以如果我们采用了上述的任一种哲学，则这些卷须都被忽略了。尽管如此，当只考虑斑点时，仍然不清楚孟德勒伯洛特集是否为“递归的”。这个问题似乎依赖于某个未被证明的有关孟德勒伯洛特集的猜测：它是所谓的“局部连通”的吗？我不想在此解释此术语的意义及其关联之处。我只想指出这些是困难的问题，它们引起了有关孟德勒伯洛特集的未解决的问题，而且其中一些正是当前某些数学研究的最前沿的问题。为了绕过复数是不可列的问题，人们还可以采用其他的观点。人们不去考虑所有可计算的复数，而去考虑这样的一个适当的子集，该子集的数具有去决定其中两个数相等与否仍是可计算的问题的性质。“有理”复数即为这样的一种简单的子集，实部和虚部均为有理数的复数即为有理复数。我认为它并不在孟德勒伯洛特集中占多少，而这种观点又是非常局限的。考虑代数数也许会更令人满意些――这就是那些为整系数的代数方程的解的那些复数。例如，方程129z7－33z5＋725z4＋16z3－2z－3=0所有z的解为代数数。代数数是可列的并且是可计算的。实际上去决定它们中的两个是否相等正是可计算的问题。（它们其中许多处于单位圆的边界和孟德勒伯洛特集的须蔓上。）如果需要的话，我们可把这问题表述成，孟德勒伯洛特集按照它们是否为递归的。在刚才考虑的两个集合的情况下代数数也许是合适的，但它实在不能一般地解决我们所有的困难。考虑由关系y≥ex所定义的集合 （图4。5中的黑的区域）。 这里z=x＋iy是阿伽德平面上的点。按照上面所表述的任何观点，该集合的内部以及其补集的内部，都是递归可列的。但是（从F？林德曼在1882年证明的一个著名定理）边界y=ex，只包含一个代数点，即z=i。代数数对于这种情形下的边界的算法性质的研究毫无用处！不难去寻找其他的可计算数的子集以对付这特殊情形，但人们会强烈地感到，我们还没得到正确的观点。图4。5由指数关系y＞ex定义的集合也必须被当作“递归的”。一些非递归数学的例子在许多数学分枝中产生了非递归的问题。也就是说，我们会遇到一系列的问题，它们答案或者为“是”或者为“非”，但是不存在决定究竟是什么答案的一般算法。在这类问题中有一些显得非常简单。首先考虑求整系数代数方程组的整数解的问题。这种方程称为丢番都方程（以希腊数学家丢番都来命名，他的生活年代为公元前三世纪，他研究了这一类方程）。这样的一组方程可为z3－y－1=0，yz2－2x－2=0，y2－2xz＋1=0，问题在于决定它们是否有x，y，z的整数值的解。在给定的特殊情况下，事实上存在X＝13，y＝7，z＝2的解。然而，不存在决定任意丢番都方程集合①的这一问题的算法：尽管丢番都算术是这么初等，它却是非算法数学的一部分！
（另一个稍微高等的例子是流形的拓朴等价。这里我仅仅简略地提及，因为它和第八章要讨论的问题有某种可以预料到的相关性。为了理解何为“流形”，先考虑一个线圈，它是仅仅为一维的流形。然后考虑一个闭合面，这是二维的流形。再摹想具有三维或更高维的“表面”。两个流形的“拓朴等价”表明其中一个可以连续运动地变形成另一个――不能撕裂，也不能粘住。这样，一个球面和一个立方体的表面就是拓朴等价的，同时它们和一个环或茶杯的表面不是拓朴等价的――后两者实际上是相互拓朴等价的。现在，对于二维流形，存在一种决定其是否拓朴等价的算法――事实上可归结为计算每一曲面所具有“把柄”的数目。在写此书时，对于三维这问题的答案还没有得到，但是对于四维或更高维的情况，已经知道不存在决定等价类的算法。四维情形和物理有些相关是可以理解的。
这是由于按照爱因斯坦的广义相对论，空间和时间一起组成了一个四流形（见第五章238页）。格罗许和哈特尔在1987年提出，这个非算法性质可能和“量子引力”有关；还可参阅第八章。）
现在我们考虑一个被称作词语问题 11的不同种类的问题。 假定我们有某些符号字母，考虑把这些符号连成各种称作词的串。词本身可以不具有意义，但是我们有一张（有限的）在它们之间“等价”的表，可用此表来推导出更多这样的“等价”。这可以用如下办法做到，在较长的词中找出和表中某个词相同的部分，这一部分可用表中认为是相等的另一个词来取代。现在问题就归结为，对某一对给定的词，按照这些规则决定它们是否“相等”。
① 允许发生这种不幸的可能性实际上是重要的，这样使得能有描述任何算法运算的潜力。我们记得，为了一般地描述图灵机，我们必须允许实际上永远不停止的图灵机。例如，我们原始的表为EAT=ATATE=ALATER=LOWPAN=PILLOWCARP=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=HAOH=HOAT=TAOT=TOTAI=ITHOI=IHTHAT=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