按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
乃惴āＣ系吕詹逄丶牟辜残碚嬲且桓龅莨榭闪械皇堑莨榈募希�
在进一步探索这个设想之前，必须先讨论我掩饰的某些问题。这些问题对于以后讨论物理的可计算性具有某种重要性。我前面的讨论实际上有些不精确。我把诸如“递归可列的”和“递归的”这样的术语应用于阿伽德平面也就是复数的集合上。严格地讲，这些术语只能适用于自然数或其他可列的集合。我们已经在
第三章（98页）看到实数是不可列的，所以复
数也不是可列的――由于实数可考虑作特殊种类的复数，也就是虚部为零的复数。事实上，刚好存在和实数“一样多”数目的复数，也就是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吗？在第一种情形下的答案恰好为“是”，而在第二种情况下则为“非”。当答案为“是”时，通常显示这一点的方法是简单地写出一串等式，每一个词都是用允许的关系从前面的词得出。这样