凑漳忱嗨惴ǘ餍卸募偕琛Ｏ衷诘搅宋乙靼椎亟馐驼庑┟匀说闹匾拍畹氖焙蛄恕�
注 释1．例如，参阅伽特纳（1958），格里高里（1981）以及所引用的参考文献。
2．例如，参阅雷斯尼柯夫和韦尔斯（1984）181―184页。有关计算奇才的经典总结参阅罗斯？玻勒（1892）以及斯密斯（1983）。3．参阅格里高里（1981）285―287页，格雷？瓦尔特（1953）。
4．这个例子引用自德尔伯吕克（1986）。
5．参阅奥柯涅夫（1988）和基奈（1988）。参阅列维更多的有关电脑下棋的情形。6．当然，大部分奕棋问题都被设计得使人类很难解决。要去构造一种人类觉得不是极难、而现代解决下棋问题的电脑在一千年内也解不出的下棋问题似乎不太困难。（所需要的是一个每下一着都要筹划非常多步的、但又是相当明显的方案。例如，已经知道一些需要筹划大约200步就绰绰有余的问题！）这提出了一个有趣的挑战。
7．为了明确起见，我在本书从头到尾地采用了西尔勒的术语“强AI”
以表示这一极端观点。术语“机能主义”也被经常地用于表示本质上同样的观点，但也许不总是这么明确。明斯基（1968），伏多（1983）以及霍弗斯达特（1979）是这类观点的一些倡导者。
8．可从西尔勒（1987）211页找到这种宣称的一个例子。
9．道格拉斯？霍弗斯达特在对西尔勒的复印在《精神》上的原始论文的批评中抱怨道，由于涉及到的复杂性，没有一个人可想象把另外的一颗人脑的整个描述“内在化”。的确不能！但是就我所见，这不是问题的全部。人们仅仅关心实行目前要体现单个精神事件发生的一段算法的那个部分。这可以是在回答图灵检验问题时某个瞬息的“意识实现”，或者它可以是某种更简单的东西。任何这种“事件”是否都需要一段极其复杂的算法呢？10．参见载于霍弗斯达特和德涅特（1981）368和372页的西尔勒（1980）的论文。11．有些关于这类事体博学的读者也许会忧虑符号不同的问题。但是，如果我们在进行交换的同时，使其中的一颗电子旋转360°，甚至那个 （可争论的）区别也消失了！（参见第六章322页的解释。）
12．参见霍弗斯达特和德涅特（1981）的导言。
第二章算法和图灵机算法概念的背景
算法、图灵机或者普适图灵机究竟是什么呢？为何这些概念在可以构成“思维仪器”的东西的现代观点中占有如此核心的地位呢？是否在原则上存在一个算法可达到的绝对极限呢？为了充分地讨论这些问题，我们必须比较细致地考察算法和图灵机的观念。我在下面的各种讨论中，有时将要用到一些数学表达式。我注意到有些读者排斥这类东西，或者觉得它们吓人。如果你是这种读者，那么我请你原谅，并请你按照我在“敬启读者”中的建议。其实，这里论证所需的数学知识并不超过小学水平，但要仔细地弄通它们，则需要一些认真的思考。事实上，大部分描述是十分显明的，只要细心地跟随就能很好地理解。
但是，如果人们只是为了稍微领略其风味而取其精华，也能有很大的收益。
另一方面，如果你是一位专家，我还要请你原谅。我猜想，它仍然值得你花一段时间把我所说的看过一遍，并且可能会有一两件东西引起你的兴趣。
“算法”这个词来自于九世纪波斯数学家阿布？雅发？穆罕默德？依伯恩？缪莎？阿勒――霍瓦里松，他在公元825年左右写了一本影响深远的《代数对话录》。“算法”这个字现在之所以被拼写成“algorithm”，而不是早先的更精确的“algorism”，似乎是由于和“算术” （arithmetic）相关联所引起的。（还值得指出的是，“代数”（algebra）这个词来源于该书的题目的阿拉伯字“al jabr”。）然而，比阿勒――霍瓦里松的书早很多就知道了算法的实例。现在被称作欧几里德算法的找两个数最大公约数的步骤是在古希腊（公元前300年左右）即有记载的一个最熟知的例子。让我们看看这是如何进行的。随意取两个特定的数，譬如讲1365和3654。所谓的最大公约数是可以同时整除这两个数的最大的整数。在应用欧几里德算法时，我们让这两数中的一个被另一个除并取余数，在3654中取出1365的两倍，其余数为924（=3654…2730）。我们现在用此余数即924以及我们刚用的除数即1365去取代原先的两个数。我们用这一对新的数重复上述步骤，用924去除1365，余数为441。这又得到新的一对441和924，我们用441除924，得到余数42（=924…882），等等，直到能够被整除为止。我们把这一切如下列出：
3654÷1365 给出余数9241365÷924 给出余数441924÷441 给出余数42441÷42 给出余数2142÷21 给出余数0。
我们最后用于做除数的21即是所需要的最大公约数。欧几里德算法本身是我们寻找这一因子的系统步骤。我们刚才把这一步骤应用于特殊的一对数，但是这步骤本身可被十分广泛地应用于任意大小的数。对于非常大的数，要花很长时间来执行该步骤，数字越大则所花的时间越长。但在任何特定的情形下，该步骤最后会终结，并在有限的步骤内得到一个确定的答复。每一步骤所要进行的运算都是非常明了的。此外，尽管它可应用到大小没有限制的自然数上去的这个事实，但是可以用有限的术语来描述整个过程。（“自然数”简单地就是通常的非负1整数0，1，2，3，4，5，6，7，8，9，10，11……）。的确很容易建立一个（有限的）描述欧几里德算法全部逻辑运算的“流程图”。
应该提到，我们在这里隐含地假定，已经“知道”如何实行从两个任意自然数A和B的除法中得到余数的必须的基本运算，所以这一步骤还未完全被分解成最基本的部分。那种运算又是算法的，是用我们在小学学到的除法的非常熟悉的步骤来进行的。在实际上，这个步骤比欧几里德的其他部分更复杂不少，但是可以再为它建立一个流程图。其复杂性主要起源于这个事实，即我们是（假定）对自然数用标准的“十进位”记号，这样子我们需要列出全部的乘法表和忧虑移位等等。如果我们简单地用一连串某种n个记号来代表数n，例如……代表五，那么可从非常初等的算法运算看到余数的形成。为了得到当A被B除时的余数，可以简单地从代表A的记号中不断取走代表B的符号串，直到最后余下的记号不够再进行这种运算为止。最后剩下的符号串提供了所需的答案。例如，为了得到十七被五除的余数，我们可以简单地从……………不断地取走五的序列……正如下面所示：
………………
……………
…………．．由于我们不能再继续这种运算，所以很清楚，其答案是二。
用这种连续减法找到除法余数的流程图可由下图给出：
为了使欧几里德算法的全部流程图完整，我们把上面形成余数的流程图代入到原先流程图的中右部的盒子中去。这种把一个算法向另一个代入是一种普遍的编电脑程序的步骤。上述寻求余数的算法是一道子程序的例子，也就是说，它是由主程序当作它的运算的一部分（通常是预先知道的）召来使用的算法。
当然，把数n简单地用n个斑点来表示，在涉及到大数时效率非常低，这就是为什么我们通常用更紧凑的诸如标准的（十进位）系统的原因。然而，我们在这里并不特别关心运算或记号的效率。我们所关心的是运算在原则上是否可被算法地实行的问题。如果我们用一种数的记号是算法的东西，则用另一种记号也是算法的。两种情况中只有在细节上和复杂性上有差别。欧几里德算法只是在整个数学中可找到的大量的经典算法步骤之一。
尽管算法的这一特殊例子的历史渊源， 一般算法概念的准确表达只从本世纪起才有记载，也许这是令人印象深刻的。事实上，这一概念的各种不同描述都是在本世纪三十年代给出的。称作图灵机的概念是最直接的、最有说服力的、也是历史上最重要的。相当仔细地考查这些“机器”将是很适当的。
关于图灵 “机” 有一件事必须记在心里， 就是说它是一段 “抽象数学”，而不是一个物理对象。这一概念是由英国数学家、非凡的破码专家兼电脑科学的开山鼻祖阿伦？图灵在1935―1936年间提出的（图灵1937）。其目的是为了解决称为判决问题的一个范围广阔的问题。它是由伟大的德国数学家大卫？希尔伯特部分地于1900年巴黎国际数学家会议上（“希尔伯特第十问题”），更完整地于1928年玻罗那国际会议上提出的。希尔伯特不多不少地要求解决数学问题的一般算法步骤，或者不如讲，是否在原则上存在这样步骤的问题。希尔伯特还有一个要把数学置于无懈可击的坚固基础上的宏伟规划，其中公理和步骤法则一旦定下就不能变。但是在图灵完成其伟大的工作之际，这个规划已经遭受到由奥地利才气焕发的逻辑学家库尔特？哥德尔在1931年证明的令人吃惊的定理的粉碎性打击。我们将在
第四章考虑哥德尔定理及其意义。图灵关心的希尔伯特问题（判决问
题）超越出任何按照公理系统的特殊的数学形式。问题在于，是否存在能在原则上一个接一个地解决所有（属于某种适当定义的族的）数学问题的某种一般的机械步骤？
回答这一问题的部分困难在于决定什么叫做“机械过程”。这概念处于当时正常的数学概念之外。为了掌握它，图灵设想如何才能把“机器”的概念表达出来，它的动作被分解成基本的项目。这一些似乎是清楚的，图灵也把人脑当成在他意义上的“机器”的例子。这样，由人类数学家在解决数学问题时进行的任何活动，都可以被冠以“机械步骤”之名。
虽然这一有关人类思维的观点似乎对于图灵发展他的极重要概念很有价值，我们却绝没有必要去附和它。的确，图灵在把机械过程的含义弄精确时，向我们展示出存在一些完好定义的数学运算，在任何通常的意义上，都不能被称为机械的！图灵本人的这一方面工作现在可间接地为我们提供了他自己有关精神现象性质观点的漏洞。这个事实也许不无讽刺意味。然而，这不是我们此刻所关心的。我们首先要弄清图灵心目中的机械过程究竟是什么。图灵概念我们设想实现某种（可以有限地定义的）计算步骤的一台仪器。这样仪器会采取什么样的一般形式呢？我们必须准备理想化一些，而且不必为实用性过份担心：我们是真正地考虑一台数学上理想化的“机器”。我们要求该仪器具有有限 （虽然也许非常大的）数目的不同可能态的分立集合。
我们把这些称作仪器的内态。但是我们不限制该仪器在原则上要实现的计算的尺度。回顾一下上述的欧几里德算法。在原则上不存在被该算法作用的数的大小的限制。不管这些数有多大，算法或者一般计算步骤都是同样的。对于非常大的数，该步骤的确要用非常长的时间，而且需要在数量可观的“粗纸”上面进行实际的计算。但是不管这些数有多大，该算法是指令的同一有限集合。这样，虽然我们仪器只有有限个内态，它却能够处理大小不受限制的输入。 此外， 为了计算应允许该仪器召来无限的外存空间 （我们的 “粗纸”）；而且能够产生大小不受限制的输出。由于该仪器只有有限数目的不同的内态，不能指望它把所有外部数据和所有自己计算的结果“内化”。相反地，它必须只考察那些立即处理的数据部分或者早先的计算，然后进行需要对它们进行的任何运算。也许可在外存空间把那个运算的相关结果记下来，然后以一种精确决定的方式进行下一个阶段的运算。正是输入、计算空间和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际上可真正建造的某种东西（见图2。1）。但这是极其关键的理想化。对于大多数实用目的而言，当代电脑技术的奇迹为我们提供了无限的电子存储仪器。
事实上，在上述讨论中称为“外部的”存储空间的类型，可实际上被认为是现代电脑的内部工作的一部分。存储空间的某一确定部分是否被当作内部的或外部的， 也许只是术语的问题。 按照硬件和软件是划分 “仪器”和“外部”的一种方法。内部可当成硬体，而外部为软体。我将不必拘泥于此，但是不管从那个角度看，当代电子电脑是图灵的理想化的极好近似。图2。1一台严格的图灵机需要无限的磁带图灵是按照在上面作记号的 “磁带”来描述其外部数据和存储空间的。一旦需要，仪器就会把该磁带召来“阅读”，而且作为其运算的一部分，磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号，允许同一磁带像外存（也就是“粗纸”）以及输入那样动作。因为在许多运算中，一个计算的中间结果起的作用正如同新的数据，所以事实上在“外存”和“输入”之间不做任何清楚的区分也许是有益的。我们记得在欧几里德算法中，不断地用计算不同阶段的结果去取代原先的输入（数A和B）。
类似地，这同一磁带可被用作最后输出（也就是“答案”）。只要必须进行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。
让我们有限的仪器前后移动一条潜在地无穷长的磁带，我自己觉得有点不舒服。不管其材料是多么轻，移动无限长的磁带是非常困难的！相反地，我宁愿把磁带设想成代表�