数也不是可列的――由于实数可考虑作特殊种类的复数，也就是虚部为零的复数。事实上，刚好存在和实数“一样多”数目的复数，也就是C那么多。（粗略地讲，为了建立复数和实数之间的一一对应，我们可以把每一复数的实虚部各作小数展开，然后将其交叉地塞到相应实数的奇数和偶数位上去：例如复数3.6781…+i512.975…对应于实数50132.6977851…。）逃避这个问题的一种办法是只管可计算的复数。我们在第三章看到，可计算的实数――并因此可计算的复数――的确是可列的。然而，这里有严重的困难：事实上不存在决定两个按照它们相应的算法给出的可计算数是否相等的一般算法！（我们可以算法地形成它们的差，但我们不能算法地决定这个差是否为0。想象两个分别产生0.99999…和1.00000…的算法，我们也许永远不会知道这些9和0是否无限地继续下去，因此这两个数相等，或最终某些其他的数会出现，因此这两个数不等。）这样，我们也许永远不能知道这些数是否相等。其中的一个含义是，甚至对诸如阿伽德平面上的单位圆盘这么简单的集合 （所有到原点的距离不大于一个单位的点的集合，也就是图4.4中的黑的区域）都没有决定复数是否实际上处于圆上的算法。当点在内部（或在外部）时不会引起这个问题，但点处于圆盘的边缘时，也就是在单位圆本身上时就有了问题。单位圆被认为是圆盘的部分。假定我们简单地给出产生某复数的实部和虚部的位数的算法。如果我们怀疑该复数实际上处于单位圆上，我们并不能肯定这个事实。不存在去决定可计算数x2+y2是否实际上等于或不等于1的算法， 也就是决定该可计算复数x+iy是否在单位圆上的判据。
图4.4单位圆盘肯定被当作“递归的”，但是这里需要一个适当的观点。这肯定不是我们所需要的。单位圆盘当然必须被当作递归的！没有很多集合比单位圆盘更简单！一种躲避这一问题的办法是不理睬边界。对实际上处于内部或外部的点肯定存在确认这些事实的算法。（简单地一个接一个地产生x2+y2的数位，最终会发现在小数展开0.99999…后面出现非9或1.00000…后面出现非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年在王浩的建议指导下，罗伯特?伯格能够指出，镶嵌问题的决定步骤实际上不存在：镶嵌问题也是非递归数学的一部分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的区域。这些（一起或分开的）区域由于上述公式的存在又组成了递归可列集。
尽管我已经做过假设，即孟德勒伯洛特集可能是非递归的，我们运用某些定义完好的以及不过于复杂的算法，可以清理出该集合的最大面积。这个步骤似乎应该继续下去。集合中所有最明显的、肯定占满了它面积的绝大部分（如果不是所有的话）的区域，可以被算法地处理。如果正如我所设想的那样，这集合全体不是递归的，则我们的算法不能达到的区域必须是非常精巧的，并且很难找到。而且，当我们已经定位了这样的一个区域，看看有无机会改善我们的算法，使那些特殊的区域也能达到。然而 （如果我关于非递归性的假设是正确的），还会有其他这类区域躲藏在微妙的、复杂的、模糊的深处，甚至于用我们改善了的算法都达不到。我们再次可能利用直觉、天才和勤奋的巨大努力，将这样的一个区域定位，但是还会有其他的会逃脱掉，等等。我想这就像用数学方式处理困难的问题，且假定为非递归性的。人们在某些特别的领域遇到的最普遍问题可由简单的算法步骤――甚至是已经知道了几世纪的步骤来解决。但是其中仍有漏网之鱼，要掌握它们就需要更复杂的步骤。漏网之鱼当然特别刺激数学家们，并促使他们去发展更为有力的方法。这些必须是基于对涉及的数学性质的越来越深刻的洞察之上。在我们对物理世界的理解中也许存在某些这种东西。在上面考虑的词语及镶嵌问题中，人们可以对这一类事稍有了解（虽然在这些领域中数学工具还未发展得非常远）。我们在一个非常特殊的情形下能用非常简单的论证去显示，某一词不能用允许的规则从另一词得到。不难想象，更复杂得多的推理可在处理更古怪的情形时起作用。很可能这些新的推理可发展成算法步骤。我们知道，不存在一个可以足够应付词语问题的所有情况的步骤，但是逃脱的例子需要非常仔细和精巧地去构造。的确，只要我们肯定知道躲开我们算法的例子，只要我们知道如何构造这些例子，则我们可以改善我们的算法以包括这种情形。只有不“相等”的配对词会逃脱，故一旦我们知道它们逃脱，我们就知道它们不“相等”，这一事实可添加到我们算法上去。我们改善了的洞察就导致一个改善了的算法！复杂性理论我在前面以及上一章关于算法的性质、存在和局限的论证是处于非常“原则的”水平上。我根本就没有讨论到出现的算法是否在任何方面像是可行的。即使对于算法存在并且该算法如何构造都很清楚的问题，也还需要许多才干和勤勉，才能将此算法发展成有用的东西。有时小小的洞察和才干就能可观地降低算法的复杂性，以及有时极大地加快其速度。这些问题经常是非常细节和技术性的。近年人们在构造、理解和改善算法方面，在不同的情况下做了大量的工作。这是一个快速扩大和发展的研究领域。我不想对这些问题进行细致的讨论。然而，有关算法的速度可被增加的某一绝对的极限有各种普遍知道或猜测的东西。人们发现，甚至在具有算法性质的数学问题中，也存在种种内在地比其他问题更难于算法地解决的问题。困难的问题只能用非常慢的算法（或许，需要非同寻常地大量的存储空间等）来解。有关这类问题的理论称为复杂性理论。
复杂性理论并不这么关心算法地解决单独问题的困难，而是关心无限个问题的族，找到解决一个单独族的所有问题的一般算法。族中的不同问题会有不同的“尺度”。问题的尺度是由某一自然数n来测量。（关于这一个数n实际上如何表征问题的尺度，我一会儿还要再说。）算法对于每类中的每一特别问题所需的时间长度――或更正确地说，基本步骤的数目――是依赖于n的某一自然数N。稍微精确一点讲，我们讲在所有具有某一特别尺度n的问题中算法采用的最大的步骤数目为N。现在，当n变得越来越大，N也似乎变得越来越大。事实上，N似乎增加得比n快速得多。例如，N可以近似地和n2，n3或许2n成比例（对于大的n，它比n，n2，n3，n4以及n5中的每一个都大多了，甚至比带有任何固定指数r的nr都大），或者譬如讲N甚至近似地和22n（这又更大得多）成比例。
当然，这些“步骤”的数目可依赖于实现该算法的电脑的类型。如果电脑为第二章描述的图灵机，那儿只有一盘磁带――这是相当低效率的――那数目N就会比允许两盘或三盘磁带的增加得更快速（也就是说机器会运行得更慢）。为了避免这类不定性，按照N作为n的函数增加的可能方式进行了宽广的分类，使得不管使用何种类型的图灵机，N的增加率的度量总是归到同一分类中去。一种称为P（说明“多项式时间”的分类包括了所有最多为n，n2，n3，n4，n5，…中的一个的固定倍数①的速率。也就是说，对P分类中的任何问题（这里我的“问题”的真正含义是具有解决它们的一个一般算法的一族问题），我们有N≤K×nr，① 这是在39页提到的希尔伯特第十问题的负面答案。（例如，参见德弗林1988。）这里变量的个数是不受限制的。然而人们知道，为了使这种非算法性质成立，实际上需要变量的个数不超过九就可以。这儿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，1+0=1，1+1=10。单独二进位乘法的次数为(n/2)×(n/2）=n2/4，并且可具有(n2/4-(n/2)次的单独的二进位加法（包括移位）。这样，总共有(n2/2)-(n/2)次的单独算术运算――我们必须包括一些涉及到移位的额外的逻辑步骤。总的步骤数为N=n2/2（忽略低阶项），这肯定是多项式的13。
一般来说，对于一族问题，我们取这问题的“尺度”的测度n为需要指明该特别尺度的问题的自由数据所需要的二进位位数（或比特）的总数。这意味着，对于给定的n，在给定的尺度下问题会有多到2n种不同的情形 （因为每一位可有两种可能性中的任一个， 0或1，而总共有n位数），而这些都必须由算法在不多于N步骤下被一致地处理好。
存在许多不属于P问题（的族）的例子。例如，为了进行从自然数r计算 的运算，甚至只要写出这一答案就大约需要 步骤，且不说进 2 ] 2 2 nr行计算了。 为在 的二进位表示中的位数。计算 的运算，只要写下就 n r 222r需要 步骤等等！这些比多项式大多了，所以肯定不在 中！ 2 P 2r在多项式时间内可以写下答案并甚至能检查正确与否的问题更为有趣。由此性质表征的（可算法地解出的）问题（的族）是一个重要的范畴。它们被称为NP问题（的族）。更精确地讲，如果在NP中的问题的族的个别问题有一解，那么该算法将给出这个解，并且它必须能在多项式时间内检验所设想的解确实是一个解。在问题没有解的情形下，算法会告诉我们这个，人们不必在多项式或别的时间内去检验的确没有解14。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和顶点5，…，顶点4接到顶点5，…等等（见图4.14）。如果需要的话，哈密顿线路可由这些边缘的子集给出，它用具有比前述的更多个零的二进位序列来描写。检查过程是可以比开始找这些哈密顿线路更迅速地完成的事。人们所要做的一切，是检查提出的线路的确是一线路，也就是边缘须属于原先的图，而图中的每一顶点刚好只被用过两次，在两个边缘的一个顶点各一次。这一检验过程是某种可以在多项式时间内完成的事。
事实上，这个问题不仅是NP的，而且被认为是NP完备的。这表明其他任何NP问题都可在多项式时间内转变成它。这样，如果某个足够聪明的人能在多项式时间内找到解决哈密顿线路的算法，也就是能显示哈密顿线路问题实际上是在P中！则其推论是任何 NP问题都在P中！这样的事情会具有重大的含义。一般地讲，对于合情理大的nP中的问题被认为可以用一台快速的现代电脑“处理”的（也就是“在一可接受的”时间长度里是可解的）。 而在NP中又不在P中的问题， 对于合情理大的n被认为是 “不可处理的”（也就是虽然在原则上可解，“在实际上是不可解的”），而不管我们将面临着何种可以预见的种类的电脑速度的增加。（对于大的n的不在P中的NP问题，需要的时间会急速地变得比宇宙的年龄还要长，这对于实际的问题没有什么用处！）任何在多项式时间内解决哈密顿线路问题的聪明算法都能转换成在多项式时间内解决任何其他NP问题的算法！
另一个NP完备的15问题是“旅行推销员的问题”。这个问题和哈密顿线路问题很相像，除了在不同的边缘附上数字，人们寻求数（推销员走的“距离”）的和为极小的哈密顿线路。旅行推销员问题的多项式时间解会又一次导致所有其他NP问题的多项式时间解。 （如果真的找到这样的一个解，将会变成头条新闻！尤其是好几年来提出了密码系统，该问题有赖于大整数的因子化问题，这是另一种NP问题。如果可在多项式时间内解决这一问题，那么这样的码就可能被强大的现代电脑所破。但是如果不能，这码就是安全的。参见伽特纳1989。）专家们普遍相信，不管用任何类图灵机的仪器，实际上都不可能在多项式时间内解决一个NP完备的问题。所以结论是，P和NP不是同样的这个信念很可能是正确的，虽然还没有一个人能证明之。这仍然是复杂性理论最重要的未解决问题。物理事物中的复杂性和可计算性复杂性理论对于本书的讨论是重要的，因为它引起了另外的问题，和事物是否可计算的问题有一点区别；也就是说，被认为是算法的事物实际上是否以一种有用的方式为算法的。在后面的章节中，我关于复杂性理论将讲得比可计算性更少。因为我倾向于认为（虽然毫无疑问地是在相当不足够的基础上）复杂性理论的问题和可计算性本身的问题不一样，在和精神现象相关联上不占有中心的地位。而且，我感到算法的可行性问题的现状才刚刚被复杂性理论所触及。
然而，关于复杂性作用的问题，我也很可能是错的。正如我将在后面（第九章464页）评论的那样，实在物理对象的复杂性理论也许和我们刚刚讨论的有显著的不同。为了使这种差异变得更明了，那就必须使用量子力学，这个原子、分子以及许多其他在大得多的尺度下重要现象行为的神秘而强有力的精确理论。 在第六章我们将遇到这一理论。 按照最近大卫?德义奇(1985)提出的一系列思想，在原则上可能建造“量子电脑”，存在不属于P的然而由这种装置可在多项式时间内解的问题的（类）。直到现在一点也不清楚，一个实际的物理仪器如何建造成行为可靠的量子电脑，而且迄今所考虑的问题的类肯定是很人为的――但是，我们似乎已经知道了用量子物理仪器改善图灵机的理论可能性。
我在这里讨论时把它当作一台“物理仪器”的人类的头脑，尽管是设计得非常微妙精巧的，而且是非常复杂，它本身会从量子理论的魔术中得到好处吗？我们是否理解量子效应可以用于解决问题或作判断的方式呢？
为了利用这种潜在的好处，我们也许必须“超越”现存的量子理论，这是可以理喻的吗？实际物理仪器真的很可能改善图灵机的复杂性理论吗？实际物理仪器的可计算性理论又是如何呢？
为了研究这类问题，我们必须离开纯粹数学的领域，并在下面的章节中探求物理世界在实际上是如何行为的！注 释1．在考虑其成员又为集合的集合时，我们必须小心地区别那个集的成员以及那个集的成员的成员。例如，假定S是另一确定的集T的非空子集的集合，而T的元素是一个苹果和一个桔子。T就有“二性”而非“三性”的性质；但是S实际上有“三性”的性质；S的三个成员是：一个只包括一个苹果的集合，一个只包括一个桔子的集合以及包括一个苹果和一个桔子的集合――总共有三个集，这就是S的三个元素。类似地，其成员只有空集的集合具有“一性”而非“零性”――它有一个成员，也就是空集！空集本身当然只有零个成员。
2．事实上，哥德尔定理的推理可以用这种方式来表达，使之不依赖于诸如Pk(k)的命题“真理”的完全外在的概念。然而，它仍然依赖于某些符号的实在“意义”的解释：尤其是，“～ ”的真正 是“不存 $ 意义在（自然数）……使得……”。
3．在下面用小写字母代表自然数，而用大写字母代表自然数的有限集合。令m-→〔n，k，r〕表示陈述“如果x=｛0，1…，m｝，它的k个元素的每一子集都被放到r个盒子里，则存在X的一个“大”的至少包含n个元素的子集Y， 使得所有Y的k元素子集都被放到同一盒里去。” 这儿 “大”的意思是Y中的元素数目比作为Y中的元素的最小的自然数还大。考虑如下命题： “对于任何选取的k，r和n，存在一个m0，使得所有大于m0的m，陈述m-→〔n，k，r〕总成立。”J?巴黎斯和L?哈林顿(1977)指出这一命题等效于算术的标准的（皮阿诺）公理的哥德尔型命题。这一道命题是不能从那些公理证明得到的，但是关于那些公理作了某些“显然正确”的断言正也就是，在这种情形下，从公理推断出来的命题本身是真的）。4．其题目为《基于序数的逻辑系统》，而且有些记者将会熟悉我用在下角标示代表康托序数的记号。使用我在上面所描述的步骤得到的逻辑系统的等级由可计算的序数来表征。
存在一些相当自然的和容易陈述的数学定理，如果人们试图用标准的算术的（皮阿诺）法则去证明，就需要使用在前面概述的“哥德尔化”步骤。这些定理的数学证明根本就不依赖于任何模糊或可疑的似乎处于正常数学论证的步骤以外那一类推理。参见斯莫林斯基(1983)。的最 “极端的” 的数学陈述 （虽然人们还经常考虑比这更极端得多的陈述）。
连续统假设，由于哥德尔本人和保罗J?柯亨确立了它实际上和集论的标准公理和步骤法则无关，而变得格外有趣。这样，对连续统假设的看法可用来区分形式主义者和柏拉图主义者。对于一个形式主义者而言，由于用标准的（策墨罗――弗兰克尔）形式系统既不能建立也不能否定连续统假设，所以是“非决定的”，把它叫做“真”的或“伪”的都“没有意义”。
然而，对于一个好的柏拉图主义者，连续统假设或是真的或是伪的，但为了确立它就需要某种新的推理形式――实际上甚至超出了对策墨罗――弗兰克尔形式系统使用哥德尔型命题的手段。（柯亨(1966)本人提出一种使得连续统假设成为“显然错误”的反思原则！）6．参阅鲁克尔(1984)的生动而不太技术性的有关论述。
7．伯鲁尔本人似乎部分地因为对自己的一个拓朴学的 “伯鲁尔固定点定理”证明的“不可构造性”忧虑，而开始沿着这个思路思考的。该定理断言，如果你取一个圆盘――也就是一个圆和它的内部――并且以一种连续的方式运动到它原先定位的区域的内部，那么在圆盘上至少有一叫做固定点的点，它刚好在自己开始的那点结束。人们也许不知该点准确地在何处，或者也许那里有许多这类的点，这个定理只是断言某一这类的点的存在。作为数学的存在定理而言，这实际上是一个相当“构造性的”定理。依赖于所谓的“选择公理”或“卓恩引理”的存在定理具有不同程度的非构造性 （参阅柯亨1966，鲁克尔1984）。伯鲁尔情形的困难和下面相类似：如果f为一实变量的实数值的连续函数，该函数既取有负值又取有正值，找到f取零值的地方。其通常的步骤是涉及到重复地对分f改变符号的区划。但是去决定f的中间值为正、负或零，在伯鲁尔需要的意义上可以不是“构造性的”。8．我们列出集合{v，w，x，…，z}，这里按照某种字典方案，v代表函数f。我们在每一阶段（递归地）检验看是否有f(w，x，…，z)=0，并且只有如果是这样的话，才维持命题 ， ，… 〔 ， ，…， $w x z f(w xz)=0〕。9．最近妮诺?伯龙（由于受这本书初版精装本中我的议论所刺激）告诉我，她已能断定孟德勒伯洛特集（的补集）在下面注释10的特殊意义下的确是非递归的，正如我在正文中所猜测的那样。
10．存在实变量的实函数的可计算性的一种新理论（和传统的自然数变量的自然数函数相反），由伯龙、苏伯和斯马勒(1989)提出。我最近才注意到该理论的细节。该理论还适用于复函数，它可能和正文中提出的问题有重要的关系。这一新工作的一些结果赋予孟德勒伯洛特集在适当意义下为非递归的猜测以强大的支持。
11．这一特殊问题可更正确地被称为“半群的词语问题”。还有其他形式的词语问题，其法则略为不同，我们在此不予关注。12．汉弗(1974)和迈尔斯(1974)还指出，存在一个单独的（一个巨大数目的花砖）集合，它只能以不可计算的方式来镶嵌平面。13．事实上对于大的n，这一步骤的数目可用一些技巧减少到nlogloglogn――这当然还在P中。参见克奴斯(1981)有关的更多资料。14．更正确地讲，只对是/非类型问题（例如，给定a，b和c，a×b=c为真的吗？）P、NP和NP完备的族（参见165页）才被定义，但在正文中的描述对我们的目的已经足够。
15．严格地讲，我们需要是/非的模式，诸如：推销员是否有一条距离小于若干的路径呢？（见上面的注释14）。
