皇帝新脑-第12部分

快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！

一种把两盘磁带的信息编码到单独一盘磁带上的方法是插入法。这样，这盘单独磁带上的奇数号码的记号可代表第一盘磁带的记号，而偶数号码的记号可代表第二盘磁带的记号。可用类似的方案来处理三盘或更多盘磁带。这一过程的“低效率”起因于如下事实，即阅读机必须沿着磁带不断地来回进退，并在上面留下记号以记住在该磁带偶数和奇数部分的什么地方。5．这一过程只是指作过记号的磁带可解释作自然数的方法而言。它并不改变我们特定的图灵机的编号譬如EUC或XN＋1。6．如果Tn/没有被正确地指定，则　U只要在n的二进位表示中到达多于四个1的第一串，就会像n的数已被终止那样进行下去。它就会把该表示式的余下部分当成m的磁带的部分来读，所以它会继续进行某种毫无意义的计算！如果需要的话，可采用扩展二进位记号来表示n，这种特征就能被清除。我决定不这样做，以免使这台可怜的普适机器U更加复杂！

　　7．我感谢大卫？德义奇根据以下我得到的u的二进位形式推导出十进位形式。我还感谢他检验u的这个二进位值实际上的确给出了一台普适图灵机！事实上u的二进位值为：

　　1000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l1001110101010010010101110101010011010001010001010110100有进取心的读者可把一台效率高的家庭用电脑，以正文中给出的方法，应用于不同的简单的图灵机号码中验证上面的号码事实上的确给出了一台普适图灵机的动作行为！对图灵机的不同明记方法可使u的值降低一些。例如，我们可以免除stop，而相反地采取这样的规则，即只要机器在某个其他非0的内态后重新进入内态0时它就停止。这样做没有太多收益（如果有的话）。如果我们允许磁带有比仅仅0和1的更多的记号，则能得到更大的收益。在文献中的确描述过显得非常简洁的普适图灵机。但是，由于它们一般地依赖于图灵机描述的极其复杂的编码，所以这种简洁性是骗人的。8．参阅德伏林（1988）的和这一著名断言相关事体的非技术性讨论。

　　9．我们再次简单地应用前面进行的步骤，当然也能击败这个改善了的算法。然后我们可以用这新的知识去进一步改善我们的算法；但是我们又可将其击败等等。这一递归步骤所导致的这类考虑将在第四章第125页的和哥德尔定理联系起来讨论。

　　第三章数学和实在托伯列南国

　　想象我们到某一遥远世界作远程旅行。我们称这一遥远世界为托伯列南国。现在把我们的遥感仪器收集到的信息展现在面前的屏幕上。调好焦距后就看到了图3。1。

　　图3。1　奇异世界之第一瞥。

　　它为何物？它是一只形状古怪的昆虫吗？也许它是一个深颜色的并有许多山溪注入的湖泊。也许它是一座巨大的形状奇特的异国城市，公路沿着不同方向散开到附近的小镇和乡村去。它也许为一个岛屿――让我们寻找看在附近是否有和它相连接的陆地。我们可以后退一些，把我们的感觉仪器的放大倍数减少十五倍左右。　嗬，　整个世界进入了我们的视界之内　（图3。2）。图3。2　整个“托伯列南国”。箭头这下标出了在图3。1、图3。3和图3。4中的放大部分的位置。我们在“岛”在图3。2中看起来成为标记“图3。1”下的小斑点。除了一条连接到右手的裂缝上去的以外，从原先岛上出发的小片断（溪流、路径、桥梁？）全部都终结了。该裂缝最终接到我们在图3。2画出的大得多的物体上去。这个更大的物体虽然和我们第一次看到的岛不完全一样，但明显地相似。如果我们更仔细地审视这一物体和海岸线相像的东西，就发现多得数不清的圆形的瘤状结构。每一结构自身又具有类似的瘤。似乎每一小瘤都在某一微小的地方附在一个更大的瘤上，由此在大瘤上产生出许许多多的小瘤。当图像变得更清楚时，人们就看到了从这个结构发出的成千上万根的细丝。这些细丝在不同的地方分叉并常常剧烈地弯折。在细丝的某些点，我们似乎看到了具有现有的放大倍数的感觉仪器所不能分析的复杂扭结。很显然，这物体不是实际的岛屿或陆地，也不是任何风景。

　　或许我们看到了某种怪诞的甲虫。我们首先看到的是它的婴儿，它用某种丝线状的脐带安静地把自己连接在母体上面。让我们把感觉仪器的放大倍数提高十倍，再来考察这个怪物的一个瘤的性质（图3。3――其位置在图3。2中的“图3。3”的标志的下面）。这个瘤本身和怪物整体非常相似――除了在接触点以外。请注意在图3。3中的不同地方五根细丝并到一块。这个特定的瘤似乎有一确定的“五性”（正如在最上面的瘤具有“三性”一样）。如果我们考察下一个相当尺度的瘤，在图3。2中稍微向左下方一点，我们就会在附近发现“七性”，再下一点为“九性”，并以此类推。当我们进入图3。2中的两个最大区域之间的裂缝，就会发现右边的瘤以奇数来表征，每回增加二。让我们钻到裂缝深处，把图3。2再放大十倍左右（图3。4）。我们看到其他许多小瘤以及扭转的结构。在右边称为“海马谷”的区域可鉴别出某些微小的涡旋状的“海马尾巴”。――如果放大倍数足够大的话，我们就将看到不同的“海乌贼”或者别具花样的区域。这也许的确是某种奇异的海岸线――也许是所有各色各样生命产生的珊瑚。看起来像是花的东西在更高的放大倍数下显得是由成千上万个微小，但同时却是不可思议的复杂的结构组成，每一结构都有极多的丝状物和扭转的涡旋尾巴。让我们稍微仔细地考察一个较大的海马的尾巴，也就是在图3。4中刚好能见到标志为“图3。5”的那个（它附在具有“二十九性”的瘤上面！）。大约再放大250倍左右，我们就得到了画在图3。5中的涡旋。我们发现这个尾巴非同寻常，它是由最复杂的、前后扭曲的、无数的小涡旋以及像章鱼和海马那样的区域组成。图3。3一个具有“五性”的细丝的瘤。

　　图3。4主狭缝：在右下方可见到“海马谷”。

　　图3。5海马尾巴的近窥。

　　图3