皇帝新脑-20

些不精确。我把诸如 “递归可列的”和“递归的”这样的术语应用于阿伽德平面也就是复数的集合上。严格地讲,这些术语只能适用于自然数或其他可列的集合。我们已经在第三章 (98 页)看到实数是不可列的,所以复数也不是可列的——由于实数可考虑作特殊种类的复数,也就是虚部为零的复数。事实上,刚好存在和实数 “一样多”数目的复数,也就是C 那么----------------------- Page 126-----------------------多。 (粗略地讲,为了建立复数和实数之间的一一对应,我们可以把每一复数的实虚部各作小数展开,然后将其交叉地塞到相应实数的奇数和偶数位上去:例如复数 3.6781…+i512.975…对应于实数50132.6977851…。)逃避这个问题的一种办法是只管可计算的复数。我们在第三章看到,可计算的实数——并因此可计算的复数——的确是可列的。然而,这里有严重的困难:事实上不存在决定两个按照它们相应的算法给出的可计算数是否相等的一般算法! (我们可以算法地形成它们的差,但我们不能算法地决定这个差是否为0。想象两个分别产生0.99999…和1.00000…的算法,我们也许永远不会知道这些9和0 是否无限地继续下去,因此这两个数相等,或最终某些其他的数会出现,因此这两个数不等。)这样,我们也许永远不能知道这些数是否相等。其中的一个含义是,甚至对诸如阿伽德平面上的单位圆盘这么简单的集合 (所有到原点的距离不大于一个单位的点的集合,也就是图4.4 中的黑的区域)都没有决定复数是否实际上处于圆上的算法。当点在内部 (或在外部)时不会引起这个问题,但点处于圆盘的边缘时,也就是在单位圆本身上时就有了问题。单位圆被认为是圆盘的部分。假定我们简单地给出产生某复数的实部和虚部的位数的算法。如果我们怀疑该复数实际上处于单位圆上,我们并不能肯定这个事实。不存在去决定可计算数2 2x +y是否实际上等于或不等于 1 的算法,也就是决定该可计算复数x+iy 是否在单位圆上的判据。图4.4 单位圆盘肯定被当作 “递归的”,但是这里需要一个适当的观点。这肯定不是我们所需要的。单位圆盘当然必须被当作递归的!没有很多集合比单位圆盘更简单!一种躲避这一问题的办法是不理睬边界。对实际上处于内部或外部的点肯定存在确认这些事实的算法。 (简单地一个接2 2一个地产生x +y 的数位,最终会发现在小数展开0.99999…后面出现非9或 1.00000…后面出现非0)。在这个意义上讲,单位圆盘是递归的。但是,这种观点是相当粗劣的,因为人们经常需要按照在边界上的行为来进行论证。另一方面,这种观点或许对物理学是合适的。我们以后还要再考虑这些问题。人们或许还会采用另一种紧密相关的观点,它根本未涉及可计算复数的问题。我们简单地要求可对给定的复数决定其是否在该集中或在补集中的算法,而不试图去列举该问题的集外或集内的复数。我在这里的“给定”的意义是,对于我们检验的每一个复数,也许用某种魔术的办法,实部和虚部的连续位数可一个接一个地写出以供使用,要多长就有多长。我不要----------------------- Page 127-----------------------求存在任何已知或未知的把这些位数写出来的算法。对于一个复数的集合,如果存在一个单独的算法,使得只要并且只要一个复数实际上在此集中,一旦该数以这种方法用一串数位写出,就在有限的步骤后它最终会说“是”,则该集合被认为是“递归可列的”。和上面提出的第一种观点一样,这种观点 “不理睬”边界。这样,单位圆盘的内部和外部分别都在这个意义上被当作递归可列的,而边界本身不是。我一点也不清楚,这些观点是否真正必需 10。把它应用到孟德勒伯洛特集时, “不理睬边界”的哲学可能将该集合的许多复杂性都损失了。该集合一部分包括具有内部区域的 “点”,还有部分是 “卷须”。其极端复杂性似乎存在于极其剧烈地弯曲的卷须之中。然而,卷须不在集合的内部,所以如果我们采用了上述的任一种哲学,则这些卷须都被忽略了。尽管如此,当只考虑斑点时,仍然不清楚孟德勒伯洛特集是否为 “递归的”。这个问题似乎依赖于某个未被证明的有关孟德勒伯洛特集的猜测:它是所谓的 “局部连通”的吗?我不想在此解释此术语的意义及其关联之处。我只想指出这些是困难的问题,它们引起了有关孟德勒伯洛特集的未解决的问题,而且其中一些正是当前某些数学研究的最前沿的问题。为了绕过复数是不可列的问题,人们还可以采用其他的观点。人们不去考虑所有可计算的复数,而去考虑这样的一个适当的子集,该子集的数具有去决定其中两个数相等与否仍是可计算的问题的性质。 “有理”复数即为这样的一种简单的子集,实部和虚部均为有理数的复数即为有理复数。我认为它并不在孟德勒伯洛特集中占多少,而这种观点又是非常局限的。考虑代数数也许会更令人满意些——这就是那些为整系数的代数方程的解的那些复数。例如,方程7 5 4 3129z -33z +725z +16z -2z-3=0所有 z 的解为代数数。代数数是可列的并且是可计算的。实际上去决定它们中的两个是否相等正是可计算的问题。 (它们其中许多处于单位圆的边界和孟德勒伯洛特集的须蔓上。)如果需要的话,我们可把这问题表述成,孟德勒伯洛特集按照它们是否为递归的。在刚才考虑的两个集合的情况下代数数也许是合适的,但它实在不能一般地解决我们所有的困难。考虑由关系y≥ex所定义的集合(图4.5 中的黑的区域)。这里 z=x+iy 是阿伽德平面上的点。按照上面所表述的任何观点,该集合的内部以及其补集的内部,都是递归x可列的。但是 (从F ·林德曼在1882年证明的一个著名定理)边界y=e ,只包含一个代数点,即z=i。代数数对于这种情形下的边界的算法性质的研究毫无用处!不难去寻找其他的可计算数的子集以对付这特殊情形,但人们会强烈地感到,我们还没得到正确的观点。----------------------- Page 128-----------------------x图4.5 由指数关系y>e 定义的集合也必须被当作 “递归的”。----------------------- Page 129-----------------------一些非递归数学的例子在许多数学分枝中产生了非递归的问题。也就是说,我们会遇到一系列的问题,它们答案或者为 “是”或者为“非”,但是不存在决定究竟是什么答案的一般算法。在这类问题中有一些显得非常简单。首先考虑求整系数代数方程组的整数解的问题。这种方程称为丢番都方程 (以希腊数学家丢番都来命名,他的生活年代为公元前三世纪,他研究了这一类方程)。这样的一组方程可为3 2 2z -y-1=0,yz -2x-2=0,y -2xz+1=0,问题在于决定它们是否有x,y,z 的整数值的解。在给定的特殊情况下,事实上存在X=13,y=7,z=2①的解。然而,不存在决定任意丢番都方程集合 的这一问题的算法:尽管丢番都算术是这么初等,它却是非算法数学的一部分!(另一个稍微高等的例子是流形的拓朴等价。这里我仅仅简略地提及,因为它和第八章要讨论的问题有某种可以预料到的相关性。为了理解何为 “流形”,先考虑一个线圈,它是仅仅为一维的流形。然后考虑一个闭合面,这是二维的流形。再摹想具有三维或更高维的 “表面”。两个流形的 “拓朴等价”表明其中一个可以连续运动地变形成另一个——不能撕裂,也不能粘住。这样,一个球面和一个立方体的表面就是拓朴等价的,同时它们和一个环或茶杯的表面不是拓朴等价的——后两者实际上是相互拓朴等价的。现在,对于二维流形,存在一种决定其是否拓朴等价的算法——事实上可归结为计算每一曲面所具有 “把柄”的数目。在写此书时,对于三维这问题的答案还没有得到,但是对于四维或更高维的情况,已经知道不存在决定等价类的算法。四维情形和物理有些相关是可以理解的。这是由于按照爱因斯坦的广义相对论,空间和时间一起组成了一个四流形(见第五章238 页)。格罗许和哈特尔在1987年提出,这个非算法性质可能和 “量子引力”有关;还可参阅第八章。)现在我们考虑一个被称作词语问题 11 的不同种类的问题。假定我们有某些符号字母,考虑把这些符号连成各种称作词的串。词本身可以不具有意义,但是我们有一张 (有限的)在它们之间“等价”的表,可用此表来推导出更多这样的 “等价”。这可以用如下办法做到,在较长的词中找出和表中某个词相同的部分,这一部分可用表中认为是相等的另一个词来取代。现在问题就归结为,对某一对给定的词,按照这些规则决定它们是否“相等”。① 允许发生这种不幸的可能性实际上是重要的,这样使得能有描述任何算法运算的潜力。我们记得,为了一般地描述图灵机,我们必须允许实际上永远不停止的图灵机。----------------------- Page 130-----------------------例如,我们原始的表为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 的不 “相等”。对于其他例子,也许需要完全不同的 “技巧”。顺便提及,对于建立“等式”的存在,智慧虽然不是必要的,却是有助的。)事实上,在上述情况中对于包含五个 “等式”的特殊的表,当两个词的确 “不等”时,提供一种去确定其 “不等”的算法并不特别困难。但是,为了找到对这种情况起作用的算法,我们必须使用一些的智慧!人们发----------------------- Page 131-----------------------现,并不存在任何单独算法可普遍地应用于所有原始表的选择。在这个意义上讲,词语问题不存在算法解。一般词语问题是属于非递归数学的范畴!甚至对于某种特别选取的初始表,不存在决定两个词语何时不相等的算法。其中一例便是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 ·冯德堡的更早的形状。值得注意的是,用这种花砖既可以构成周期性的也可以构成非周期性的镶嵌。许多其他单独花砖形状和花砖集合也具有这种性质。现在我们要问,----------------------- Page 132-----------------------

上一章 下一章
目录
打赏
夜间
日间
设置
61
正序
倒序
皇帝新脑
皇帝新脑-2
皇帝新脑-3
皇帝新脑-4
皇帝新脑-5
皇帝新脑-6
皇帝新脑-7
皇帝新脑-8
皇帝新脑-9
皇帝新脑-10
皇帝新脑-11
皇帝新脑-12
皇帝新脑-13
皇帝新脑-14
皇帝新脑-15
皇帝新脑-16
皇帝新脑-17
皇帝新脑-18
皇帝新脑-19
皇帝新脑-20
皇帝新脑-21
皇帝新脑-22
皇帝新脑-23
皇帝新脑-24
皇帝新脑-25
皇帝新脑-26
皇帝新脑-27
皇帝新脑-28
皇帝新脑-29
皇帝新脑-30
皇帝新脑-31
皇帝新脑-32
皇帝新脑-33
皇帝新脑-34
皇帝新脑-35
皇帝新脑-36
皇帝新脑-37
皇帝新脑-38
皇帝新脑-39
皇帝新脑-40
皇帝新脑-41
皇帝新脑-42
皇帝新脑-43
皇帝新脑-44
皇帝新脑-45
皇帝新脑-46
皇帝新脑-47
皇帝新脑-48
皇帝新脑-49
皇帝新脑-50
皇帝新脑-51
皇帝新脑-52
皇帝新脑-53
皇帝新脑-54
皇帝新脑-55
皇帝新脑-56
皇帝新脑-57
皇帝新脑-58
皇帝新脑-59
皇帝新脑-60
皇帝新脑-61
需支付:0 金币
开通VIP小说免费看
金币购买
您的金币 0

分享给朋友

皇帝新脑
皇帝新脑
获月票 0
  • x 1
  • x 2
  • x 3
  • x 4
  • x 5
  • x 6
  • 爱心猫粮
    1金币
  • 南瓜喵
    10金币
  • 喵喵玩具
    50金币
  • 喵喵毛线
    88金币
  • 喵喵项圈
    100金币
  • 喵喵手纸
    200金币
  • 喵喵跑车
    520金币
  • 喵喵别墅
    1314金币
网站统计