皇帝新脑-21

是否存在一种花砖或一组花砖，只能非周期性地镶嵌平面呢？答案是肯定的。在图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 的集合。该集合是由2c=z-z的形式产生的，z 是离原点距离小于 1/2 的复数。这一集合在早先提出的意义上肯定是递归可列的：即存在一个算法，把它应用于区域的内部的一点时，将会断定这一点的确是在区域的内部。很容易从上述的公式得到实际的算法。图4.13 可用简单的算法方程来定义孟德勒伯洛特集内部的主要部分。现在考虑刚好处于心脏线左边的圆盘状的区域（图4.13 中的区域B）。它的内部区域为点c=z-1的集合，这儿z 离开原点距离小于 1/4。这一区域的确是圆盘的内部——在一个准确圆的内部的点集合。这一区域又是在上面意义下递归可列的。关于心脏线上其他“瘤”的情况又如何呢？考虑余下的两个最大的瘤。这是大致圆形的斑点，近似地处于图3.2 心脏线的上顶和底下图4.13 中用C ，C 表示。它们可按1 23 2 2c +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 rn 以及n 中的每一个都大多了，甚至比带有任何固定指数r 的n 都大），或者譬如讲N 甚至近似地和22n （这又更大得多）成比例。当然，这些 “步骤”的数目可依赖于实现该算法的电脑的类型。如果电脑为第二章描述的图灵机，那儿只有一盘磁带——这是相当低效率的——那数目 N 就会比允许两盘或三盘磁带的增加得更快速 （也就是说机器会运行得更慢）。为了避免这类不定性，按照N作为 n 的函数增加的可能方式进行了宽广的分类，使得不管使用何种类型的图灵机，N 的增加率的度量总是归到同一分类中去。一种称为P （说明“多项式时间”的分类包括2 3 4 5 ①了所有最多为n，n ，n ，n ，n ，…中的一个的固定倍数 的速率。也就是说，对P分类中的任何问题 （这里我的“问题”的真正含义是具有解决它们的一个一般算法的一族问题），我们有rN≤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，21+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 和顶点