大众对图灵的认识往往停留在二战时期破解密码拯救生命这个层面。对于图灵在学术上的成就却知之甚少。本书深入分析图灵一生中*重要的论文《论可计算数及其在判定问题上的应用》，从科学的角度讲述图灵为什么重要，如果没有图灵，我们的世界将会怎样。
本书简介：
1936年，24岁的图灵发表了现代计算领域奠基性的论文《论可计算数及其在判定问题上的应用》。这篇论文堪称图灵一生中最重要的贡献。然而，大众对图灵的了解多停留在破解德国的著名密码系统Enigma，帮助盟军取得二战的胜利上。对于数学家图灵，人们往往知之甚少。 在本书中，作者深入分析了图灵的这篇论文，读者只需具备高中水平的数学知识，即可轻松读懂这篇划时代的论文，了解其对现代计算发展的杰出贡献。正如人工智能之父马文•明斯基所说，图灵的论文有着超乎寻常的简洁性及数学之美。任何希望深入了解图灵及其工作的读者都不该错过这本书！
作者简介：
克里斯•伯恩哈特是美国费尔菲尔德大学数学系的一位教授，他从数学的角度入手，研究图灵的可计算数理论及现代计算的诞生，堪称图灵理论最深入的研究者。
目录：
前言//VII
第一章背景
数学的确定性//004
布尔逻辑//008
数学逻辑//010
逻辑机器//011
保卫数学基础//012
希尔伯特的方法//014
哥德尔结论//016
图灵的结论//016
第二章一些不可判定的判定问题
埃米尔•波斯特//025前言// 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第二次世界大战 //20920世纪40年代的计算机发展//213克兰德•楚泽 //214莫奇利和艾克特 //214冯•诺依曼 //215图灵测试 //218陨落 //221道歉和赦免 //223拓展阅读// 227注释// 231前言序言市面上的图灵传记不胜枚举。英国演员德里克•雅各比（DerekJacobi）将他的形象带上舞台，本尼迪克特•康伯巴奇（BenedictCumberbatch）又在电影中进行了重新演绎。艾伦•图灵即便算不上家喻户晓的名人，也算得上众所周知的人物。很多人都知道，他在第二次世界大战期间进行的密码破译工作对盟军最终战胜德军起到了关键作用。人们可能听说过，图灵的一生以氰化物中毒悲惨而终，也有人听说过他为判断“计算机是否可以思考”而设计的测试。或许并不那么有名的事实是计算机科学界的最高奖项叫图灵奖（A.M.TuringAward）。这一奖项被奉为计算界的诺贝尔奖。每年国际计算机协会（AssociationforComputingMachinery，简称ACM）都会向在计算机领域有杰出贡献的人颁发图灵奖，并送上100万美元的奖金。ACM以图灵的名字命名了这一奖项，是因为图灵被视作计算机科学的奠基人之一。他做了哪些帮助人类构建计算机科学的事情？答案就是1936年图灵发表的一篇引人注目的论文，那时他只有24岁。这篇论文是图灵最重要的知识贡献。然而论文本身以及蕴藏其中的开创性观点却并没有广泛流传。本书的内容就围绕这篇论文展开。
这篇论文的题目看起来有些无趣：论可计算数及其在判定问题上的应用（On Computable Numbers, with an Application to theEntscheidungsproblem）。不要因为这个题目序言市面上的图灵传记不胜枚举。英国演员德里克•雅各比（DerekJacobi）将他的形象带上舞台，本尼迪克特•康伯巴奇（BenedictCumberbatch）又在电影中进行了重新演绎。艾伦•图灵即便算不上家喻户晓的名人，也算得上众所周知的人物。很多人都知道，他在第二次世界大战期间进行的密码破译工作对盟军最终战胜德军起到了关键作用。人们可能听说过，图灵的一生以氰化物中毒悲惨而终，也有人听说过他为判断“计算机是否可以思考”而设计的测试。或许并不那么有名的事实是计算机科学界的最高奖项叫图灵奖（A.M.TuringAward）。这一奖项被奉为计算界的诺贝尔奖。每年国际计算机协会（AssociationforComputingMachinery，简称ACM）都会向在计算机领域有杰出贡献的人颁发图灵奖，并送上100万美元的奖金。ACM以图灵的名字命名了这一奖项，是因为图灵被视作计算机科学的奠基人之一。他做了哪些帮助人类构建计算机科学的事情？答案就是1936年图灵发表的一篇引人注目的论文，那时他只有24岁。这篇论文是图灵最重要的知识贡献。然而论文本身以及蕴藏其中的开创性观点却并没有广泛流传。本书的内容就围绕这篇论文展开。这篇论文的题目看起来有些无趣：论可计算数及其在判定问题上的应用（OnComputableNumbers,withanApplicationtotheEntscheidungsproblem）。不要因为这个题目而太过沮丧，论文中包含了很多优雅而强大的结论和出色美妙的论证。图灵希望通过自己的论文证明当时一位顶尖数学家的观点是错误的。为了实现这一目标，他需要研究计算：什么是计算？我们该如何定义它？是否存在无法用计算解决的问题？他用令人眼花缭乱的技巧、别出心裁的创意回答了这些问题。图灵仔细思考了人们完成计算的方法。他意识到，任何计算都可以拆分成一系列简单的步骤。接下来，他制造了能够完成其中每一个步骤的理论机器。这些机器就是我们现在所说的图灵机，它们能够完成任何计算1。而在这之后，他指出我们并不需要为每种不同算法设计各自的专属机器，只需设计一个可以运行任意算法的机器。在这一过程中，他提出了存储程序（stored-program）的概念，我们将会看到这对现代计算机的发展是至关重要的。最后，他证明了有一些特定的问题超出了计算机的能力范畴。这些图灵机是现代计算机的理论模型。计算机能够执行的所有任务都能够由图灵机进行计算。因此，他的论文不只具有历史价值，他告诉我们计算机能完成哪些任务，不能完成哪些任务。他告诉我们计算的限制乍看起来似乎直接明了，可想要做出正确回答，却超出了任何一台计算机的能力范畴。这篇论文中包含的观点出现在很多大学的本科课程中，课程名称通常是计算理论（TheoryofComputation）。由于大多数大学生没有选修这门课程，所以多数人并未接触过图灵的工作。总体来说，在全球庞大的人口数量中，只有很小一部分人知道图灵论文的内容。这篇论文不仅包含了很多非凡的想法，也与当代生活有着紧密联系，考虑到这些，不能不说这种陌生是一个遗憾。广义相对论与量子力学都诞生于20世纪上半叶。对于这两大理论，大多数人脑海中都有些概念。这两大理论都建立在非常复杂的数学基础上，所以理解起来有一定的难度。不过，理解图灵的论文并没有这种压力。正如马文•明斯基（MarvinMinsky）所说：“这一理论的纯粹与简明赋予其数学的美感，这种美感确保其在计算机理论中拥有永恒的地位。”2我们将从图灵理论的基础开始，逐步延伸到那些惊人的结论。同时，我们也会尽可能补充图灵研究的背景和相关信息。为此，我们将介绍一些图灵论文发表前后的历史。对于计算，不同人可能有不同的见解，这些观点并无对错之分。不同观点背后的景色迥然不同。在本书中，我们会在必要的时候稍作停留，深入探讨其中的一些观点。特别是普林斯顿大学逻辑学家阿隆佐•邱奇（AlonzoChurch）的观点，它采用了一种完全不同的方式来探索计算。邱奇和图灵都曾为解答德国数学家戴维•希尔伯特（DavidHilbert）提出的问题而努力研究。两人得出了一样的结论：希尔伯特做出的假设是错误的，不过邱奇先于图灵发表了自己的结论。看到邱奇的论文时，图灵还在撰写自己的论文——知道有人已经抢先一步得出与自己一致的结论，当时图灵的心中势必满是苦涩与失望。不过两人解决这一问题的方式却很不同，论证过程也因此大相径庭。图灵的论证要简明优雅得多。他的论文并非为了结论而发表，而是为了结论的证明过程而发表。数学家经常会用“美丽”来形容一些出色的证明过程。在进行数学研究的时候，会有一种美学的指引。每当你做出证明却感觉过程稍显笨拙时，一定还有更好的论证有待开发。匈牙利数学家保罗•厄多斯（PaulErdõs）在谈及《圣经》时指出，上帝在一本书中写就了所有最简捷、最美妙的论证。厄多斯说过这样一句著名的话：“你不一定要信仰上帝，但是你应该信仰《圣经》。”据此来看，图灵的证明以及他参考的库尔特•哥德尔（KurtGödel）和格奥尔格•康托尔（GeorgCantor）的理论，一定都能被收录在《圣经》中。本书主要服务那些希望了解这些想法的读者。我们将从基础开始，徐徐展开整幅画卷。读者只需具备高中数学知识。本书需要认真阅读，有些章节、段落需要反复研读。因为图灵讲述的并不是计算领域一些无关紧要的细枝末节，而是一些深层次的、并不直观的内容。也就是说，很多人可能会觉得这些想法相当有趣，自己的付出也是值得的。图灵的《论可计算数及其在判定问题中的应用》堪称史诗级论文，拉开了计算机革命的序幕。在这本书中，伯恩哈特与我们分享了与这篇论文相关的许多细节，让我们以最简洁、最轻松的方式了解这篇伟大的论文。
——伊恩•斯图尔特，《改变世界的17个方程式》作者
对于那些不太了解图灵的读者来说，这本精彩纷呈的书是非常好的普及读物。
——斯科特•阿伦森，麻省理工学院电气工程和计算机科学学院教授
近年来，现代计算之父图灵已经成为文化领域的偶像。伯恩哈特这本清晰易懂的书解释了图灵的工作，说明了他的思想如何深刻影响了今天的计算机科学。
——诺索•亚诺夫斯基，《理性的外部界限》作者图灵的《论可计算数及其在判定问题中的应用》堪称史诗级论文，拉开了计算机革命的序幕。在这本书中，伯恩哈特与我们分享了与这篇论文相关的许多细节，让我们以最简洁、最轻松的方式了解这篇伟大的论文。——伊恩•斯图尔特，《改变世界的17个方程式》作者 对于那些不太了解图灵的读者来说，这本精彩纷呈的书是非常好的普及读物。——斯科特•阿伦森，麻省理工学院电气工程和计算机科学学院教授近年来，现代计算之父图灵已经成为文化领域的偶像。伯恩哈特这本清晰易懂的书解释了图灵的工作，说明了他的思想如何深刻影响了今天的计算机科学。——诺索•亚诺夫斯基，《理性的外部界限》作者如今智能手机和笔记本电脑的高速发展掩盖了现代计算先驱们的光芒。在这本书中，伯恩哈特揭示了图灵和其他早期计算机科学家做出的决定性贡献。这是一本了不起的书！ ——A•K•杜德尼，西安大略大学计算机系名誉教授1935年，22岁的艾伦•图灵当选剑桥大学国王学院研究员。那时的他刚刚完成了数学专业的本科课程。年轻的图灵聪慧而又野心勃勃，读本科的时候就完成了中心极限定理（CentralLimitTheorem）的证明。这个定理可能是统计学中最基础的定理，它说明了正态分布的普遍性并解释了其多样性。虽然图灵完成了证明，但他很快发现自己并不是第一个完成了这个任务的人。早在10年之前，亚尔•瓦尔德马•林德伯格（JarlWaldemarLindeberg）就发表了对这一定理的证明。虽然图灵的证明并非首创，但却展现出了他过人的天分和非凡的潜力。这足以让他被剑桥选中，获得研究员的职位：这份工作为他赢得了奖金和三年食宿补助，他唯一要做的就是把精力投入数学研究之中。现在，图灵必须要证明自己。要想做到这一点，他得完成一些真正具有独创性的事情。还有什么比解决一个世界顶级数学家提出的猜想，并证明他是错误的更令人心动？这正是图灵想要做的，他将解决希尔伯特的判定问题。在介绍图灵的工作之前，我们有必要了解希尔伯特提出这一问题的原因。这还要追溯到19世纪下半叶至20世纪上半叶数学领域的发展。我将用较多的笔墨介绍数学逻辑的兴起、人们为追求数学公理化所做的努力以及算法扮演的角色与作用。 数学通常被视作“确定”的代名词。如果数学真理不是确定的，又有什么事情存在定数？纵观数学史，由于根基不牢靠而导致整个结构崩溃的案例并不少见。人类第一次感觉到数学的非确定性要追溯到公元前5世纪。据传，这种非确定性的发现也导致希帕索斯（Hippasus）因为自己证明的定理而惨遭谋杀。如今希帕索斯的证明原稿早已不知所踪，不过这段论证很可能也会归入最美丽的数学论证之列（我们将在稍后看到完整的证明）。古希腊数字系统由两部分组成——完整数以及完整数的比率，也就是我们现在常说的整数和有理数。希帕索斯首先假定了一个底和高都是1的直角三角形，接下来他发现这个三角形的斜边长度并不是有理数。现在看来，这完全不是问题。因为除了有理数，我们还有像π、e这样的无理数。我们明白希帕索斯论证中的斜边长度，实际上就是这个无理数。然而对于古希腊人来说，这无疑是个大问题——他们的数字系统中只存在有理数。对他们来说，希帕索斯论证中那条斜边的长度无法由他们的数字表示，这也意味着还有更多的长度不是数字！希帕索斯是毕达哥拉斯学派的成员，这个神秘的学派相信，数字能够表示所有事物的本质。由学派成员证明出数字无法表示所有长度，这无异于晴天霹雳，令人心神不安——这一论断直接撼动了他们最基础的信念。据说当希帕索斯将自己的证明展示给其他毕达哥拉斯派成员时，愤怒的同伴用沉重的链条缠住他的身体，将他溺毙在湖中央。这个故事的真实性难以考证，但无法测量的长度这一发现无疑引发了数学史上第一场地震般的剧变。数字和长度都是基本的实体，你能够画出底和高都是1的直角三角形，意味着它的斜边是真实存在的。这条斜边拥有自己的长度，但对于古希腊人来说这却非常怪异，因为他们无法给这个长度分配一个数字。这类论证使古希腊人认为，长度才是更基础的实体。这样看来，数字确实让人有些不安——它缺少绝对的确定性。数字理论曾经被视作数学中最基本、最确定的概念，在经历了这场风云突变后，几何学很快取而代之。从那以后直到现在，几何学都是数学教学重要的组成部分。这主要归功于一个人和一本书——欧几里得（Euclid）及其所著的《几何原本》（Elements）。《几何原本》是欧几里德编撰的收录了已知数学知识的百科全书，也是一本教科书。自2000多年前写就以来，这些文字一直备受追捧，不断吸引着研究者的目光，在拜占庭和阿拉伯数学家中广为流传。1482 年《几何原本》首次印刷出版，并在之后不断再版。欧几里德从一系列公理、假设入手2，逐渐延展、推理出更多新的结论。每一个新定理都能够通过公理以及之前的推论得出。这种公理化的方法给人们带来了一种数学具有确定性的印象。如果我们知道自己使用的最初级的公理是正确的，就会知道自己的逻辑推理是有效的，这样也就能够肯定通过推理得出的结论。然而问题在于我们很容易做出一些无根据的假设——这些假设可能显而易见，甚至可能是正确的，但是却不能由最初的几条公理推导而出。当这些无根据的假设被加入证明过程时，逻辑的有效性顷刻土崩瓦解，数学的必然性也就此丧失。在19世纪，有人意识到欧几里德做出的很多假设并非基于自己的推导。因此，他的几何学著作需要重新修订。欧几里德在证明过程中使用的一些无法从公理中推断出的陈述，必须添加到他的公理列表之中。整个几何学的框架都需要重新扩展、更新。戴维•希尔伯特提出了新的挑战。1899年，他发表了学术著作《几何基础》（GrundlagenderGeometrie），在书中列出了一个更新、更长也更完整的公理列表。希尔伯特十分审慎，希望确保没有根据的假设不会混入证明过程。为了实现这一目标，他对公理的定义与欧几里德的定义有着非常大的差异。在欧几里德看来，像“两点确定一条直线”这样的公理是不证自明的。“点”和“线”都有自身的含义。希尔伯特的方法却不同，他意识到任何公理和定义系统都应该始于某个起点，这些最初的陈述中势必会包含此前从未被定义过的术语。对希尔伯特来说，公理是能够用来证明其他观点的陈述，但公理并不能被视作不证自明的真理。欧几里德的公理“两点确定一条直线”中包含了“点”和“线”这两个没有被定义过的概念，因此这两个字不应该具有任何意义。公理会定义这些未定义概念之间的关系。正如希尔伯特指出的，由于这些术语并没有任何意义，因此理论上你可以选用任何一个词来替换“点”和“线”。据说，他曾将公理中的“点”、“线”、“面”等字眼，换作“桌子”、“椅子”、“几杯啤酒”。伯特兰•罗素曾经颇为风趣地对此做出总结：“数学可能就是这样一个学科，我们可能永远不知道自己在谈论什么，或者无法判断自己说的是对还是错。”3我们当然希望“点”、“线”这样的术语指代的是我们平时谈论的点和线，但是希尔伯特认为任何涉及这些术语的证明，都只应通过公理推导而出，不该源于我们对这些文字的直观理解。希尔伯特在几何学方面的成功自然而然地带来了一个问题：公理化方法是否能够应用到整个数学学科？是否能够找出一组公理，构建出数学学科的全部？包括希尔伯特和罗素在内的一些数学家认为这种公理化方法是可行的。但是，在讨论罗素、希尔伯特和其他人的研究前，我们还需要了解一下数学逻辑的发展。
|
