大众对图灵的认识往往停留在二战时期破解密码拯救生命这个层面。对于图灵在学术上的成就却知之甚少。由克里斯·伯恩哈特著的《论可计算数(图灵与现代计算的诞生)(精)》深入分析图灵一生中最重要的论文《论可计算数及其在判定问题上的应用》，从科学的角度讲述图灵为什么重要，如果没有图灵，我们的世界将会怎样。

1936年，24岁的图灵发表了现代计算领域奠基性的论文《论可计算数及其在判定问题上的应用》。这篇论文堪称图灵一生中重要的贡献。然而，大众对图灵的了解多停留在破解德国的著名密码系统Enigma，帮助盟军取得二战的胜利上。对于数学家图灵，人们往往知之甚少。

在由克里斯·伯恩哈特著的《论可计算数(图灵与现代计算的诞生)(精)》中，作者深入分析了图灵的这篇论文，读者只需具备高中水平的数学知识，即可轻松读懂这篇划时代的论文，了解其对现代计算发展的杰出贡献。正如人工智能之父马文·明斯基所说，图灵的论文有着超乎寻常的简洁性及数学之美。任何希望深入了解图灵及其工作的读者都不该错过这本书！

前言

第一章 背景

 数学的确定性

 布尔逻辑

 数学逻辑

 逻辑机器

 保卫数学基础

 希尔伯特的方法

 哥德尔结论

 图灵的结论

第二章 一些不可判定的判定问题

 埃米尔·波斯特

 波斯特的对应问题

 一个算法

 含有更多符号的对应问题

 希尔伯特的第10个问题

 停机问题

 剑桥的图灵

第三章 有限自动机

 有限自动机

 我们的第一个机器

 字母表和语言

 有限自动机和回答问题

 问题的否定

 忽略图表中的陷阱

 一些基本事实

 正则表达式

 有限自动机的瓶颈

 同样数量的0和1

 平衡括号

 磁带和配置

 联系对应问题

第四章 图灵机

 有限自动机

 我们的第一个机器

 字母表和语言

 有限自动机和回答问题

 问题的否定

 忽略图表中的陷阱

 一些基本事实

 正则表达式

 有限自动机的瓶颈

 同样数量的0和1

 平衡括号

 磁带和配置

 联系对应问题

 图灵机的例子

 可计算函数和计算

 邱奇—图灵论题

 计算能力

 多项式时间

 非确定性图灵机

 不会停机的机器

第五章 其他计算系统

 λ积分

 皮亚诺算术

 λ积分和函数

 算术

 逻辑

 标签系统

 一维元胞自动机

第六章 编码和通用机器

 编码有限自动机的方法

 通用机器

 设计通用机器

 现代计算机是图灵机

 冯·诺依曼结构

 随机存取机器

 图灵机能够模拟RAM

 其他通用机器

 当我们把〈M〉输入M的时候会发生什么

第七章 不可判定的问题

 矛盾证明法

 罗素的理发师

 不接纳自己的编码的有限自动机

 不接纳自己的编码的图灵机

 “图灵机是否会在自己的编码上偏离”是不可判定的

 接纳、停机和空白磁带问题

 一个不可计算函数

 图灵的方法

第八章 康托尔的对角论证法

 基数

 有理数的子集拥有相同的基数

 希尔伯特旅馆

 定义不完善的减法

 一般对角论证

 康托尔定理

 实数的基数

 对角论证法

 连续统假设

 计算的基数

 可计算数

 一个非可计算数

 存在可数数量的可计算数

 可计算数无法有效枚举

第九章 图灵的遗产

 图灵在普林斯顿大学

 克劳德·香农

 第二次世界大战

 20世纪40年代的计算机发展

 克兰德·楚泽

 莫奇利和艾克特

 冯·诺依曼

 图灵测试

 陨落

 道歉和赦免

拓展阅读

注释

1935年，22岁的艾伦·图灵当选剑桥大学国王学院研究员。那时的他刚刚完成了数学专业的本科课程。年轻的图灵聪慧而又野心勃勃，读本科的时候就完成了中心极限定理（Central Limit Theorem）的证明。这个定理可能是统计学中最基础的定理，它说明了正态分布的普遍性并解释了其多样性。虽然图灵完成了证明，但他很快发现自己并不是第一个完成了这个任务的人。

早在10年之前，亚尔·瓦尔德马·林德伯格（Jarl Waldemar Lindeberg）就发表了对这一定理的证明。虽然图灵的证明并非首创，但却展现出了他过人的天分和非凡的潜力。这足以让他被剑桥选中，获得研究员的职位：这份工作为他赢得了奖金和三年食宿补助，他唯一要做的就是把精力投入数学研究之中。现在，图灵必须要证明自己。要想做到这一点，他得完成一些真正具有独创性的事情。还有什么比解决一个世界顶级数学家提出的猜想，并证明他是错误的更令人心动？这正是图灵想要做的，他将解决希尔伯特的判定问题。

在介绍图灵的工作之前，我们有必要了解希尔伯特提出这一问题的原因。这还要追溯到19世纪下半叶至20世纪上半叶数学领域的发展。我将用较多的笔墨介绍数学逻辑的兴起、人们为追求数学公理化所做的努力以及算法扮演的角色与作用。

数学的确定性

数学通常被视作“确定”的代名词。如果数学真理不是确定的，又有什么事情存在定数？纵观数学史，由于根基不牢靠而导致整个结构崩溃的案例并不少见。人类第一次感觉到数学的非确定性要追溯到公元前5世纪。据传，这种非确定性的发现也导致希帕索斯（Hippasus）因为自己证明的定理而惨遭谋杀。如今希帕索斯的证明原稿早已不知所踪，不过这段论证很可能也会归入最美丽的数学论证之列（我们将在稍后看到完整的证明）。

古希腊数字系统由两部分组成——完整数以及完整数的比率，也就是我们现在常说的整数和有理数。希帕索斯首先假定了一个底和高都是1的直角三角形，接下来他发现这个三角形的斜边长度并不是有理数。现在看来，这完全不是问题。因为除了有理数，我们还有像π、e这样的无理数。我们明白希帕索斯论证中的斜边长度，实际上就是这个无理数。然而对于古希腊人来说，这无疑是个大问题——他们的数字系统中只存在有理数。对他们来说，希帕索斯论证中那条斜边的长度无法由他们的数字表示，这也意味着还有更多的长度不是数字！

希帕索斯是毕达哥拉斯学派的成员，这个神秘的学派相信，数字能够表示所有事物的本质。由学派成员证明出数字无法表示所有长度，这无异于晴天霹雳，令人心神不安——这一论断直接撼动了他们最基础的信念。据说当希帕索斯将自己的证明展示给其他毕达哥拉斯派成员时，愤怒的同伴用沉重的链条缠住他的身体，将他溺毙在湖中央。这个故事的真实性难以考证，但无法测量的长度这一发现无疑引发了数学史上第一场地震般的剧变。

P3-5

序言

市面上的图灵传记不胜枚举。英国演员德里克·雅各比(Derek Jacobi)将他的形象带上舞台，本尼迪克特·康伯巴奇(Benedict Cumberbatch)又在电影中进行了重新演绎。艾伦·图灵即便算不上家喻户晓的名人，也算得上众所周知的人物。很多人都知道，他在第二次世界大战期间进行的密码破译工作对盟军最终战胜德军起到了关键作用。人们可能听说过，图灵的一生以氰化物中毒悲惨而终，也有人听说过他为判断“计算机是否可以思考”而设计的测试。或许并不那么有名的事实是计算机科学界的最高奖项叫图灵奖(A.M.TuringAward)。这一奖项被奉为计算界的诺贝尔奖。每年国际计算机协会(Association for Computing Machinery，简称ACM)都会向在计算机领域有杰出贡献的人颁发图灵奖，并送上100万美元的奖金。ACM以图灵的名字命名了这一奖项，是因为图灵被视作计算机科学的奠基人之一。他做了哪些帮助人类构建计算机科学的事情？答案就是1936年图灵发表的一篇引人注目的论文，那时他只有24岁。这篇论文是图灵最重要的知识贡献。然而论文本身以及蕴藏其中的开创性观点却并没有广泛流传。本书的内容就围绕这篇论文展开。

这篇论文的题目看起来有些无趣：论可计算数及其在判定问题上的应用(On Computable Numbers， with an Application to the Entscheidungsproblem)。不要因为这个题目而太过沮丧，论文中包含了很多优雅而强大的结论和出色美妙的论证。图灵希望通过自己的论文证明当时一位顶尖数学家的观点是错误的。为了实现这一目标，他需要研究计算：什么是计算？我们该如何定义它？是否存在无法用计算解决的问题？他用令人眼花缭乱的技巧、别出心裁的创意回答了这些问题。

图灵仔细思考了人们完成计算的方法。他意识到，任何计算都可以拆分成一系列简单的步骤。接下来，他制造了能够完成其中每一个步骤的理论机器。这些机器就是我们现在所说的图灵机，它们能够完成任何计算1。而在这之后，他指出我们并不需要为每种不同算法设计各自的专属机器，只需设计一个可以运行任意算法的机器。在这一过程中，他提出了存储程序(stored-program)的概念，我们将会看到这对现代计算机的发展是至关重要的。最后，他证明了有一些特定的问题超出了计算机的能力范畴。

这些图灵机是现代计算机的理论模型。计算机能够执行的所有任务都能够由图灵机进行计算。因此，他的论文不只具有历史价值，他告诉我们计算机能完成哪些任务，不能完成哪些任务。他告诉我们计算的限制乍看起来似乎直接明了，可想要做出正确回答，却超出了任何一台计算机的能力范畴。

这篇论文中包含的观点出现在很多大学的本科课程中，课程名称通常是计算理论(Theory of Computation)。由于大多数大学生没有选修这门课程，所以多数人并未接触过图灵的工作。总体来说，在全球庞大的人口数量中，只有很小一部分人知道图灵论文的内容。这篇论文不仅包含了很多非凡的想法，也与当代生活有着紧密联系，考虑到这些，不能不说这种陌生是一个遗憾。

广义相对论与量子力学都诞生于20世纪上半叶。对于这两大理论，大多数人脑海中都有些概念。这两大理论都建立在非常复杂的数学基础上，所以理解起来有一定的难度。不过，理解图灵的论文并没有这种压力。正如马文·明斯基(Marvin Minsky)所说：“这一理论的纯粹与简明赋予其数学的美感，这种美感确保其在计算机理论中拥有永恒的地位。”我们将从图灵理论的基础开始，逐步延伸到那些惊人的结论。同时，我们也会尽可能补充图灵研究的背景和相关信息。为此，我们将介绍一些图灵论文发表前后的历史。

对于计算，不同人可能有不同的见解，这些观点并无对错之分。不同观点背后的景色迥然不同。在本书中，我们会在必要的时候稍作停留，深入探讨其中的一些观点。特别是普林斯顿大学逻辑学家阿隆佐·邱奇(AlonzoChurch)的观点，它采用了一种完全不同的方式来探索计算。邱奇和图灵都曾为解答德国数学家戴维·希尔伯特(David Hilbert)提出的问题而努力研究。两人得出了一样的结论：希尔伯特做出的假设是错误的，不过邱奇先于图灵发表了自己的结论。

看到邱奇的论文时，图灵还在撰写自己的论文——知道有人已经抢先一步得出与自己一致的结论，当时图灵的心中势必满是苦涩与失望。

不过两人解决这一问题的方式却很不同，论证过程也因此大相径庭。图灵的论证要简明优雅得多。他的论文并非为了结论而发表，而是为了结论的证明过程而发表。

数学家经常会用“美丽”来形容一些出色的证明过程。在进行数学研究的时候，会有一种美学的指引。每当你做出证明却感觉过程稍显笨拙时，一定还有更好的论证有待开发。匈牙利数学家保罗·厄多斯(Paul Erdos)在谈及《圣经》时指出，上帝在一本书中写就了所有最简捷、最美妙的论证。厄多斯说过这样一句著名的话：“你不一定要信仰上帝，但是你应该信仰《圣经》。”据此来看，图灵的证明以及他参考的库尔特·哥德尔(Kurt Godel)和格奥尔格·康托尔(Georg Cantor)的理论，一定都能被收录在《圣经》中。

本书主要服务那些希望了解这些想法的读者。我们将从基础开始，徐徐展开整幅画卷。读者只需具备高中数学知识。本书需要认真阅读，有些章节、段落需要反复研读。因为图灵讲述的并不是计算领域一些无关紧要的细枝末节，而是一些深层次的、并不直观的内容。也就是说，很多人可能会觉得这些想法相当有趣，自己的付出也是值得的。

……

第九章

最后一章将介绍在图灵发表论文后的几年时间里，他本人和计算机发生了什么变化。

图灵来到普林斯顿大学，在邱奇的指导下拿到了自己的博士学位。他在这里结识了约翰·冯·诺依曼(John von Neumann)。随后，图灵返回英国，并在第二次世界大战期间研究密码破译。

讲述完这些故事后，我们会简要地介绍在这40年间，现代计算机是如何从无到有的。我们将看到从复杂计算器到通用计算机，再到存储程序的通用计算的发展历程。具体来说，我们会提及图灵论文中萌生出的存储程序概念。

1950年，图灵发表了一篇论文，描述现在所谓的图灵机。我们将会简要介绍图灵机及这个概念的后续发展。

本章结尾部分将谈及杰克·科普兰(Jack Copeland)对图灵之死的研究，以及事实真相——或许图灵之死源于事故，而非谋杀。

最后，我们会谈到戈登·布朗(Gordon Brown)代表英国政府发表的道歉文章。

图灵的《论可计算数及其在判定问题中的应用》堪称史诗级论文，拉开了计算机革命的序幕。在这本书中，伯恩哈特与我们分享了与这篇论文相关的许多细节，让我们以简洁、轻松的方式了解这篇伟大的论文。

——伊恩·斯图尔特，《改变世界的17个方程式》作者

对于那些不太了解图灵的读者来说，这本精彩纷呈的书是非常好的普及读物。

——斯科特·阿伦森，麻省理工学院电气工程和计算机科学学院教授

近年来，现代计算之父图灵已经成为文化领域的偶像。伯恩哈特这本清晰易懂的书解释了图灵的工作，说明了他的思想如何深刻影响了今天的计算机科学。

——诺索·亚诺夫斯基，《理性的外部界限》作者

如今智能手机和笔记本电脑的高速发展掩盖了现代计算先驱们的光芒。在这本书中，伯恩哈特揭示了图灵和其他早期计算机科学家做出的决定性贡献。这是一本了不起的书！

——A·K·杜德尼，西安大略大学计算机系名誉教授