在电脑科学的行话中，术语硬件表示一台电脑，涉及的实在的机构（印 刷线路、晶体管、导线、磁性存储空间等等），包括了把所有东西都联结 起来的方法的全部细节。相应地，术语软件是指可在机器上进行的各种程 序。阿伦·图灵的一个杰出的发现便是，任何其硬件达到一定程度复杂性 和灵活性的机器，都等效于任何其他同类机器。这一等效性的含义是，对 于任何两台这样的机器 A 和 B，存在一段特别的软件，如果将其赋予机器 A， 就会使之完全像机器 B 一样地动作；类似地，还存在另一段特殊的软件， 如果将其赋予机器 B，就会使之和机器 A 完全一样地动作。我在这里用词 “完全一样”是指，对任何给定的输入（在对机器提供了转换软件之后再 提供它）机器的实际输出，而不是指每台机器用以产生这输出所花的时 间。如果任一台机器在任何阶段用光了用于计算的存储空间，我还允许其 召来一些（在原则上无限制的）外部空白空间的“粗纸”供应，可采用磁 带、磁盘、磁鼓或任何别的什么。事实上，对机器 A 和 B 执行同一任务所 需时间的不同值得严肃地加以考虑。例如，也许有这种情形，A 在执行一 特别任务时比 B 快一千倍；也许还有这种情形，同样的一对机器，存在某 一其他任务，这时 B 比 A 快一千倍。此外，这里计时可以极大地依赖于所 用的转换软件的选取。这是非常“原则的”讨论，人们不甚关心诸如在一 段合理的时间内完成他的计算的实际的事体。我将在下一章把在这里提到 的概念弄得更精确些：机器 A 和 B 是所谓普适图灵机的实例。
　　实际上，所有现代通用的电脑都是普适图灵机。这样，在上述的意义 上，所有通用的电脑都是互相等效的：假使我们不关心运算的速度和存储 空间的可能限制，则它们之间的差别可完全地被包摄到软件中去。的确， 现代技术已经使得电脑如此快速地运行，并具有如此庞大的储存能力，对 于大多数“日常”目的，这些实际考虑对于通常的需求不构成任何严重的 限制①，所以这种电脑之间有效的理论上的等价也可认为是在实践的水平上 的。技术仿佛已经把有关理想化的计算仪器的纯学术讨论转变或直接影响 我们生活的事体。
　　就我所知，作为强 AI 哲学基础的最重要因素之一是在物理计算仪器之 间的这种等价。硬件似乎相对地不重要（也许甚至完全不重要），而软件 也就是程序或者算法被认为是要紧的因素。然而，我似乎觉得还有从物理 的方向来的更多的重要的基础因素。我将指出这些因素是什么。
是什么东西赋于个别人其单独的认同性呢？在一定的程度上，是否正 是构成他身体的原子呢？他的认同性是否依赖于构成这些原子的电子、质 子和其他粒子的特殊选择呢？至少有两种理由说明不可能是这样子的。首




① 然而，参阅在第四章结尾处关于复杂性理论和 NP 问题的讨论。

先，任何活人身体的物质都处于连续代换的状态中。这尤其适用于一个人 脑的细胞中，尽管在出生后没有产生新头脑细胞的这一事实。在每一活细 胞（包括每一个头脑细胞）中的绝大多数原子以及实际上我们身体的整个 物质从诞生以来已被代换了许多回。
　　第二个理由来自于量子物理。而且极富讽刺意味的是，严格地讲，它 和第一个理由相冲突！按照量子力学（我们在第六章 322 页还要进一步地 讨论），任意两颗电子必须是完全等同的，这同样地适合于任意两颗质子 以及任一特殊种类的两颗粒子。这不仅仅说没有办法把两颗粒子区分开， 其陈述比这还要强许多。如果一颗人脑中的一颗电子和一块砖头中的一颗 电子相互交换，则系统的态和它过去的态不仅不能区分，而且完全相同
11。这同样适用于质子和任何其他种类的粒子，整个原子，分子等等。如 果一个人的整个物质内容和他房子里的砖头的相应的粒子相交换，那么在 某种强的意义上来讲，没有发生过任何事情。把人和他的房子区分开来的 是把这些成份安置的模式，而不是这些成份本身的个性。
　　在与量子力学无关的日常水平上也许存在一个相似的情景。这就是由 于电子技术使得我能以文字处理机来打字。当我写到这里时感到特别明 显。如果我必须改变一个词，譬如说把“make”改成“made”，我只要简 单地把“k”用“d”来取代即可以，或者我可重打整个词。如果我重打， 新的“m”是否和旧的“m”一样，或者我是否用同样的字母来取代了它呢？ “e”的情形又如何呢？即使如果我简单地用“d”来取代“k”，而不重打 这个词，存在刚好在“k”消失和“d”出现从而填上空隙之间的一个瞬息， 随着接续着的每一字母（包括“e”）的安置，存在（或者至少有时存在） 重排这页以下的波动。然后当“d”插进去时又再次重新计算。（呵，现代 没有思想的计算是多么的卑贱！）不管怎么样，在我面前屏幕上看到的所 有字母，随着它的每一秒钟的六十次扫描，仅仅是一个电子束的轨迹的缝 隙。如果我取走了任一字母并用同一字母取代之，在代换后的情形是否一 样，或仅仅和原先的不可区分？认为第二种观点（也就是“仅仅是不可区 分的”）可以和第一种观点（也就是“同样”）相区分似乎是痴人说梦。 至少在字母不变时可以合理地说这情形是同样的。而等同粒子的量子力学 的情形也是如此。把一颗粒子用另一颗等同粒子取代时量子态不受丝毫影 响。这情形的确被认为和以前的是同样的。（然而，正如我们在第六章将 要看到的，这一差异在量子力学的框架中实际上不是微不足道的。）
　　上述关于在一个人体中连续地置换原子的评论，是在经典的而不是量 子物理的框架下进行的。它是在似乎坚持每一原子的个性有意义的情形下 措词的。经典物理在这一描述的水平上把原子当作单独物体的近似是足够 好的，我们不会错得太离谱。假设原子在运动时和它们等同的伙伴分离得 相当开，那么由于在事实上每一颗原子的轨道是连续的，以至于人们想象 能够看守住每一颗并可以协调地认为它们坚持各自的本体。从量子力学的
　　
观点提到原子的个性只不过是一种方便的说法，但是在刚才考虑的水平上 它是一个足够协调的描述。
　　让我们接受这种观点，一个人的个性和人们想赋予他的物质成份的任 何个性无关。相反地，在某种意义上，它必须和那些成份的形态，让我们 讲在空间或空间——时间中的形态有关。（后面还要更多地讲到。）但是
强 AI 的支持者走得比这更远。如果这样一种形态的信息内容能被翻译成另 一种可能恢复成原状的形式，那么他们就能够宣称，这个人的个性必须维 持不动。这正如同我刚打的字母序列和我现在于我的文字处理机屏幕上看 到的展示是一样的。如果我把它们从屏幕上移开，它们被编码成某种微小 的电荷位移的形式，处在一种和我刚才打印的字母在几何上毫无类似性的 某种形态。然而，我可在任一时刻把它们移回到屏幕上去，它们在那里正 如同没有进行过任何变换一样。如果我选择把我才写下的存起来，那么我 可以把字母序列的讯息转移到一个以后我可取走的磁盘的磁化形态上去， 然后关掉机器就中和了在它上面的所有（有关的）微小电荷位移。第二天， 我可重新插入我的磁盘，复原小电荷位移并在屏幕上正如没有发生过任何 事一样重新展现字母序列。这对于强 AI 支持者而言是“清楚的”，一个人 的个性可用同样的方式处理。所以这些人会宣称，正如在我的显示屏幕上 的字母序列一样，如果一个人的身体形状被翻译成完全不同的某种东西， 譬如说一块铁的磁场，他的个性一点也没损失，实际上对他根本没有发生 过什么。他们甚至会宣称，当一个人的“信息”处于这不同的形式时，他 的意识知觉继续存留。一个“人的知觉”在这种观点中实际被当成一段软 件，而他作为一个物质的人的特殊的显现则被认为是通过他头脑和身体硬 件对这软件的运算。
　　作这些断言的原因仿佛是，不管硬件采取何种物质形式，例如某种电 子仪器，人们总可以“问”软件问题（以图灵检验的形式），并假定该硬 件能令人满意地进行计算以获得这些问题的答案。这些答案会和一个人处 于正常状态时所回答的相同。（“今天上午你感觉如何？”“哦，相当好， 谢谢，尽管我有一点讨厌的头痛。”“你对你的个人认同感和别的什么有 点不对头的地方吧？”“不；你为什么这样讲？这似乎是很古怪的问题。” “那么你感到你正是昨天的那个同一的你吧？”“当然是这样！”）
　　科学幻想的超距运送机 12 是一种被频繁讨论的观念。这是作为譬如讲 从一颗行星到另一颗行星的“运送”手段。所有的讨论都是关心它是否能 在实标上做到这样。旅行者不用空间飞船以“正常”方式运送其身体，而 是从头到脚地被扫描，他身体的每一原子和电子的准确位置和完整的特征 都被全部细致地记录下来。然后所有这些信息由一电磁信号束（以光速） 发射到目的地。在目的地把这信息收集到，并作为装配旅行者以及他所有 记忆、企图、希望和最内心的感情的复本的指导书。至少这就是所期望的， 因为他的头脑状态的每一细节都被完全忠实地记录、传送和重造了。假如
　　
这个机制能成功，则旅行者的原版可被“安全地”毁掉。显然的问题是： 这真的是从一处到另一处旅行的一种方法吗？或者它是否仅仅是制造一个 复本而把原先的人杀死？假定这种方法在这框架中被证明是完全可靠的， 你会准备用这种方法吗？如果超距运送不是旅行的话，那么在原则上它和 从一个房间走到另一个房间有何不同？在后者的情形，难道不是一个时刻 的原子简单地为下一时刻的原子提供定位的信息吗？我们毕竟看到了，维 持任何特殊原子的等同性都是没有任何意义的。原子的任何运动模式难道 不就是构成从一处到另一处传播的信息的波吗？在描述从一个房间随便遛 达到另一房间的我们旅行者的波动传播和发生在超距运送机中的有什么本 质的区别？
　　假定远距运送的确“可行”，那就是说，在一遥远行星的旅行者的复 本中他自身的“知觉”确实被重新唤醒（假设这是一个具有真正意义的问 题）。如果该旅行者的原版没有如这个游戏所需求的那样被毁坏，将会发 生什么呢？他的“知觉”是否会同时处于两个地方呢？（当你听到如下一 段话时想像看将会如何反应：“哦，亲爱的，在把你放到超距运送机前给 你的药已被消耗完了。是吗？那是有点不幸，但是没有关系。无论如何， 你将高兴地听到，另一个你，呃，我是说真正的你已经安全地到达了金星。 这样，我们可以把你，哦，我指的是多余的版本，安置在这儿。当然这是 完全不痛苦的。”）这种情景有一点佯谬的风味。物理学的定律中是否有 任何在原则上使得超距运送不可能的东西呢？另一方面，也许在原则上没 有东西反对以这种手段运送一个人以及他的意识，但是所涉及的“复制” 过程会不可避免地消灭原来的那个人吗？尽管这些考虑显得很奇异，我相 信从它们也许可得到某些关于意识和个性的物理性质的东西。我相信它们 提供了表示量子力学在理解精神现象的某种根本作用的指针。但是我更往 前多跨一步。我们只有在第六章（参见 311 页）考察了量子理论的结构后， 才能回到这些事体上来。
　　让我们看看强 AI 的观点与远距运送问题有什么关联。我们设想，在这 两个行星之间的某处有一转换站，在这里把信息暂时存储然后再传送到最 终的目的地。为了方便起见，这信息不用人的而是用某种磁或电的仪器的 方式存储。该旅行者的“知觉”是否会在和这一仪器的相关联中呈现呢？
强 AI 的支持者愿使我们相信，事情必须如此。他们说，我们想问该旅行者 的任何问题，在原则上都可由此仪器答复，“只要”对他的头脑的适当活 动建立模拟就可以了。该仪器会拥有所有必须的信息，而余下的只不过是 计算的问题。由于仪器会完全如同旅行者一样地回答问题，那么（图灵检 验！）它就是该旅行者。这完全回到了强 AI 的论点，在考虑精神现象时 硬件根本不重要。我觉得这一论点是未被证实的。它是基于如下的假设， 即头脑（或精神）实际上是一台数字电脑。他们假想，当一个人思维时并 没有引起特别的物理现象，也许头脑真正需要具备特殊的物理的（生物的、

化学的）结构。
　　人们无疑地会（从强 AI 观点）争论道，所做的仅有的假设是，任何必 须涉及的特殊物理现象的效应都可由数字电脑精密地仿照。我可以相当肯 定，大多数物理学家会论证道，在我们现在对物理理解的基础上作这样的 假设是非常自然的。我将在后面的章节提出我自己持相反观点的原因（我 在那里还需要把话题引到为何我相信甚至不必作任何假定）。但是，在此 刻我们暂且接受这一（普遍的）观点，即所有相关的物理总能由数字计算 来仿照。那么（除了时间和计算空间的问题外）这唯一真正的假设是一个 “行为主义”的问题，即如果某物全然像一个意识地知觉的本体那样地行 为，那么人们还应该坚持说它“感觉”到它自己是那一个本体。
　　强 AI 观点认为，在头脑运行中实际上被涉及的任何“仅仅”是作为硬 件问题的物理，必须能用合适的转换软件来模拟。如果我们接受这个行为 主义的观点，那么问题就归到普适图灵机的等价，以及任何算法可的确由 这种机器执行的事实，还有头脑按照某类算法动作行动的假设。现在到了 我要更明白地解释这些迷人的重要概念的时候了。


注 释
　　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 给出余数 924
1365÷924 给出余数 441
924÷441 给出余数 42
441÷42 给出余数 21
　　　　42÷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）。 类似地，这同一磁带可被用作最后输出（也就是“答案”）。只要必须进 行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最 后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上 显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所 有数据以及要解的问题的详细说明总是由右边进去。
　　让我们有限的仪器前后移动一条潜在地无穷长的磁带，我自己觉得有 点不舒服。不管其材料是多么轻，移动无限长的磁带是非常困难的！相反 地，我宁愿把磁带设想成代表某一外部环境，我们有限的仪器可以通过这 环境进行移动。（当然用现代电子学，既不需要“磁带”也不需要“仪器” 作实际的、在通常物理意义上的“运动”，但是这种“运动”是一种描述 事体的便利方法。）依此观点，该仪器完全是从这个环境接受它的输入。 它把环境当成它的“粗纸”。最后将其输出在这同一个环境中写出。
　　在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两 个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个 单独的记号①。我们可利用有记号或者没有记号的方格来阐释，我们的环境
（也就是磁带）可允许被细分并按照分立（和连续相反的）元素来描述。 如果希望仪器以一种可靠并绝对确定的方式工作。这似乎是合情理的要做 的事。然而，我们允许该“环境”是（潜在地）无限的，把这作为我们使 用的数学理想化的特征。但是，在任何特殊的情形下，输入、计算和输出 必须总是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该 有有限数目的实在的记号。磁带在每一个方向的一定点以外必须是空白
的。
　　我们用符号“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→00R
01→131L
10→651R
11→10R
20→01R STOP
21→661L
30→370R
··
··
··
2100→31
··
··
··
2580→00R.STOP
2590→971R
　　　　　　2591→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→00R
0１→1101１R
1０→1000001１L
1１→1０R
10０→0１STOPR
10１→1000010１L
11０→100101０R
··
··
··
11010010０→11１L
··
··
··
··

100000010１→0０STOP
100000011０→1100001１R
100000011１→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。
在 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），尤其是波兰——美国逻辑学家爱弥尔·波斯特的设想（比图 灵稍晚些，但其思想和图灵比和撤屈更相像许多）。所有这些方案很快就 被证明是完全等效的。这就给现在称作撤屈——图灵主题的观点增加了许 多份量，即图灵机（或等效的）概念实际在数学上定义了我们认为是算法
（或有效、或递归、或机械的）步骤的东西。现在，高速电脑已变成我们 生活中如此熟悉的部分，很少人似乎觉得有必要去问这些主题的原始形 式。相反地，已有不少人转去注意真正的物理系统（假定包括人脑）—— 精确服从物理定律的东西——是否能够实行比图灵机更多、更少或刚好一 样多的逻辑和数学运算。我本人是非常喜欢撤屈——图灵主题的原先的数 学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本书主 要关注的另外一个单独的问题。






① 正如这里所描述的，这一流程图本身实际上是“仪器”的一部分，而不是外部环境的“磁带”。我们在
磁带上表示的正是实际的数 A，B，A-B 等等。然而，我们还要以一个线性的一维形式来表达该仪器的详细 指明。正如我们将要看到的，和普适图灵机相关的，在一台特殊仪器的详细指明和对该仪器可能的“资料”
（或“程序”）的详细指明之间有个密切关系。所以，使这两者都处于一维形式是方便的。

不同于自然数的数


　　我们在上述的讨论中考虑了自然数的运算，并且注意到了这一显著的 事实，即尽管每台图灵机只有固定的有限数目的不同内态，它却可能处理 任意大小的自然数。然而，人们经常需要使用比这更复杂的其他种类的数， 诸如负数、分数或无理数。图灵机可以容易地处理负数和分数（例如像-
597/26），而且我们可取任意大的分母和分子。我们所要做的全部是对“-” 和“/”作适当的编码。这可容易地利用早先描述的扩展二进位记号做到（例 如，“3”表示“-”以及“4”表示“/”，它们分别在扩展二进位记号中 编码成 1110 和 11110）。人们就是这样地按照自然数的有限集合来处理负 数和分数的。这样，就可计算性的一般问题而言，它们没有告诉我们什么 新的东西。
　　类似地，由于长度不受限制的有限小数表式仅仅是分数的特殊情形， 它们并没给我们带来什么新问题。例如，无理数π的由 3.14159265 给出的 有限小数近似，简单地就是分数 314159265/100000000。然而，无限小数 表式，譬如完全无限展开
　　　　　　　　　　　π=3.14159265358979? 出现了一定的困难。严格地讲，无论是图灵机的输入或者输出都不是无限 小数。人们也许会想到，我们可以找到一台图灵机，在其输出磁带上产生 由π的小数展开的、所有的一个接一个位数 3，1，4，1，5，9，?。我们 就简单地让机器一直开下去好了。但这对于一台图灵机来讲，是不允许 的。我们必须等待机器停了以后（铃声响过！）才允许去检查输出。只要 机器还没有到达停止命令，其输出就可能要遭受到改变，所以不能对它信 任。另一方面，在它到达停止时，其输出必须是有限的。
　　然而，存在一种合法地使图灵机以与此非常类似的方法，一个位数跟 着另一个位数产生位数的步骤。如果我们希望产生一个数，譬如讲π的无 限小数展开，我们可以让一台图灵机作用于 0 上以产生整数部分了；然后 使机器作用到 1 上，产生第一小数位 1；然后使其作用于 2 上，产生第二 小数位 4；然后作用于 3 上，产生 1，这样不断地下去。事实上，一定存 在在这个意义上产生π的全部小数展开的图灵机，尽管要把它明显地造出
来颇费一点周折。类似的评论也适用于许多其他无理数，譬如 2
=1.414213562?。然而，正如在下一章将要看到的，人们发现有些无理数
（非常引人注目地）根本不能由任何图灵机产生。能以这种方式产生的数 叫作可计算的（图灵 1937）。那些不能的（实际上是绝大多数！）是叫作 不可计算的。我们将在后面的章节中回到这件事体及有关的问题上来。按 照物理理论，用可计算的数学结构能否足够地描述实在的物理对象（也就 是人脑），是我们要关心的问题。
一般地讲，可计算性是数学中的一个重要问题。人们不应该只将其当

成只适合于这类数的事体。人们可有直接作用于诸如代数或三角的数学公 式上的图灵机，或可进行微积分的形式运算的图灵机。人们所需的一切是 某种准确地把所有涉及的数学符号编码成 0 和 1 序列的形式，然后再利用 图灵机的概念。这毕竟是图灵在着手解决判决问题时心里所想的，即寻求 回答具有一般性质的数学问题的算法步骤。我们将很快地回到这上面来。

普适图灵机


　　我还未描述普适图灵机的概念。虽然其细节是复杂的，但是它背后的 原则并不十分复杂。它的基本思想是把任意一台图灵机 T 的指令的表编码 成在磁带上表示成 0 和 1 的串。然后这段磁带被当作某一台特殊的被称作 普适图灵机 U 的输入的开始部分，接着这台机器正如 T 所要进行的那样， 作用于输入的余下部分。普适图灵机是万有的模仿者。“磁带”的开始部 分赋予该普适机器 U 需要用以准确模拟任何给定机器 T 的全部信息！
　　为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方 式。考虑定义某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我 们必须按照某种准确的方案把这表编码成 0 和 1 的串。我们可借助于以前 采用的“收缩”步骤来办到。因为，如果我们用数 2，3，4，5 和 6 来分别 代表符号 R、L、STOP、箭头（→）以及逗点，那么我们就可以用１１０、
１１１０、１１１１０、１１１１１０以及１１１１１１０的收缩把它们 编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成０ 和１０的位数 0 和１。由于在该图灵机的表中，在二进位计数的结尾大写 的数的位置足以把大写的０和１从其他小写的阿拉伯数字中区分开来，所 以我们不需要用不同的记号。这样，110１将被读成二进位数 1101，而在 磁带上被编码成１０１００１０。特别是，0０读作 00，它可毫不含糊地 被编码成０，或者作为被完全省略的符号。实际上我们可以不必对任何箭 头或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些 符号必须是什么。尽管在采用这个步骤时，在必要之处要提供一些额外的 “哑”指令，以保证在这个顺序中没有缝隙。这样的做法具有相当好的经 济性。（例如，图灵机 XN+1 没有告诉我们对 110０要做什么的命令，这是 因为这条指令在机器运行时从不发生，所以我们应该插入一条“哑”指令， 譬如讲 110０→0０R，它可合并到表中而不改变任何东西。类似地，我们 应该把 10１→0０R 插入到 XN×2 中去。）若没有这些“哑的”，表中后面 的指令的编码就会被糟蹋了。因为在结尾处的符号 L 或 R 足以把一条指令 和另一条隔开，所以我们在每一指令中实际不需要逗号。因此，我们采用 下面的编码：
０表示 0 或０，１０表示 1 或１，１１０表示 R，１１１０表示 L，１
１１１０表示 stop。
　　作为一个例子，让我们为图灵机 XN+1 编码（插入指令 110０→0０R）。 在去掉箭头和在它们紧前面的位数以及逗号之后，我们得到
0０R 1１R 0０R 10１R 11０L 10１R 0１STOP
100０L 101１L 100１L110０R10１R0０R111１R
　　11１R 111０R 为了和早先说的相一致，我们可以去掉每一个００，并把每一个 01 简单地
　　
用 1 来取代，这样得到 R1１RR10１R11０L10１R１STOP100０L101１L1
　　00１L110０R10１RR111１R11１R111０R 如下是在磁带上的相应的码：
１１０１０１０１１０１１０１００１０１１０１０１００１１１０１０
０１０１１０１０１１１１０１００００１１１０１００１０１０１１１
０１０００１０１１１０１０１０００１１０１００１０１１０１１０１
０１０１０１０１１０１０１０１０１１０１０１０１００１１０ 我们总是可以把开始的１１０（以及它之前的无限的空白磁带）删去。由 于它表示 0０R，这代表开头的指令 0０→0０R。而我已隐含地把它当作所 有图灵机共有的。这样仪器可从磁带记号左边任意远的地方向右跑到第一 个记号为止。而且，由于所有图灵机都应该把它们的描述用最后的１１０ 结束（因为它们所有都用 R、L 或 STOP 来结束），所以我们也可把它（以 及假想跟在后面的０的无限序列）删去。这可以算作两个小节约。所得到 的二进位数是该图灵机的号码，它在 XN+1 的情况下为：
１０１０１１０１１０１００１０１１０１０１００１１１０１００１０
１１０１０１１１１０１００００１１１０１００１０１０１１１０１０
００１０１１１０１０１０００１１０１００１０１１０１１０１０１０
１０１０１１０１０１０１１０１０１０１００。 这一特殊的数在标准十进位记号下为
　　450813704461563958982113775643437908。 我们有时不严格地把号码为 n 的图灵机称为第 n 台图灵机，并用 Tn 来表
示。这样，XN+1 是第 450813704461563958982113775643437908 台图灵机！ 我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如 此平凡的（在扩展二进位记号上）对自然数加一的运算，这真使人印象深 刻！（尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得 相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN+1 的二
进位号码为
１０１０１１０１０１１１１０１０１０
它只是十进位制的 177642！这样，只不过是把一个附加的 1 加到序列 1 的 尾巴上的特别平凡的图灵机 UN+1 是第 177642 台图灵机。为了好奇的原因， 我们可以注意在任一种进位制中“乘二”是在图灵机表中这两个号码之间 的某处。我们找到 XN×2 的号码为 10389728107，而 UN×2 的号码为
1492923420919872026917547669。 人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数
根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的十三台 图灵机列出来：
T0：0０→0０R，0１→0０R，

T1：0０→0０R，0１→0０L， T2：0０→0０R，0１→0１R， T3：0０→0０R，0１→0０STOP， T4：0０→0０R，0１→1０R， T5：0０→0０R，0１→0１L， T6：0０→0０R，0１→0０R，1０→0０R， T7：0０→0０R，0１→？？？， T8：0０→0０R，0１→10０R， T9：0０→0０R，0１→1０L， T10：0０→0０R，0１→1１R， T11：0０→0０R，0１→0１STOP， T12：0０→0０R，0１→0０R，1０→0０R。
　　其中，T0 简单地就是向右移动并且抹去它所遇到的每一件东西，永不 停止并永不往回退。机器 T1 最终得到同样的效应。但它是以更笨拙的方 法，在它抹去磁带上的每个记号后再往后跳回。机器 T2 也和机器 T0 一样无
限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。 由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T3 是第一台可敬的机器。它的确是在改变第一个（最左边）的１为０后便谦
虚地停止。
T4 遭遇了严重的问题。它在磁带上找到第一个１后就进入了一个没有
列表的内态，所以它没有下一步要做什么的指令。T8、T9 和 T10 遇到同样的
问题。T7 的困难甚至更基本。把它编码的０和１的串涉及到五个接续的１
的序列：１１０１１１１１０。对于这种序列不存在任何解释，所以只要 它在磁带上发现第一个 1 就被绊住。（我把 T7 或其他任何机器 Tn，它的 n 的二进位展开包含多于四个１的序列称为不是正确指明的。）机器 T5、T6
和 T12 遭遇到和 T0、T1 和 T2 类似的问题。它们简单地、无限地、永远不停 地跑下去。所有 T0、T1、T2、T4、T5、T6、T7、78、T9、T10 和 T12 都是伪品！ 只有 T3 和 T11 是可工作的，但不是非常有趣的图灵机。T11 甚至比 T3 更谦虚，
它在第一次遇到 1 时就停止，并且没有改变任何东西！ 我们应该注意到，在表中还有一个多余。由于 T6 和 T12 从未进入内态
1，机器 T12 和 T6 等同，并在行为上和 T0 等同。我们既不必为这个多余，
也不必为表中的图灵机伪品而烦恼。人们的确可以改善编码以摆脱许多伪 品和大大减少重复。所有这些都是以使我们可怜的普适图灵机变得更复杂 作为代价。普适图灵机必须把所读到的号码 n 解码并假装成图灵机 Tn。如
果我们可以把所有伪品（或者多余量）取走，这还是值得做的。但是，我 们很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。
例如，可方便地把具有
?０００１１０１１１００１００００?