皇帝新脑-第21章

按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！


中许多处于单位圆的边界和孟德勒伯洛特集的须蔓上。）如果需要的话，我们可把这问题表述成，孟德勒伯洛特集按照它们是否为递归的。在刚才考虑的两个集合的情况下代数数也许是合适的，但它实在不能一般地解决我们所有的困难。考虑由关系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年在王浩的建议指导下，罗伯特？伯格能够指出，镶嵌问题的决定步骤实际上不存在：镶嵌问题也是非递归数学的一部分12！

　　图4。9三个非周期性的“螺旋”镶嵌，使用了图4。8中的同样的“万能”的形状。这样，我们从王浩的早期结果得知。必然存在非周期性的花砖集合，而且伯格也确实找到了第一族非周期性花砖。但是，由于这些论证脉络之复杂性，他的集合涉及到了非同小可的大数目的不同花砖――最初有20426个。　伯特又用了许多技巧才将其数目减少到104个。　然后到1971年，拉飞逸？罗宾逊将此数目减少到图4。10所示的六个。

　　图4。10拉飞逸？罗宾逊的只能把平面非周期性镶嵌的六种花砖。

　　图4。11另一种只能非周期性地把平面镶嵌的六种花砖的集合。

　　①　事实上，该证明可由一系列步骤组成，这些步骤反映了直到停止以前的机器的动作。机器一旦停止则证明即告完成。图4。12（彭罗斯镶嵌）两对花砖，每对都只能非周期性地镶嵌平面。还有对每对花砖镶嵌的平面区域。

　　图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，C2表示。它们可按c3＋2c2＋（1…z）c＋（1…z）2=0的集合给出，这儿z的范围是离开原点距离小于1/8的区域。这个方程事实上不仅为我们提供了两个斑点（在一起的），而且还提供一个“婴儿”心脏线形状，后者出现在图3。2的左边的地方――也就是图3。1的主要区域――在图4。13中标作C3的区域。这