友情提示：如果本网页打开太慢或显示不完整，请尝试鼠标右键“刷新”本网页！
皇帝新脑-第8部分
快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！
11０→0１STOP，11１→11１R，100０→101１L，100１→100１R，101０→10１L，101１→101１L。
在EUC的情形、为了得到有关的概念，人们可用一些明显的数对譬如6和8来试验。正如以前一样，阅读机处于态0，并且初始时处在左边，而现在磁带一开始的记号是这样子的：
…０００００００００００１１１１１１０１１１１１１１１０００００…在许多步之后，图灵机停止，我们得到了具有如下记号的磁带：
…００００１１００００００００００００…
而阅读机处于这些非零位数的右边。这样，所需的最大公约数正是所需要的（正确的）2。要完全解释为何EUC（或者UN×2）在实际上完成所预想的，牵涉到许多微妙之处，而且解释本身比机器更复杂，这是电脑程序的通常特征！ （为了完全理解一个算法步骤为何能做到所预想的，牵涉到洞察。“洞察”本身是算法的吗？这是一个对我们以后颇为重要的问题。）我不想在这里为EUC或UN×2提供解释。真正做过检验的读者会发现，为了在所需的方案中把事情表达得更精密一些，我自作主张地对欧几里德算法作了一些不重要的变通。EUC的描述仍然有些复杂，对于11种不同的内态包含有22条基本指令，大部分复杂性是纯粹组织形式的。例如，可以看到在22条指令中，只有三条真正涉及到在磁带上改变记号！（甚至对于UN×2用了12条指令，其中只有一半涉及到改变记号。）数据的二进位码用一进位系统表示大数极端无效率。正如早先描述的，我们将相应地用二进位计数系统。然而，不能直接地把磁带当作二进位数来读。如果这样做的话，就没有办法告知一个数的二进位表示何时结束，以及无限个０的序列是否代表右端开始的空白。我们需要某种终结一个数的二进位描述的记号。此外，我们还经常要输进几个数，正如欧几里德算法需要一对数2那样。问题在于，我们不能把数之间的间隔和作为单独的一个数的二进位表示中的一部分的０或一串０区分开来。此外，我们或许在输入磁带中包括所有种类复杂的指令和数。为了克服这些困难，让我们采用一种我称之为收缩的步骤。按照该步骤，任何一串０或一串１（共有有限个）不是简单地被当作二进位数来读，而是用一串0，1，2，3等来取代。其作法是，第二个序列的每一数字就是在第一个序列中的连续的０之间的１的个数。例如序列０１０００１０１１０１０１０１１０１０００１１１０１０１０１１１１００１１０就可被取代成：我们现在可以把数2，3，4，…当作某种记号或指令来读。让我们把2简单地当作表示两个数之间间隔的“逗号”，而根据我们的愿望，3， 4，5，…可以代表各种有兴趣的指令或记号，诸如“负号”、“加”、“乘”“到具有下面号码的位置”，“递归进行前面的运算如下面数目那么多次”等等。我们现在有了由更高的数分开的各种０和１的串。后者代表写成二进位的通常的数。这样上面可读成（“逗号”为2）：（二进位数１００１）逗号（二进位数11）逗号……。
使用标准的阿拉伯记号“9”，“3”，“4”，“0”来写相应的二进位１００１，１１，１００，０，我们就得到整个序列：9，3，4（指令3）3（指令4）0，特别是，这一步骤给了我们一种简单地利用在结尾处逗号终结描述一个数的手段（并因此把它和在右边的无限长的空白带区分开来）。此外，它还使我们能对以二进位记号写成０和丨的单独序列的自然数的任何有限序列编码。让我们看看在一特定情形下这是怎么进行的。例如，考虑序列5，13，0，1，1，4在二进位记号中这是１０１，１１０１，０，１，１，１００，它可用扩展（也就是和上面收缩相反）的步骤在磁带上编码成…００００１００１０１１０１０１００１０１１００１１０１０１１０１０１１０１０００１１０００…为了直截了当地得到这个码，我们可在原先的二进位数序列上作如下代换：０→０１→１０，→１１０然后在两端加上无限个０。如果我们把它列出，就能更清楚地看出，如何把这个应用到上面的磁带上：００００１００１０１１０１０１００１０１１００１１０１０１１０１０１１０１０００１１０００我将把这种数（的集合）的记号称为扩展二进位记号。（这样，例如13的扩展二进位形式为１０１００１０）关于这种编码还有最后一点必须提及。这只不过是个技巧，但是为了完备起见是需要的3。在自然数的二进位（或十进位）表示中处于表式最左端的0是不“算”的，它通常可被略去，这里有些多余。例如００１１００１０和１１００１０是两个相同的二进位数（而0050和50为相同的十进位数）。这一多余可适合于数0本身，它也可写成000或00。一个空白的空间的确也应该逻辑地表示0！在通常的记号下这会导致巨大的混淆，但是它和上面刚描述的记号可相安无事。这样，在两个逗号之间的0可只写成两个连在一起的逗号（，，），它在磁带上被编码成两对由单独的０隔开的１１：
…００１１０１１００…
这样，上面的六个数的集合也可用二进位记号写成１０１，１１０１，，１，１，１００，而且在磁带上可以扩展的二进位方式编码成…００００１００１０１１０１０１００１０１１０１１０１０１１０１０１１０１０００１１０００… （有一个０已从我们以前的序列中略去）。
现在我们可以考虑让一台图灵机，譬如讲欧几里德算法，把它应用到以扩展二进位记号写出的一对数上。例如，这一对数是我们早先考虑的6，8，不用以前用的…０００００００００００１１１１１１０１１１１１１１１０００００…
而考虑6和8的二进位表示，也就是分别为110和1000。这一对为6，8，在二进位记号也就是１１０，１０００扩展后在磁带上编码成…０００００１０１００１１０１００００１１００００００…
对于这一对特殊的数，并没有比一进位形式更紧凑。然而，譬如说我们取（十进位数）1583169和8610。在二进位记号中它们是１１０００００１０１００００１０００００１，１００００１１０１０００１０，这样，我们在磁带上把这一对编码成…００１０１００００００１００１０００００１００００００１０１１０１０００００１０１００１００００１００１１０…只要用一行就可将其全部写出， 而如果用一进位记号的话， 表示 “1583169，8610”的磁带用这一整本书都写不下。当数用扩展二进位记号表示时，一台执行欧几里德算法的图灵机，如果需要的话，可以简单地把适当的一对在一进位和扩展二进位之间互相翻译的子程序算法接到EUC上去而得到。然而，由于一进位计数系统的无效率仍在“内部”存在，并且在仪器的迟缓以及需要大量的外部“粗纸” （它是磁带的右手部分）方面表现出来，实际上这是极其无效率的。可以给出全部用扩展二进位运算的、更有效率的、欧几里德算法的图灵机，但是它在这里对我们并无特别启发之处。
相反地，为了阐明如何使一台图灵机能对扩展二进位数运算，让我们尝试某种比欧几里德算法简单得多的东西，即是对一个自然数加一的过程。这可由（我称之为XN＋1的）图灵机来执行：
0０→0０R，0１→1１R，1０→0０R，1１→10１R，10０→11０L，10１→10１R，11０→0１STOP，11１→100０L，100０→101１L，100１→100１L，101０→110０R，101１→10１R，110１→111１R，111０→11１R，111１→111０R，某些勤奋的读者可把它应用到，譬如讲数167上去，以再次验证这一台图灵机在实际上做到了所预想的。这一个数的二进位表示可由下面的磁带给出：
…００００１００１０００１０１０１０１１０００…
为了把一加到这个二进位数上，我们简单地找到最后的那个0，并把它改成1，然而用0来取代所有跟在后面的1。例如167＋1=168在二进位记号下写成１０１００１１１＋１=１０１０１０００。这样，我们的“加一”图灵机应把前面的磁带用…００００１００１００１００００１１０００００…来取代，它的确做到了这一点。
我们注意到，甚至这种简单加一的非常基本的运算在用这种记号时都会显得有些复杂，它使用了十五条指令和八种不同的内态！由于在一进位系统中“加一”只是把1的串再延长一个而已，事情当然是简单得多。所以我们的机器UN＋1更为基本，这一点也不奇怪。然而，对于非常大的数，由于所需的磁带非同寻常地长，UN＋1就会极慢。而用更紧凑的扩展二进位记号运算的更复杂的机器XN＋1就会更好。作为旁白，我愿意指出对于扩展二进位比一进位图灵机显得更简单的一个运算，这就是乘二。在这里由0０→0０R，0１→1０R，1０→0１R，1１→10０R，10０→11１R，11０→0１STOP，给出的图灵机XN×2能在扩展的二进位上实现这个运算，而前面描述的相应于一进位的机器UN×2就要复杂得多！
我们从这里得到了，关于图灵机在非常基础水平上可做到的一些事情的概念。正如预料得到的，当进行某些复杂的运算时，它们会变得极为复杂。这种仪器的终极能力是什么呢？让我们在下面讨论这一个问题。撤屈――图灵主题人们一旦对建造简单的图灵机稍有一些熟悉，下面这些事实就很容易使他们感到满意。特殊的图灵机的确能执行各种基本的算术运算，诸如把两个数加到一起，或把它们相乘，或求一个数的到另一个数的方次。显明提供其结果为一对自然数的运算，譬如带有余数的除法，或者其结果为任意大数目的数的有限集合。此外，可以这样地建造图灵机，即预先没有必要指定它要做何种运算，其运算的指令由磁带提供。需要实行的特定运算也许在某一阶段依赖于该机器在某个更早阶段的需要进行的某个计算的结果。（“如果那个计算的结果比某数大，则做这个；否则就做那个。”）
一旦人们理解到，他可制造实现算术或简单的逻辑运算的图灵机，则很容易想象如何使之进行具有算法性质的更复杂的任务。在他们捣弄了好一阵之后，很容易坚信，这类机器的确能实行不管什么样的机械运算！在数学上，可以很合情合理地把机械运算定义为可被这样的一台机器所执行的运算。数学家用名词“算法”以及形容词“可计算的”、“递归的”和“有效的”来表示能由这类理论机器――图灵机实行的机械运算。一个步骤只要是足够清楚并且机械的，则可合理地相信能找到一台执行它的图灵机。
这正是我们（也就是图灵）引进图灵机概念本身的初步讨论的全部要点。
另一方面，人们仍会感到，这些机器的设计不必这么局限。初看起来，只允许仪器在一个时刻读一个二进位位数（０或１），并且一次沿着一个单独的一维磁带只移动一格似乎是限制。为什么不允许大数目或相互联结的阅读机一下子跑过四条或五条甚至一千条分开的磁带呢？为什么不允许０和１的方格的整个平面（或者甚至一个三维的阵列），而坚持只用一维的磁带呢？为什么不允许从某种更复杂的计数系统或字母来的其他符号呢？事实上，虽然这些改变中的一些会对运算的经济性造成一定程度的不同（正如允许用多于一条的磁带一定会是这种情形那样），但是所有这一切都不会对我们在原则上要得到的东西造成丝毫的影响。即使我们在所有这些方面一下子推广该定义，这种归于“算法”的名下（或“计算”、“有效步骤”或“递归运算”）所实现的运算种类刚好和推广以前的完全相同！
我们可以看到，没有必要有多余一条的磁带。只要该仪器需要时总能在给定的磁带不断地找到新的空白。为此，也许必须不断地把数据从磁带的一处往另一处调度。这也许是“低效率的”，但是它不限制在原则上可以得到的极限4。类似地，利用多于一台并行动作的图灵机――这在近年由于和想更接近地仿照人脑试图相关联而变得很时髦――不能在原则上得到任何新东西（虽然在某种情形下可改善动作的速度）。拥有两台分开的、不直接相互联络的仪器并不比两台相互联络的得到更多，而且如果它们联络，则实际上只不过是一台单独的仪器！关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带代表“环境”，也许宁愿把它当作一个平面或许一个三维空间，而不当作一维磁带。一个平面似乎比一维磁带更接近于一个“流程图”（正如在上面对欧几里德算法运算的描述） 所需要的①。 然而， 在原则上没有困难以 “一维的”形式（也就是利用流程图的通常术语来描述）写出流程图的运行。在二维平面上显示只是为了我们的便利和容易理解，它对原则上能得到的并没造成什么影响。人们总能把一个二维平面上甚至三维空间上的一个记号或对象的地址，直截了当地在一维磁带上编码。（事实上，使用一个二维平面完全等效于用两根磁带。这两根磁带提供为在二维平面上指明一点所需的两个“座标”；正如三根磁带可作为一个三维空间的一点的“座标”
一样。）这一维的编码再次可能为“低效率的”，但是它在原则上不限制我们的目标。尽管所有这一切，我们仍然可心询问，图灵机的概念是否真的和我们希望叫做“机械的”每一逻辑或数学运算相统一。在图灵写他的开创性文章的时候，这一点比今天模糊得多，所以他觉得有必要把情形解释得更清楚一些。图灵的严密论证从以下事实得到了额外的支持，这就是美国逻辑学家阿伦佐？撤屈（在S。C。克利涅的协助下）完全独立地（并实际上稍早一些）提出了一种方案，也是旨在解决希尔伯特的判决问题的拉姆达计算。尽管它不如图灵的那么明显地为一种完全广泛的机械的方案，但在数学结构上的极端经济性方面有些优点。（我将在本章的结尾描述撤屈的杰出的计算。） 还存在其他一些解决希尔伯特问题的和图灵相独立的设想 （见甘迪1988），尤其是波兰――美国逻辑学家爱弥尔？波斯特的设想（比图灵稍晚些，但其思想和图灵比和撤屈更相像许多）。所有这些方案很快就被证明是完全等效的。 这就给现在称作撤屈――图灵主题的观点增加了许多份量，即图灵机（或等效的）概念实际在数学上定义了我们认为是算法（或有效、或递归、或机械的）步骤的东西。现在，高速电脑已变成我们生活中如此熟悉的部分，很少人似乎觉得有必要去问这些主题的原始形式。相反地，已有不少人转去注意真正的物理系统（假定包括人脑）――精确服从物理定律的东西――是否能够实行比图灵机更多、更少或刚好一样多的逻辑和数学运算。我本人是非常喜欢撤屈――图灵主题的原先的数学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本书主要关注的另外一个单独的问题。① 正如这里所描述的，这一流程图本身实际上是“仪器”的一部分，而不是外部环境的“磁带”。�
快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部!
温馨提示： 温看小说的同时发表评论，说出自己的看法和其它小伙伴们分享也不错哦！发表书评还可以获得积分和经验奖励，认真写原创书评 被采纳为精评可以获得大量金币、积分和经验奖励哦！