皇帝新脑-第7部分

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


　　关于图灵　“机”　有一件事必须记在心里，　就是说它是一段　“抽象数学”，而不是一个物理对象。这一概念是由英国数学家、非凡的破码专家兼电脑科学的开山鼻祖阿伦？图灵在1935―1936年间提出的（图灵1937）。其目的是为了解决称为判决问题的一个范围广阔的问题。它是由伟大的德国数学家大卫？希尔伯特部分地于1900年巴黎国际数学家会议上（“希尔伯特第十问题”），更完整地于1928年玻罗那国际会议上提出的。希尔伯特不多不少地要求解决数学问题的一般算法步骤，或者不如讲，是否在原则上存在这样步骤的问题。希尔伯特还有一个要把数学置于无懈可击的坚固基础上的宏伟规划，其中公理和步骤法则一旦定下就不能变。但是在图灵完成其伟大的工作之际，这个规划已经遭受到由奥地利才气焕发的逻辑学家库尔特？哥德尔在1931年证明的令人吃惊的定理的粉碎性打击。我们将在

　　第四章考虑哥德尔定理及其意义。图灵关心的希尔伯特问题（判决问

　　题）超越出任何按照公理系统的特殊的数学形式。问题在于，是否存在能在原则上一个接一个地解决所有（属于某种适当定义的族的）数学问题的某种一般的机械步骤？

　　回答这一问题的部分困难在于决定什么叫做“机械过程”。这概念处于当时正常的数学概念之外。为了掌握它，图灵设想如何才能把“机器”的概念表达出来，它的动作被分解成基本的项目。这一些似乎是清楚的，图灵也把人脑当成在他意义上的“机器”的例子。这样，由人类数学家在解决数学问题时进行的任何活动，都可以被冠以“机械步骤”之名。

　　虽然这一有关人类思维的观点似乎对于图灵发展他的极重要概念很有价值，我们却绝没有必要去附和它。的确，图灵在把机械过程的含义弄精确时，向我们展示出存在一些完好定义的数学运算，在任何通常的意义上，都不能被称为机械的！图灵本人的这一方面工作现在可间接地为我们提供了他自己有关精神现象性质观点的漏洞。这个事实也许不无讽刺意味。然而，这不是我们此刻所关心的。我们首先要弄清图灵心目中的机械过程究竟是什么。图灵概念我们设想实现某种（可以有限地定义的）计算步骤的一台仪器。这样仪器会采取什么样的一般形式呢？我们必须准备理想化一些，而且不必为实用性过份担心：我们是真正地考虑一台数学上理想化的“机器”。我们要求该仪器具有有限　（虽然也许非常大的）数目的不同可能态的分立集合。

　　我们把这些称作仪器的内态。但是我们不限制该仪器在原则上要实现的计算的尺度。回顾一下上述的欧几里德算法。在原则上不存在被该算法作用的数的大小的限制。不管这些数有多大，算法或者一般计算步骤都是同样的。对于非常大的数，该步骤的确要用非常长的时间，而且需要在数量可观的“粗纸”上面进行实际的计算。但是不管这些数有多大，该算法是指令的同一有限集合。这样，虽然我们仪器只有有限个内态，它却能够处理大小不受限制的输入。　此外，　为了计算应允许该仪器召来无限的外存空间　（我们的　“粗纸”）；而且能够产生大小不受限制的输出。由于该仪器只有有限数目的不同的内态，不能指望它把所有外部数据和所有自己计算的结果“内化”。相反地，它必须只考察那些立即处理的数据部分或者早先的计算，然后进行需要对它们进行的任何运算。也许可在外存空间把那个运算的相关结果记下来，然后以一种精确决定的方式进行下一个阶段的运算。正是输入、计算空间和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际上可真正建造的某种东西（见图2。1）。但这是极其关键的理想化。对于大多数实用目的而言，当代电脑技术的奇迹为我们提供了无限的电子存储仪器。

　　事实上，在上述讨论中称为“外部的”存储空间的类型，可实际上被认为是现代电脑的内部工作的一部分。存储空间的某一确定部分是否被当作内部的或外部的，　也许只是术语的问题。　按照硬件和软件是划分　“仪器”和“外部”的一种方法。内部可当成硬体，而外部为软体。我将不必拘泥于此，但是不管从那个角度看，当代电子电脑是图灵的理想化的极好近似。图2。1一台严格的图灵机需要无限的磁带图灵是按照在上面作记号的　“磁带”来描述其外部数据和存储空间的。一旦需要，仪器就会把该磁带召来“阅读”，而且作为其运算的一部分，磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号，允许同一磁带像外存（也就是“粗纸”）以及输入那样动作。因为在许多运算中，一个计算的中间结果起的作用正如同新的数据，所以事实上在“外存”和“输入”之间不做任何清楚的区分也许是有益的。我们记得在欧几里德算法中，不断地用计算不同阶段的结果去取代原先的输入（数A和B）。

　　类似地，这同一磁带可被用作最后输出（也就是“答案”）。只要必须进行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。

　　让我们有限的仪器前后移动一条潜在地无穷长的磁带，我自己觉得有点不舒服。不管其材料是多么轻，移动无限长的磁带是非常困难的！相反地，我宁愿把磁带设想成代表某一外部环境，我们有限的仪器可以通过这环境进行移动。（当然用现代电子学，既不需要“磁带”也不需要“仪器”作实际的、在通常物理意义上的“运动”，但是这种“运动”是一种描述事体的便利方法。）依此观点，该仪器完全是从这个环境接受它的输入。它把环境当成它的“粗纸”。最后将其输出在这同一个环境中写出。

　　在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个单独的记号①。我们可利用有记号或者没有记号的方格来阐释，我们的环境（也就是磁带）可允许被细分并按照分立（和连续相反的）元素来描述。如果希望仪器以一种可靠并绝对确定的方式工作。这似乎是合情理的要做的事。然而，我们允许该“环境”是（潜在地）无限的，把这作为我们使用的数学理想化的特征。但是，在任何特殊的情形下，输入、计算和输出必须总是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该有有限数目的实在的记号。磁带在每一个方向的一定点以外必须是空白的。我们用符号“0”来表示空白方格，用符号“1”来代表记号方格，例如：0　0　0　1　1　1　1　0　1　0　0　1　1　1　0　0　1　0　0　1　0　1　1　0　1　0　0我们要求该仪器“读”此磁带，并假定它在一个时刻读一个方格，在每一步运算后向右或向左移动一个方格。这里没有损失任何涉及到的一般性。

　　可以容易地由另一台一次只读和移动一个方格的仪器去仿照一台一次可读n个方格或者一次可移动k个方格的仪器。　k方格的移动可由一个方格的k次移动来积累，而存储一个方格上的n种记号的行为正和一次读n个方格一样。这样的一台仪器在细节上可做什么呢？什么是我们描述成“机械的”

　　东西作用的最一般方式呢？我们记得该仪器的内态在数目上是有限的。除了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态①　事实上，图灵在他原先的描述中允许磁带有更复杂的记号，但这并没有什么本质上的差别。更复杂的记号总能被细分成记号和空白的序列。我将随意地对他原先的详细说明作各种不重要的变通。和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号0或1来取代它刚读过的0或1；它向右或向左移动一个方格；最后它决定是继续还是终止计算并停机。为了以明白的方式定义该仪器的运算，我们首先，譬如讲用标号0，　1，2，3，4，5，……，来为不同的内态编号；那么，用一张显明的代换表可以完全指定该仪器或图灵机的运行，譬如：

　　00→00R01→131L10→651R11→10R20→01R　STOP21→661L30→370R？？？？？？2100→31？？？？？？2580→00R。STOP2590→971R2591→00R。STOP箭头左边的大写的数字是仪器在阅读过程中磁带上的符号，仪器用右边中间的大写的数字来取代之。R告诉我们仪器要向右移动一个方格，而L告诉我们它要向左移动一个方格。（如果，正如图灵原先描述的那样，我们认为磁带而不是仪器在移动，那么我们必须将R解释成把磁带向左移动一个方格，而L为向右移动一个方格。）词STOP表示计算已经完成而且机器就要停止。特别是，第二条指令01→131L告诉我们，如果仪器内态为0而在磁带上读到1，则它应改变到内态13，不改变磁带上的1，并沿着磁带向左移一格。最后一条指令2591→00R。STOP告诉我们，如果仪器处于态259而且在磁带上读到1，那么它应被改变为态0，在磁带上抹去1而产生0，沿着磁带向右移一格，然后终止计算。

　　如果我们只用由0到1构成的符号，而不用数字0，1，　2，3，4，　5……

　　来为内态编号的话，则就和上述磁带上记号的表示更一致。如果我们有选择的话，可简单地用一串n个1来标号态n，但这是低效率的。相反地，我们使用现在人们很熟悉的二进位记数系统：0→0，1→1，2→10，3→11，4→100，5→101，6→110，7→111，8→1000，9→1001，10→1010，11→1011，12→1100，等等正如在标准的（十进位）记数中一样，这里最右边的数字代表“个位”，但是紧在它前面的位数代表“二”而不是“十”。再前面的位数代表“四”

　　而不是“百”，更前面的是“八”而不是“千”等等。随着我们向左移动，每一接续的位数的值为接续的二的幂：1，2，4（=2×2），8（=2×2×2），16（=2×2×2×2），32（=2×2×2×2×2）等等。　（为了将来的其他目的，我们有时发现用二和十以外的基来表示自然数是有助的：例如基数为三，则十进位数64就可被写成2101，现在每一位数都为三的幂：64=（2×33）

　　＋32＋1；参阅第四章122页的脚注。）

　　对上面图灵机的内态使用这种二进位记号，则原先的指令表便写成：

　　00→00R0１→1101１R1０→1000001１L1１→1０R10０→0１STOPR10１→1000010１L11０→100101０R？？？？？？11010010０→11１L？？？？？？？？100000010１→0０STOP100000011０→1100001１R100000011１→0０STOP我还在上面把R。STOP简写成STOP，这是由于可以假定L。STOP从来不会发生，以使得计算的最后一步结果，作为答案的部分，总是显示在仪器的左边。现在假定我们的仪器处于由二进位序列1010010代表的特殊内态中，它处于计算的过程中，第43页给出了它的磁带，而且我们利用指令11010010０→11１L；在磁带上被读的特殊位数（这里是位数“０”）由一个更大写的数字指示，符号串的左边表示内态。在由上面（我多多少少是随机造出的）部分地指定的图灵机例子中，读到的“０”会被“1”所取代，而内态变成‘11’，然后仪器向左移动一格：

　　该仪器现在已准备好读另一个数字，它又是“０”。根据该表，它现在不改变这个“０”，但是其内态由“100101”所取代，而且沿着磁带向右移回一格。现在它读到“１”，而在表的下面某处又有如何进一步取代内态的指令，告诉它是否改变所读到的数，并向那个方向沿着磁带移动。它就用这种方式不断继续下去，直到达到STOP为止，在该处（在它向右再移一格之后）我们可以想象听到一声铃响，警告机器操作员计算完毕。我们将假定机器总是从内态“0”开始，而且在阅读机左边的磁带原先是空白的。所有指令和数据都是在右边输进去。正如早先提到的，被提供的这些信息总是采用０和１的有限串的形式，后面跟的是空白带（也就是０）。当机器达到STOP时，计算的结果就出现在阅读机左边的磁带上。由于我们希望能把数字数据当作输入的一部分，这样就需要有一种描述作为输入部分的通常的数（我这里是说自然数0，1，2，3，4，…）的方法。一种方法可以是简单地利用一串n个1代表数n（尽管这会给我们带来和自然数0相关的困难）：1→1，2→11，3→111，4→1111，5→11111，等等。

　　这一初等的记数系统（相当非逻辑地）被称作一进位系统。那么符号‘O’可用作不同的数之间的分隔手段。这种把数分隔开的手段是重要的，这是由于许多算法要作用到数的集合，而不仅仅是一个数上面。例如，对于欧几里德算法，我们的仪器要作用到一对数　A和B上面。图灵机可以很容易地写下执行该算法的程序。作为一个练习，某些勤奋的读者也许介意去验证下面的一台图灵机（我将称它为EUC）的显明的描述，当应用到一对由０分隔的一进位数时，的确会执行欧几里德算法：0０→0０R，0１→1１L，1０→10１R，1１→1１L，10０→1010０R，10１→11０R，11０→100０R，11１→11１R，100０→100０R，100１→101０R，101０→111０L，101１→110１L，110０→110０L，110１→1１L，111０→111０L，111１→1000１L，1000０→1001０L，1000１→1000１L，1001０→10０R，1001１→1１L，1010０→0０STOP，　1010１→1010１R。

　　然而，　任何读者在进行此事之前，　从某种简单得多的东西，　譬如图灵机UN＋1开始将更为明智：0０→0０R，0１→1１R，1０→0１STOP，1１→0１R。

　　它简单地把一加到一个一进位数上。为了检查UN＋1刚好做到这点，让我们想象，譬如讲把它应用到代表数4的磁带上去：…０００００１１１１０００００…。

　　我们使仪器在开始时从某处向左为一些1。它处于内态０并且读到0。根据第一条指令，它仍保留为０，向右移动一格，而且停在内态0上，在它遇到第一个1之前，它不断地这么进行并向右移动。然后第二条指令开始作用：它把1留下来不变并且再向右移动，但是现在处于内态１上。按照第四条指令，它停在内态1上，不改变这些1，一直向右移动，一直达到跟在这些１后面的第一个０为止。第三条指令接着告诉它把那个０改变成１，向右再移一步（记住STOP是表示R，STOP），然后停机。这样，另一个１已经加到这一串１上。正如所要求的，我们例子中的4已经变成了5。作为更费神的练习，人们可以验证，下面所定义的机器UN×2，正如它所希望的，把一个一进位数加倍：0０→0０R，0１→1０R，1０→10１L，1１→1１R，10０→11０R10１→100０R，11０→0１STOP，11１→11１R，100０→101１L，100１→100１R，101０→10１L，101１→101１L