引言

研究过计算机的历史、技术或理论的人，都会接触到“图灵机”这个概念。在1936年，为帮助解决数理逻辑中的一个问题，英国数学家阿兰·图灵（1912—1954）提出了图灵机。它是一种纯属虚构的计算机，连计算机假设也算不上。而由此得到的意外收获是，图灵创立了一个新的研究领域——计算理论（或可计算性），它主要研究数字计算机的功能和局限性。

尽管图灵机是一种并不太合理的计算机，但由于其自身极其简单而大放异彩。最基本的图灵机只能进行一些简单的操作。如果连这些操作都不能做，那么这台机器干脆什么都别做了。然而，只要将这些简单的操作组合起来，图灵机就能够进行现代数字计算机可以执行的任何计算。

拨开云雾见天日，通过考查计算机的原始基础，我们就能够更好地理解数字计算机的能力和局限性，这二者同样重要。尽管有人早就论证过计算机可以做什么，但在这种论证出现多年之前，图灵就证明了计算机永远都做不到的事。

图灵机仍然是被阐述和探讨的热门话题，你可以试试用喜爱的网络搜索引擎搜索“图灵机”。然而，我猜很少有人会阅读阿兰·图灵描述他这项创造的原始论文。或许，这与论文的标题“On Computable Numbers, with an Application to the Entscheidungsproblem”（“论可计算数及其在判定性问题上的应用”）有关。即使你会读最后那个单词（试试看，将重音放在第二个音节上，把这个音节发成类似“shy”的音，这就差不多了），并且知道它的意思（即判定性问题），你可能也会担心，图灵一定指望他的读者对繁冗的德国数学问题有基本的了解。快速浏览这篇论文（其中还用到了德国哥特式字体来表示机器状态）也无法让人消除这种担心。今天的读者还能手捧70年前伦敦数学学会集刊中的文章，并坚持看到有所收获，甚至十分满意吗？

这本书要讲的正是这篇论文。它包含了图灵原版36页的论文¹“On Computable Numbers, with an Application to the Entscheidungsproblem”和增补的3页修订²，并辅以背景材料和大量注解。阅读图灵的原版论文就是在探索他构建图灵机的思维过程，就像在他充满想象、内容丰富的思想中进行一次奇特的旅行。图灵机不仅对计算产生了深远的影响，还深深影响了我们对数学局限性、人类思维方式，甚至宇宙本质的理解。（当然，图灵的论文中并没有出现“图灵机”这个术语，他称之为“计算机器”。不过，早在1937年³人们就开始使用“图灵机”这种说法，并且至今仍是标准术语。）

¹ 阿兰·图灵，“On Computable Numbers, with an Application to the Entscheidungsproblem”，Proceedings of the London Mathematical Society，2nd series，Vol.42（1936），pp.230-265。

² 阿兰·图灵，“On Computable Numbers, with an Application to the Entscheidungsproblem A Correction”，Proceedings of the London Mathematical Society，2nd series，Vol.43，(1937)，pp.544-546。

³ 阿隆佐·邱奇对“On Computable Numbers, with an Application to the Entscheidungsproblem”，一文的评论，The Journal of Symbolic Logic，Vol. 2，No. 1，1937年3月，42-43。

我在对图灵论文进行注释的过程中，发现用解释和阐述频繁打断他的叙述还是很有用的。我努力做到（但并没有完全做到）不打断他的某一整句话。大部分情况下，我会在讨论中保留图灵自己的术语和符号，不过有时，虽然图灵没有采用某个术语，如果我觉得这个术语在解释其工作时很有用，也会引入这些术语。

图灵论文的内容会像下面这样表示。

为了避免混淆，我们会更多地提及可计算序列，而非可计算数。

我们（指出版商和我）努力保留图灵原始论文的字体和版式，⁴除非有一些奇怪的表示方法（比如冒号前加空格）在现代文字处理软件中总报错。原稿中所有的行间距也得以保留。图灵的论文中存在一些印刷错误、技术性错误和理论上的疏漏，尽管我没有在原文中加以修正，但会在评注中一一指出。图灵对他自己论文内容的引用，仍沿用原发表期刊中的页码，我没有修改这些引用，不过在评注中指出了被引用部分在本书中的页码。偶尔，你会在图灵的论文中发现一个括起来的数字，例如：

⁴ 中文版依然保留图灵原始论文的印刷体和排版，其下是中译文，译文不再保留页码和版式。——编者注

如果用数字代替这些字母，如在§5中，那么我们可以得到这个完全格局的数字表示，也可以称作它的描述数。

这是原论文的分页处以及标注的页码。我这本书的脚注采用的是圆圈编号，而图灵论文的脚注使用符号标注，并写在阴影部分。

如果只保留本书阴影部分的英文内容，再组合起来，得到的就是完整的图灵论文，而我这个劳而无功的作者只能欲哭无泪了。更有趣的阅读方式是，先读本书，再读没有被我打断的图灵论文。

图灵的论文分散在本书的第4~15章，其修订内容在第16章。他的论文分为11个部分和一个附录，对应到本书的页码是：

图灵写这篇论文的最初动机是想解决德国数学家大卫·希尔伯特（1862—1943）构想的一个问题。希尔伯特想寻找一种通用的方法来判定数理逻辑中的任意命题是否可证。寻找这种“通用的方法”被称为判定性问题。尽管判定性问题确实是图灵写这篇论文的动机，但是这篇长篇大论本身讲的却是可计算数。在图灵的定义中，可计算数就是可以使用机器计算的数。论文前面60%的内容都是图灵对可计算数的探索，就算完全不了解希尔伯特在数理逻辑或判定性问题方面的研究，也能够阅读并理解这些内容。

了解可计算数与“实数”的区别对于理解图灵的观点很重要。因此，本书利用前几章介绍了数字分类的背景知识，数字包括整数、有理数、无理数、代数数和超越数，它们都可归为实数。我尽可能不涉及比高中数学更复杂的知识。我知道，有些读者离开快乐的高中生活已经几十年了，我要努力唤醒这些记忆。如果由于我本着这种教育热情而做出一些冒犯读者的解释，我表示歉意。

尽管我觉得本书的读者大多会是计算机科学专业的学生、程序员或其他技术人员，但是我还是尽量让非程序员的读者也愿意读，因此我定义了一些便于理解的术语。图灵的论文被誉为“20世纪的一座知识地标”⁵，我希望本书可以让更多的读者领略到这篇论文的风采。

⁵ 这一说法是John P. Burgess在George S. Boolos、John P. Burgess和Richard C. Jeffrey所著的 Computability and Logic, fourth edition（Cambridge University Press，2002）一书的前言中提到的。

为了满足不同读者的需要，本书分成了四个部分。

第一部分“基础”介绍阅读图灵论文所必须掌握的一些历史和数学背景知识。

第二部分“可计算数”包含了图灵论文的大部分内容，也是关心图灵机和可计算性相关问题的读者最感兴趣的部分。

第三部分“判定性问题”先简要介绍了数理逻辑的背景知识，然后讨论图灵论文的剩余部分。

第四部分“题外话”讨论了图灵机为何成为人们理解计算机、人类意识和宇宙本身的必要工具。

第三部分的数学内容肯定是比前几章的难，并且讲得比较快。对图灵论文在数理逻辑方面的影响不感兴趣的读者甚至可以跳过第三部分，直接阅读第四部分。

本书涉及数学中几个大的研究领域，包括可计算性和数理逻辑。我仅仅把与理解图灵论文最相关的那些主题和概念挑出来加以解释，省去了很多细节，因此本书从深度和严格性上都无法取代那些可计算性和逻辑方面的专业书籍。想深入研究这些领域的读者可以查阅参考文献。

阿兰·图灵一生发表过近30篇论文和文章⁶，却从未写过书。其中的两篇论文造就了他流芳百世的声望。“On Computable Numbers”（“论可计算数”）当然是第一篇。第二篇名为“Computing Machinery and Intelligence”（“计算机器和智能”，发表于1950年），这一篇的技术性不是很强，图灵在文中首次提出了一种判断人工智能的标准，在今天被称为“图灵测试”。总的来说，一台机器如果可以骗得我们相信它是一个人，那么就可以说它是智能的。

⁶ 这些和其他文档可以从The Collected Works of A.M. Turing（Amsterdam: Elsevier，1992，2001）的4卷中获得。其中大部分重要资料由B. Jack Copeland收集到The Essential Turing（Oxford University Press，2004）和Alan Turing's Automatic Computing Engine（Oxford University Press，2005）中。前者包含了与图灵机相关的文章和论文，后者是关于20世纪40年代中后期ACE计算机工程的。

图灵机和图灵测试是阿兰·图灵声名不朽的两大基石。初看上去，它们像是两个完全不同的概念，但事实并非如此。图灵机是以一种非常机械的方式展现人类如何进行数学运算的，图灵测试则是对计算机能力的人为评估。在整个数学研究期间，图灵都在探索人类思维和计算机器之间的关系，他所采用的研究方法至今仍很吸引人。

很多关于可计算性的教科书只讨论图灵的研究而不涉及图灵这个人，它们可没有劳神讲述有关个人传记的细节。不过，本书不会这么做。图灵在二战期间所做的密码分析方面的秘密工作，他参与的影响力巨大的计算机工程，他对于人工智能的思索，他的性取向，他由于“严重猥亵”罪而被逮捕和起诉的经历，以及他在41岁时自杀身亡，所有这些事情都需要关注。

得益于英国数学家安德鲁·霍奇斯（1949—　）撰写的精彩传记Alan Turing: The Enigma（《艾伦·图灵传：如谜的解谜者》，Simon & Schuster，1983年出版），我没费多大力气就总结出了图灵一生中的重要事件。霍奇斯对图灵感兴趣的部分原因，在于他参与了20世纪70年代的同性恋解放运动。霍奇斯的传记还给休·怀特摩尔的剧本Breaking the Code（《破解密码》，1986）带来了灵感，在舞台上和在1996年改编的电视片中，阿兰·图灵的角色都是由德里克·雅克比扮演的。

如同早期的英国数学家、计算机先驱查尔斯·巴贝奇（1791—1871）和艾达·拉夫拉斯（1815—1852），图灵也成为计算机时代的一个标志。美国计算机协会每年都会为在计算机行业做出杰出贡献的人颁发图灵奖，奖金为10万美元。现在还有一些用来组装图灵机的工具，比如“图灵编程语言”（从Pascal衍生而来）和“图灵的世界”软件。

图灵的名字几乎成为计算机编程的通用代名词。杜特尼把他的“计算机科学探索”一书命名为The Turing Omnibus（《图灵选集》，计算机科学出版社，1989）。戴维德·波尔特把他编写的一本关于“计算机时代的西方文化”的书命名为Turing's Man（《图灵时代的人类》，北卡罗来纳州大学出版社，1984）。布莱恩·罗特曼对传统数学极限概念的评论文章Ad Infinitum（斯坦福大学出版社，1993）被幽默地加上了副标题The Ghost in Turing's Machine（《图灵机里的幽灵》）。

数学和计算机科学领域以外的学者也对阿兰·图灵感兴趣。研究文集Novel Gazing: Queer Readings in Fiction（《凝神注视：论小说的另类解读》）中最有特色的一篇文章就是由泰勒·科坦撰写的The“Sinister Fruitiness”of Machines: Neuromancer, Internet Sexuality, and the Turing Test（《智能机器带来的“阴暗苦果”：神经漫游者、网络性爱和图灵测试》）。科坦博士所说的Neuromancer指的是威廉·吉布森著名的“赛博朋克”小说Neuromancer（《神经漫游者》）。在这部科幻小说里，有一个叫做图灵警察局的组织，他们负责确保人工智能体不会试图增强它们自身的智能。

图灵还出现在很多小说的书名中。马文·明斯基（麻省理工学院人工智能方向著名的研究者）与科幻小说家哈里·哈里森合写了The Turing Option（《图灵选择》，华纳图书公司，1992）。伯克利计算机科学教授克里斯托斯·帕帕迪米特里欧参与创作了Turing（《图灵》，一部关于计算的小说，麻省理工学院出版社，2003）。

玻利维亚小说家埃德蒙多·苏丹写了一本名为Turing's Delirium（《图灵的狂热》，英文版由丽莎·卡特翻译，霍顿·米夫林出版公司，2006）的小说，在其中，一个外号叫图灵的密码专家发现了用他的技能为腐败政府服务带来的危险。在珍娜·列文的小说A Madman Dreams of Turing Machines（《图灵机狂人梦》，Knopf出版社，2006）中，阿兰·图灵和库尔特·哥德尔的生活被虚构在了一起，他们穿越时空，产生了奇特的交织。

阿兰·图灵这个角色还出现在其他很多小说中，如尼尔·斯蒂芬森的Cryptonomicon（《编码宝典》，Avon，1999），罗伯特·哈里斯的Enigma（《密码迷情》，Hutchinson，1995），约翰·卡斯蒂的The Cambridge Quintet: A Work of Scientific Speculation（《剑桥五重奏：一部科学思考的著作》，Perseus图书公司，1998），以及道格拉斯·侯世达的Gödel, Escher, Bach⁷（Basic图书公司，1979）。阿兰·图灵甚至为The Turing Test（《图灵测试》，BBC， 2000）的一部分做了解说，这本书是保罗·伦纳德写的Doctor Who系列小说中的一本。

⁷ 中文版《哥德尔、埃舍尔、巴赫——集异璧之大成》由商务印书馆1996年8月出版。——译者注

人们以各种方式来表达对阿兰·图灵的尊敬当然是好事，不过这样一 来，图灵的实际研究可能会被遗忘。我希望，就算那些正式研究过计算理论，并认为自己完全了解图灵机的人，也能在面对这个真正由大师自己构建的图灵机时发现不少令人惊奇的事物。

*　*　*

我在1999年就开始构思这本书，当时只写了一点，然后在接下来的五年里时不时又写上一些。2004～2005年基本完成了前11章。后面7章是在2007～2008年完成的，在此期间的写作几乎未中断，唯一的中断就是与我一生中最好的朋友，也是我的至爱迪尔德丽·辛诺特结婚（终于结婚啦）！

非常感谢伦敦数学协会许可完整地再版阿兰·图灵的论文“On Computable Numbers, with an Application to the Entscheidungsproblem”。

沃尔特·威廉姆斯和拉里·史密斯审阅了本书的初稿，发现了一些错误，并且提出了一些很有益的改进建议。

非常感谢Wiley出版公司的同仁，正是他们的工作将我所钟爱的想法真正出版成书。克里斯· 韦伯负责督促这本书的出版，策划编辑克里斯多夫· 里韦拉和制作编辑安吉拉·史密斯克服了很多版式和印刷方面的困难，技术编辑彼得·伯凡蒂帮助我认真完成了技术相关的内容。Wiley出版公司的很多幕后工作人员也都努力把这本书做得至臻至善。所有未被发现而遗留在书中的缺陷、瑕疵或隐藏的错误，都只能归咎于作者。

每位作者都是站在前人肩上的。选出的参考书目只列出了我所参考的众多书籍中的一小部分。我还要感谢纽约公共图书馆，特别是科学、工业和商业图书馆的工作人员。为参考原始论文，我多次使用JSTOR，同时我发现维基百科、谷歌书籍搜索和Wolfram MathWorld也都很有用。

*　*　*

登录网站www.TheAnnotatedTuring.com可以找到与本书相关的信息和资源。

查里斯·佩措尔德

纽约州纽约市和罗斯科

2008年5月