克里斯·伯恩哈特，是美国费尔菲尔德大学数学系的一位教授，他从数学的角度入手，研究图灵的可计算数理论及现代计算的诞生，堪称图灵理论深入的研究者。

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

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

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

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

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

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

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

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

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

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

　　1935 年，22 岁的艾伦·图灵当选剑桥大学国王学院研 究员。那时的他刚刚完成了数学专业的本科课程。年轻的图 灵聪慧而又野心勃勃，读本科的时候就完成了中心极限定理

　　（Central Limit Theorem）的证明。这个定理可能是统计学中 最基础的定理，它说明了正态分布的普遍性并解释了其多样 性。虽然图灵完成了证明，但他很快发现自己并不是第一个完成了这个任务的人。

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

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

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

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

　　然而对于古希腊人来说，这无疑是个大问题——他们的数字 系统中只存在有理数。对他们来说，希帕索斯论证中那条斜 边的长度无法由他们的数字表示，这也意味着还有更多的长 度不是数字！

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

　　数字和长度都是基本的实体，你能够画出底和高都是 1 的直角三角形，意味着它的斜边是真实存在的。这条斜边 拥有自己的长度，但对于古希腊人来说这却非常怪异，因为 他们无法给这个长度分配一个数字。这类论证使古希腊人认 为，长度才是更基础的实体。这样看来，数字确实让人有些 不安——它缺少绝对的确定性。数字理论曾经被视作数学中 最基本、最确定的概念，在经历了这场风云突变后，几何学 很快取而代之。

　　从那以后直到现在，几何学都是数学教学重要的组成部 分。这主要归功于一个人和一本书——欧几里得（Euclid）及 其所著的《几何原本》（Elements）。《几何原本》是欧几里德 编撰的收录了已知数学知识的百科全书，也是一本教科书。 自 2 000 多年前写就以来，这些文字一直备受追捧，不断吸 引着研究者的目光，在拜占庭和阿拉伯数学家中广为流传。 1482  年《几何原本》首次印刷出版，并在之后不断再版。

　　欧几里德从一系列公理、假设入手 2，逐渐延展、推理出 更多新的结论。每一个新定理都能够通过公理以及之前的推 论得出。这种公理化的方法给人们带来了一种数学具有确定性的 印象。如果我们知道自己使用的最初级的公理是正确的，就 会知道自己的逻辑推理是有效的，这样也就能够肯定通过推 理得出的结论。然而问题在于我们很容易做出一些无根据的 假设——这些假设可能显而易见，甚至可能是正确的，但是却不能由最初的几条公理推导而出。当这些无根据的假设被 加入证明过程时，逻辑的有效性顷刻土崩瓦解，数学的必然 性也就此丧失。

　　在 19 世纪，有人意识到欧几里德做出的很多假设并非 基于自己的推导。因此，他的几何学著作需要重新修订。欧 几里德在证明过程中使用的一些无法从公理中推断出的陈述， 必须添加到他的公理列表之中。整个几何学的框架都需要重 新扩展、更新。

　　戴维·希尔伯特提出了新的挑战。1899 年，他发表了学 术著作《几何基础》（Grundlagen der Geometrie），在书中列 出了一个更新、更长也更完整的公理列表。希尔伯特十分审 慎，希望确保没有根据的假设不会混入证明过程。为了实现 这一目标，他对公理的定义与欧几里德的定义有着非常大的 差异。

　　在欧几里德看来，像“两点确定一条直线”这样的公理 是不证自明的。“点”和“线”都有自身的含义。希尔伯特 的方法却不同，他意识到任何公理和定义系统都应该始于某 个起点，这些最初的陈述中势必会包含此前从未被定义过的 术语。

　　对希尔伯特来说，公理是能够用来证明其他观点的陈 述，但公理并不能被视作不证自明的真理。欧几里德的公理 “两点确定一条直线”中包含了“点”和“线”这两个没有被定义过的概念，因此这两个字不应该具有任何意义。公理会 定义这些未定义概念之间的关系。正如希尔伯特指出的，由 于这些术语并没有任何意义，因此理论上你可以选用任何一个替换“点”和“线”。据说，他曾将公理中的“点”、 “线”、“面”等字眼，换作“桌子”、“椅子”、“几杯啤酒”。

　　伯特兰·罗素曾经颇为风趣地对此做出总结：“数学可 能就是这样一个学科，我们可能永远不知道自己在谈论什么， 或者无法判断自己说的是对还是错。”3 我们当然希望“点”、 “线”这样的术语指代的是我们平时谈论的点和线，但是希尔 伯特认为任何涉及这些术语的证明，都只应通过公理推导而 出，不该源于我们对这些文字的直观理解。

　　希尔伯特在几何学方面的成功自然而然地带来了一个问 题：公理化方法是否能够应用到整个数学学科？是否能够找 出一组公理，构建出数学学科的全部？包括希尔伯特和罗素 在内的一些数学家认为这种公理化方法是可行的。但是，在 讨论罗素、希尔伯特和其他人的研究前，我们还需要了解一 下数学逻辑的发展。

　　……

前 言 //  VII

第一章 背景

数学的确定性 //004

布尔逻辑//008

数学逻辑//010

逻辑机器//011

保卫数学基础//012

希尔伯特的方法//014

哥德尔结论//016

图灵的结论//016

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

埃米尔？波斯特  // 025

波斯特的对应问题  // 026

一个算法  // 030

含有更多符号的对应问题  // 032

希尔伯特的第 10 个问题 // 034

停机问题  // 036

剑桥的图灵  // 036

第三章 有限自动机

有限自动机 // 043

我们的第一个机器 // 044

字母表和语言 // 046

有限自动机和回答问题 // 049

问题的否定 // 051

忽略图表中的陷阱 // 052

一些基本事实 // 054

正则表达式 // 057

有限自动机的瓶颈 // 062

同样数量的0 和1 // 063

平衡括号 // 064

磁带和配置 // 065

联系对应问题 // 067

第四章 图灵机

有限自动机  // 043

我们的第一个机器  // 044

字母表和语言  // 046

有限自动机和回答问题  // 049

问题的否定  // 051

忽略图表中的陷阱  // 052

一些基本事实  // 054

正则表达式  // 057

有限自动机的瓶颈  // 062

同样数量的 0 和 1  // 063

平衡括号  // 064

磁带和配置  // 065

联系对应问题  // 067

图灵机的例子  // 079

可计算函数和计算  // 088

邱奇—图灵论题  // 090

计算能力  // 092

多项式时间  // 093

非确定性图灵机  // 095

不会停机的机器  // 097

第五章 其他计算系统

λ积分 // 106

皮亚诺算术 // 108

λ积分和函数 // 109

算术 // 110

逻辑 // 112

标签系统 // 114

一维元胞自动机 // 119

第六章 编码和通用机器

编码有限自动机的方法 // 129

通用机器 // 133

设计通用机器 // 136

现代计算机是图灵机 // 138

冯？诺依曼结构 // 140

随机存取机器 // 142

图灵机能够模拟RAM // 145

其他通用机器 // 147

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

第七章 不可判定的问题

矛盾证明法  // 155

罗素的理发师  // 158

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

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

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

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

一个不可计算函数  // 168

图灵的方法  // 170

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

基数  // 177

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

希尔伯特旅馆  // 182

定义不完善的减法  // 184

一般对角论证  // 184

康托尔定理 // 186

实数的基数 // 189

对角论证法 // 193

连续统假设 // 195

计算的基数 // 195

可计算数  // 197

一个非可计算数  // 198

存在可数数量的可计算数  // 199

可计算数无法有效枚举  // 200

第九章图灵的遗产

图灵在普林斯顿大学  // 206

克劳德？香农  // 208

第二次世界大战  // 209

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

克兰德？楚泽  // 214

莫奇利和艾克特  // 214

冯？诺依曼  // 215

图灵测试  // 218

陨落  // 221

道歉和赦免  // 223

拓展阅读 //  227

注 释 //  231