作者：[美] 克里斯·伯恩哈特
出版社：中信出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
论可计算数：图灵与现代计算的诞生试读：
前言
市面上的图灵传记不胜枚举。英国演员德里克·雅各比（Derek Jacobi）将他的形象带上舞台，本尼迪克特·康伯巴奇（Benedict Cumberbatch）又在电影中进行了重新演绎。艾伦·图灵即便算不上家喻户晓的名人，也算得上众所周知的人物。很多人都知道，他在第二次世界大战期间进行的密码破译工作对盟军最终战胜德军起到了关键作用。人们可能听说过，图灵的一生以氰化物中毒悲惨而终，也有人听说过他为判断“计算机是否可以思考”而设计的测试。或许并不那么有名的事实是计算机科学界的最高奖项叫图灵奖（A. M. Turing Award）。这一奖项被奉为计算界的诺贝尔奖。每年国际计算机协会（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）所说：“这一理论的纯粹与简明赋予其数学的美感，这种美感确保其在计算机理论中拥有永恒的地位。”2
我们将从图灵理论的基础开始，逐步延伸到那些惊人的结论。同时，我们也会尽可能补充图灵研究的背景和相关信息。为此，我们将介绍一些图灵论文发表前后的历史。
对于计算，不同人可能有不同的见解，这些观点并无对错之分。不同观点背后的景色迥然不同。在本书中，我们会在必要的时候稍作停留，深入探讨其中的一些观点。特别是普林斯顿大学逻辑学家阿隆佐·邱奇（Alonzo Church）的观点，它采用了一种完全不同的方式来探索计算。邱奇和图灵都曾为解答德国数学家戴维·希尔伯特（David Hilbert）提出的问题而努力研究。两人得出了一样的结论：希尔伯特做出的假设是错误的，不过邱奇先于图灵发表了自己的结论。
看到邱奇的论文时，图灵还在撰写自己的论文——知道有人已经抢先一步得出与自己一致的结论，当时图灵的心中势必满是苦涩与失望。
不过两人解决这一问题的方式却很不同，论证过程也因此大相径庭。图灵的论证要简明优雅得多。他的论文并非为了结论而发表，而是为了结论的证明过程而发表。
数学家经常会用“美丽”来形容一些出色的证明过程。在进行数学研究的时候，会有一种美学的指引。每当你做出证明却感觉过程稍显笨拙时，一定还有更好的论证有待开发。匈牙利数学家保罗·厄多斯（Paul Erdõs）在谈及《圣经》时指出，上帝在一本书中写就了所有最简捷、最美妙的论证。厄多斯说过这样一句著名的话：“你不一定要信仰上帝，但是你应该信仰《圣经》。”据此来看，图灵的证明以及他参考的库尔特·哥德尔（Kurt Gödel）和格奥尔格·康托尔（Georg Cantor）的理论，一定都能被收录在《圣经》中。
本书主要服务那些希望了解这些想法的读者。我们将从基础开始，徐徐展开整幅画卷。读者只需具备高中数学知识。本书需要认真阅读，有些章节、段落需要反复研读。因为图灵讲述的并不是计算领域一些无关紧要的细枝末节，而是一些深层次的、并不直观的内容。也就是说，很多人可能会觉得这些想法相当有趣，自己的付出也是值得的。
以下是本书中一些重要观点的概述，依据它们在本书中的出现顺序排列。第一章
本章将关注19世纪下半叶至20世纪初的数学发展历史，介绍当时的数学基础如何摇摇欲坠，各类学者如何纷纷试图捍卫数学的基础。一位名叫戴维·希尔伯特的数学家在自己的研究项目中阐述了“判定问题”，即寻找算法来判定数学中的某些一般陈述正确与否。希尔伯特确信，这种算法一定存在。
这种观点导致了一个问题：执行一个计算，到底意味着什么？计算一直是数学的组成部分。实际上，几个世纪以来，数学和计算本质上是同义词，然而现在情况发生了转变。计算已经发展为一个独立的研究领域。图灵撰写论文的目的，就是证明希尔伯特关于计算能力的观点是错误的。第二章
图灵希望证明存在一些超出计算机解决能力的问题。具体来说，他想要找到一个能够被证明为不可判定的判定问题。本章的目标就是解释“判定问题”和“不可判定”的含义以及它们为何重要。
我们会讨论三个著名的判定问题，这三个问题已经被证明是不可判定的。我们还会分析不可判定在这些情况中有何意义。第三章
图灵用理论计算机器定义了计算。我们将以有限自动机为切入点研究自动机（即理论计算机器）。有限自动机比图灵机简单，并且易于描述和使用。我们会讨论有限自动机可以计算哪些问题，还会给出超越它们计算能力的例子并证明。此外，我们还会考虑如何将这些自动机执行的运算与波斯特的对应问题联系起来。
本章还会介绍正则表达式，证明它们与所说明的有限自动机的等价性。我们看到，拥有不止一种计算描述方法将十分有益。第四章
本章介绍了图灵机。图灵机看起来并不比有限自动机复杂很多，但却被证明更加强大。上一章中的超越有限自动机计算能力的问题，被证明可以使用这些新机器解决。
本章还介绍了邱奇—图灵论题，即任意可由图灵机实现的算法。我们还将看到，这些机器带来了一种新的重要现象。一些机器永远不会停止输入，会一直运行下去。第五章
除了图灵的方法，还有几种研究计算的不同方法。在本章，我们将讨论其中三种方法。首先是阿隆佐·邱奇的λ积分，接下来是标签系统，最后是元胞自动机。
这些计算观点看似截然不同，但每种观点都具有自身的优势。λ积分孕育了编程语言；标签系统在证明不同系统的等价性时非常有用；元胞自动机给出了计算全过程的图形表示。之后，我们将回归图灵的论证。第六章
在之前几章中，我们一直用图形描述机器。在本章，我们将展示如何使用有限数字序列描述有限自动机和图灵机，即编码（encodings）。这与将高级语言转换为机器语言类似。编码导致了通用图灵机（Universal Turing machines）概念的产生——一个能够输入程序和数据，并在数据上运行程序的机器。我们会看到，现代计算机是通用机器。第七章
上一章的最后一个话题讨论了在与机器描述对应的有限数字序列上运行机器，即在机器自己的编码上运行机器。这种自我引用概念相当重要。我们将详细分析并证明这个概念能够帮助我们证明某些问题是不可判定的。
本书并未假设读者具有相当强的数学知识。本章和下一章都会用到矛盾证明法。本章首先会解释这种证明方法——详细介绍“2不是有理数”的经典证明。随后，我们会介绍罗素的理发师悖论（Barber Paradox）。
介绍完这些概念后，我们将回归自动机的论证。我们证明了一些有限自动机可以接纳自己的编码，一些有限自动机则不能，但是不存在能够区分这两种情况的有限自动机。
之后，这种观点被拓展到图灵机：存在一些图灵机可以接纳自己的编码，一些图灵机则不可以，但是不存在能够区分这两种情况的图灵机。反过来，这个事实使我们可以证明某些判定问题是不可判定的。具体来说，我们证明了停机问题（Halting Problem）和接纳问题（Acceptance Problem）都是不可判定的。第八章
图灵的论文题目为“论可计算数及其在判定问题上的应用”。我们已经介绍了判定问题，但是并未介绍可计算数。本章，我们会讨论这些数字的含义以及与它们相关的基本结论。
本章首先会介绍康托尔的基数（cardinality）概念。我们会讨论一些基本的、令人惊讶的关于无限基数的事实，还会介绍用于证明两个集合拥有不同基数的康托尔对角论证法和一般论证法。然后，我们会再次回归图灵的论文。我们还会解释有效可枚举（effectively enumerable）的含义。最后，我们会解释图灵证明可计算数并不是有效可枚举的过程。第九章
最后一章将介绍在图灵发表论文后的几年时间里，他本人和计算机发生了什么变化。
图灵来到普林斯顿大学，在邱奇的指导下拿到了自己的博士学位。他在这里结识了约翰·冯·诺依曼（John von Neumann）。随后，图灵返回英国，并在第二次世界大战期间研究密码破译。
讲述完这些故事后，我们会简要地介绍在这40年间，现代计算机是如何从无到有的。我们将看到从复杂计算器到通用计算机，再到存储程序的通用计算的发展历程。具体来说，我们会提及图灵论文中萌生出的存储程序概念。
1950年，图灵发表了一篇论文，描述现在所谓的图灵机。我们将会简要介绍图灵机及这个概念的后续发展。
本章结尾部分将谈及杰克·科普兰（Jack Copeland）对图灵之死的研究，以及事实真相——或许图灵之死源于事故，而非谋杀。
最后，我们会谈到戈登·布朗（Gordon Brown）代表英国政府发表的道歉文章。第一章背景
正确地审视数学，你会发现它拥有的不仅是真理，更是一种至高无上的美丽，这是一种像雕刻作品般冷峻而朴素的美。数学之美并未沾染人类的气息，也没有绘画或音乐般华丽。它极度纯净，极致完美，这种完美只有最伟大的艺术才能展现。——伯特兰·罗素（Bertrand Russell）1
1935年，22岁的艾伦·图灵当选剑桥大学国王学院研究员。那时的他刚刚完成了数学专业的本科课程。年轻的图灵聪慧而又野心勃勃，读本科的时候就完成了中心极限定理（Central Limit Theorem）的证明。这个定理可能是统计学中最基础的定理，它说明了正态分布的普遍性并解释了其多样性。虽然图灵完成了证明，但他很快发现自己并不是第一个完成了这个任务的人。
早在10年之前，亚尔·瓦尔德马·林德伯格（Jarl Waldemar Lindeberg）就发表了对这一定理的证明。虽然图灵的证明并非首创，但却展现出了他过人的天分和非凡的潜力。这足以让他被剑桥选中，获得研究员的职位：这份工作为他赢得了奖金和三年食宿补助，他唯一要做的就是把精力投入数学研究之中。现在，图灵必须要证明自己。要想做到这一点，他得完成一些真正具有独创性的事情。还有什么比解决一个世界顶级数学家提出的猜想，并证明他是错误的更令人心动？这正是图灵想要做的，他将解决希尔伯特的判定问题。
在介绍图灵的工作之前，我们有必要了解希尔伯特提出这一问题的原因。这还要追溯到19世纪下半叶至20世纪上半叶数学领域的发展。我将用较多的笔墨介绍数学逻辑的兴起、人们为追求数学公理化所做的努力以及算法扮演的角色与作用。数学的确定性
数学通常被视作“确定”的代名词。如果数学真理不是确定的，又有什么事情存在定数？纵观数学史，由于根基不牢靠而导致整个结构崩溃的案例并不少见。人类第一次感觉到数学的非确定性要追溯到公元前5世纪。据传，这种非确定性的发现也导致希帕索斯（Hippasus）因为自己证明的定理而惨遭谋杀。如今希帕索斯的证明原稿早已不知所踪，不过这段论证很可能也会归入最美丽的数学论证之列（我们将在稍后看到完整的证明）。
古希腊数字系统由两部分组成——完整数以及完整数的比率，也就是我们现在常说的整数和有理数。希帕索斯首先假定了一个底和高都是1的直角三角形，接下来他发现这个三角形的斜边长度并不是有理数。现在看来，这完全不是问题。因为除了有理数，我们还有像π、e这样的无理数。我们明白希帕索斯论证中的斜边长度，实际上就是2这个无理数。然而对于古希腊人来说，这无疑是个大问题——他们的数字系统中只存在有理数。对他们来说，希帕索斯论证中那条斜边的长度无法由他们的数字表示，这也意味着还有更多的长度不是数字！
希帕索斯是毕达哥拉斯学派的成员，这个神秘的学派相信，数字能够表示所有事物的本质。由学派成员证明出数字无法表示所有长度，这无异于晴天霹雳，令人心神不安——这一论断直接撼动了他们最基础的信念。据说当希帕索斯将自己的证明展示给其他毕达哥拉斯派成员时，愤怒的同伴用沉重的链条缠住他的身体，将他溺毙在湖中央。这个故事的真实性难以考证，但无法测量的长度这一发现无疑引发了数学史上第一场地震般的剧变。
数字和长度都是基本的实体，你能够画出底和高都是1的直角三角形，意味着它的斜边是真实存在的。这条斜边拥有自己的长度，但对于古希腊人来说这却非常怪异，因为他们无法给这个长度分配一个数字。这类论证使古希腊人认为，长度才是更基础的实体。这样看来，数字确实让人有些不安——它缺少绝对的确定性。数字理论曾经被视作数学中最基本、最确定的概念，在经历了这场风云突变后，几何学很快取而代之。
从那以后直到现在，几何学都是数学教学重要的组成部分。这主要归功于一个人和一本书——欧几里得（Euclid）及其所著的《几何原本》（Elements）。《几何原本》是欧几里德编撰的收录了已知数学知识的百科全书，也是一本教科书。自2 000多年前写就以来，这些文字一直备受追捧，不断吸引着研究者的目光，在拜占庭和阿拉伯数学家中广为流传。1482年，《几何原本》首次印刷出版，并在之后不断再版。
欧几里德从一系列公理、假设入手2，逐渐延展、推理出更多新的结论。每一个新定理都能够通过公理以及之前的推论得出。
这种公理化的方法给人们带来了一种数学具有确定性的印象。如果我们知道自己使用的最初级的公理是正确的，就会知道自己的逻辑推理是有效的，这样也就能够肯定通过推理得出的结论。然而问题在于我们很容易做出一些无根据的假设——这些假设可能显而易见，甚至可能是正确的，但是却不能由最初的几条公理推导而出。当这些无根据的假设被加入证明过程时，逻辑的有效性顷刻土崩瓦解，数学的必然性也就此丧失。
在19世纪，有人意识到欧几里德做出的很多假设并非基于自己的推导。因此，他的几何学著作需要重新修订。欧几里德在证明过程中使用的一些无法从公理中推断出的陈述，必须添加到他的公理列表之中。整个几何学的框架都需要重新扩展、更新。
戴维·希尔伯特提出了新的挑战。1899年，他发表了学术著作《几何基础》（Grundlagen der Geometrie），在书中列出了一个更新、更长也更完整的公理列表。希尔伯特十分审慎，希望确保没有根据的假设不会混入证明过程。为了实现这一目标，他对公理的定义与欧几里德的定义有着非常大的差异。
在欧几里德看来，像“两点确定一条直线”这样的公理是不证自明的。“点”和“线”都有自身的含义。希尔伯特的方法却不同，他意识到任何公理和定义系统都应该始于某个起点，这些最初的陈述中势必会包含此前从未被定义过的术语。
对希尔伯特来说，公理是能够用来证明其他观点的陈述，但公理并不能被视作不证自明的真理。欧几里德的公理“两点确定一条直线”中包含了“点”和“线”这两个没有被定义过的概念，因此这两个字不应该具有任何意义。公理会定义这些未定义概念之间的关系。正如希尔伯特指出的，由于这些术语并没有任何意义，因此理论上你可以选用任何一个词来替换“点”和“线”。据说，他曾将公理中的“点”、“线”、“面”等字眼，换作“桌子”、“椅子”、“几杯啤酒”。
伯特兰·罗素曾经颇为风趣地对此做出总结：“数学可能就是这样一个学科，我们可能永远不知道自己在谈论什么，或者无法判断自己说的是对还是错。”3我们当然希望“点”、“线”这样的术语指代的是我们平时谈论的点和线，但是希尔伯特认为任何涉及这些术语的证明，都只应通过公理推导而出，不该源于我们对这些文字的直观理解。
希尔伯特在几何学方面的成功自然而然地带来了一个问题：公理化方法是否能够应用到整个数学学科？是否能够找出一组公理，构建出数学学科的全部？包括希尔伯特和罗素在内的一些数学家认为这种公理化方法是可行的。但是，在讨论罗素、希尔伯特和其他人的研究前，我们还需要了解一下数学逻辑的发展。布尔逻辑
逻辑一直是数学的组成部分。实际上，《几何原本》之所以如此有影响力（特别是在教育领域），欧几里得在写作时使用的方法功不可没。这本书不只是数学结论的罗列，更重要的是它向我们展示了如何从更简单的结论中得到这些结论。它不仅教你数学，还教你如何使用逻辑论证。为了真正受到教育，你必须熟悉这些论证。亚伯拉罕·林肯（Abraham Lincoln）曾经写道：“最后我说，林肯，如果你不理解证明意味着什么，你永远当不了律师；我放下自己在斯普林菲尔德的工作，回到父亲家，待在那里，直到我只看一眼就能给出欧几里得6本书中任意命题的证明。那之后，我发现了证明意味着什么，于是继续我的法律研究。”4
逻辑一直用于数学论证，19世纪时成为数学研究的一个独立领域。乔治·布尔（George Boole）最早提出了这个方法，意识到代数可以应用到逻辑中。使用“与”、“或”、“非”等连接符陈述的某些逻辑推论可以简化为对符号的代数运算。
1847年，布尔首次发表了自己的结论，他将这些结论继续雕琢，最终写入了自己的著作《思维规律的研究：构成逻辑和概率的数学原理》（An Investigation of the Laws of Thought: on Which are Founded the Mathematical Theories of Logic and Probabilities），直到1854年才发表。
其他数学家将布尔的结论发展壮大，形成了如今人们所知的布尔代数。这种代数对我们相当重要，因为它既是数学逻辑的开端，也是计算机设计的基础（在注释中，我们给出了一个使用布尔代数的例子，证明“今天是星期六或今天下雨了”不正确，等价于“今天不是星期六并且今天没下雨”是正确的5）。数学逻辑
布尔代数只能处理现在所谓的命题逻辑或零阶逻辑，并不包括“全部”或“部分”这类量词。像“一些正整数是质数”、“所有的整数都是有理数”这样的陈述，布尔代数无法处理。
下一步就是扩展布尔代数来包含量词并最终将数学所需逻辑完全转换为代数形式，即所有逻辑论证都可以用符号化操作表示。美国的查尔斯·桑德斯·皮尔士（Charles Sanders Peirce）和德国的戈特洛布·弗雷格（Gottlob Frege）分别独立完成了这项工作。弗雷格首先发表了关于量词的结论，但是皮尔士的研究对数学逻辑的后续发展起到了更为重要的作用。部分原因是皮尔士采用了更高级的标记，主要原因则是另一位德国数学家恩斯特·施罗德（Ernst Schröder）的研究，他撰写了一本关于数学逻辑的教科书，这本书影响深远，解释并拓展了布尔和皮尔士的研究。6
一旦证明逻辑具备数学结构，就会导致一个问题：是否可以制造机器来进行逻辑计算？在继续对数学基础的讨论前，我们将谈一些题外话，介绍一些制造机器的人。逻辑机器
英国经济学家、逻辑学家威廉·斯坦利·杰文斯（William Stanley Jevons）是最早意识到机器可以处理布尔逻辑的学者之一。他设计出逻辑钢琴（Logic Piano）来计算小真值表。逻辑钢琴像钢琴一样有键盘，用于输入初始假设。它于1869年制成，1870年在英国皇家学会展览。7逻辑钢琴并不是很实用，因为它只能处理容易由人工完成的简单问题，但是它却证明了机器可以处理逻辑。
1882年，皮尔士的学生艾伦·马昆德（Allan Marquand）在普林斯顿大学教授逻辑和拉丁语时，设计了自己的逻辑机器。这台机器类似杰文斯的机器，能够完成的任务相当有限。皮尔士致信马昆德，建议使用电机机械制造更高级的机器。但是，当时的普林斯顿大学校长认为皮尔士研究逻辑的数学方法是“异教徒的、非加尔文主义的”，因此马昆德应该停止教授逻辑，改为教授艺术史。马昆德成为一位成功的艺术史专家，但是他在逻辑学方面的研究就此止步。
大约在同一时期，皮尔士迎娶了自己的第二任妻子，人们发现皮尔士夫妇在婚前已经开始同居。绯闻终结了他的学术生涯。他被约翰·霍普金斯大学解聘，没有大学愿意雇用他。对于一个被罗素誉为“19世纪晚期最具独创性思想，当之无愧的最伟大的美国思想家”的学者而言，这不能不说是一个悲惨的结局。保卫数学基础
弗雷格的研究引起了罗素的兴趣。罗素对弗雷格如何发展逻辑并不在意，而是对他将逻辑与数学联系在一起的观点感兴趣。弗雷格是“逻辑主义”（逻辑构成了数学的基础）这个概念的发起人之一。根据这个概念，人们首先发展出了逻辑，随后由逻辑构建了数学。一切都是根据准确规则建立的。弗雷格投入多年时间发展这个理论，但不幸的是，在即将发表第二卷研究的内容前——他在里面详细阐释了这个理论，他接到一封来自罗素的信，信中指出这个理论存在一个基本缺陷。弗雷格从集合出发，发展了自己的理论，他将集合视作聚集。他并未意识到，这种看似简单的想法可能会导致问题。
罗素认为，集合应该被更认真地定义。弗雷格的构想让我们能够考虑所有可能集合的集合——最大可能集合，这产生了悖论。罗素联系弗雷格，解释了这个问题。弗雷格匆忙为自己的作品增加了附录：“书稿完成后，自己研究的一个基础被动摇，或许很难有比这更不幸的事情降临在一个科学作者身上。这就是我在收到伯兰特·罗素先生的信后面临的问题，当时这一卷的印刷工作即将完成。”但是，尽管罗素实际上驳倒了弗雷格的研究，他依旧认为弗雷格的方法是正确的。弗雷格的研究可以重新来做。
这是他在自己最重要的数学研究——与阿尔弗雷德·诺斯·怀特海（Alfred North Whitehead）合著的《数学原理》（Principia Mathematica）中所做的事情。与弗雷格的方法一样，他们以逻辑为起点，从逻辑来到了算术。但是，进展相当缓慢。在完成三卷著作后（分别于1910年、1912年和1913年发表），他们只研究到实数。为了确保没有涉及无根据的假设，直到第362页（第一卷的中段）才有这样的陈述：“从这个命题开始，直到算术加法被定义，才有1 + 1 = 2。”这一卷并未定义算术加法，它出现在第二卷。
读者也惊讶于这项研究的时间跨度。他们已经撰写了三卷，并且远未接近终点。下一卷或许会关于几何学，但是罗素和怀特海看到了巨大的工程量，决定放弃这个项目。
这是一项洋洋洒洒近2 000页的研究。有些页只有符号，但也附上了翔实的描述来介绍使用这些符号在做什么及原因——罗素是一位杰出的作者。尽管这个项目并未完成，已经出版的研究成果仍然影响深远，且影响范围不局限于数学界。它清晰的文字表达吸引了更加广泛的读者。T·S·艾略特（T. S. Eliot）对这一著作颇为赞赏，评论道：“逻辑学家必须利用好英语，使这种语言令读者容易准确清晰地思考。或许，《数学原理》对语言的贡献要超过它对数学的贡献。”8希尔伯特的方法
除了数学逻辑，19世纪还见证了非欧几何的诞生。除了关于平行线的公理，其他几何结构都是使用欧几里得几何构建的。不同公理在这些几何结构中得到证明，这些几何结构与对应的欧几里得几何结构大不相同。有人对这些公理系统最终会导致悖论持怀疑态度。给定一组连续的公理，我们能否确定无法证明一个陈述正确与否？非欧几何公理是否会导致悖论？我们能否确定欧几里得几何不包含矛盾？为了尝试回答类似的问题，数学中一个领域的模型需要在另一个领域中得出。
希尔伯特证明，如果算术是连续的，那么欧几里得几何也是连续的。有学者证明，如果欧几里得几何是连续的，那么非欧几何也是连续的。这些相关的连续性证明令人欣慰，但是人们意识到，连续性证明不应假设另一个领域是连续的。我们需要从一个能够被证明为连续的领域开始。因此，希尔伯特列出了他认为数学的公理基础应该具备的基本性质。
第一个性质是公理应该是连续的。公理不应该导致悖论——没有论述可以被证明是既对又错的。除此以外，应该能够证明这些公理是连续的。证明不应该涉及无法通过这些公理证明的概念。它应该能够由这些公理证明得到——从系统内得到。
第二个性质是公理应该是完整的。数学中的每个论述应该能够通过公理证明或反证。“数学应该建立在一个完整、连续的公理系统上，并且在系统内进行一致性证明”的想法，就是后来所谓的希尔伯特计划（Hilbert’s Program）。1920年，希尔伯特提出了最初的计划。1928年，他增加了判定问题。他认为应该存在一个决策程序，能够告诉我们一个论述能否通过这些公理证明。希尔伯特所指的决策程序是一种清晰的计算过程，也就是我们现在所说的算法。9他认为，向这个过程输入公理和可能结论，它应该告诉我们这个可能结论是否可以通过这些公理证明。希尔伯特确信，这样的算法一定存在。判定问题就是寻找算法的问题。
尽管希尔伯特喜欢用这种有序、机械的方法研究数学，其他人并不是这样。英国数学家G·H·哈代（G. H. Hardy）确信希尔伯特是错误的。1928年，他在谈到判定问题时指出：“当然不存在这样的公理，我们应该感到庆幸，因为如果我们找到了一套机械的规则，为所有数学问题提供解决方案，那么数学家的活动就将结束。”10
希尔伯特并不赞同哈代的意见。他坚信这种算法是存在的，坚信数学中的所有问题都可以被解决，坚信在所有情况下都存在能够给出解决方案的算法。他曾经这样说道：“我们必须知晓。我们将会知晓。”他辞世后，这两句话成为他的墓志铭。他确信这个计划可以构建一个安全的框架，数学的所有方面都可以建立在这个框架下。
然而，事与愿违。在他去世之前，他的计划就被证明是无法达成的。首先有了哥德尔的结论，随后是邱奇和图灵的结论。哥德尔结论
1931年，奥地利逻辑学家库尔特·哥德尔发表了一篇题为“论《数学原理》及相关体系中的形式上不可判定命题”（On Formally Undecidable Propositions of“Principia Mathematica” and Related Systems）的论文。在这篇论文中，他讨论了公理系统，这些系统足够强大，可以证明关于数字的结论——罗素和怀特海的《数学原理》就是这种系统的雏形。哥德尔证明了如果这些公理是连续的，那么它们就不是完整的。存在这些公理无法证明或反证的论述。他同样证明了无法在这个系统内证明公理的连续性。
哥德尔彻底摧毁了希尔伯特在1920年创立的项目。但是，判定问题仍然悬而未决。图灵的结论
在同一时期，图灵开始了在剑桥的研究生涯。1935年春天，他参加了马克斯·纽曼（Max Newman）的数学基础课程。在课堂上，纽曼对哥德尔的结论进行了解释，图灵也了解到了判定问题。他下定决心证明希尔伯特是错误的。希尔伯特渴望构建通用算法。他的命题中内嵌了隐性的假设——这种算法是真正存在的，而图灵的计划则是证明这一假设本身就是伪命题。他罗列了一些远远超出算法能力范畴的问题。他做出的证明也支持了哈代的观点——没有哪些规则能够给全部的数学问题带来解决方案，因此数学家的研究是永远不会结束的。
希尔伯特并没有正式定义过所谓的决策过程。因为在他看来这可能并无必要。纵观历史，人们脑海中的数学等同于计算——数学这一术语也出现在天文学和占星学中，用于计算恒星、行星的位置。11到19世纪，论证过程基本仍存在于计算范畴。大多数数学家或参与到算法开发研究中，或使用明确的算法——对算法的使用是做数学这门学问必不可少的部分。然而，像希尔伯特的判定问题这样的难题却让一些数学家和逻辑学家不禁要问：计算究竟是什么？算法的定义又是什么？
如果图灵想要证明某些特定的算法并不存在，那么他就必须回答这些问题。包括逻辑学家哥德尔、阿隆佐·邱奇在内的大师们都给出了自己的答案，但是图灵的解答却别具一格，他选择用设计理论计算机器的方式定义算法。稍后我们将看到各种完成计算的方式，但我认为，图灵采用的方法是最优雅、最简洁的。
在定义基本术语后，图灵论证过程的第二步是把自己的理论机器转化成一串串数字。也就是将一些由高级编程语言编写的程序转化成一系列二进制数字串、机器代码，让真正的计算机能够处理。
众所周知，今天的计算机使用二进制字符串，我们通过普通的语言与它们交互。很显然，肯定存在某种方式能够将我们的指令转化为二进制数字。但是在20世纪30年代，把指令转化成二进制数字的想法却是绝对的天方夜谭。要知道在这一时期，“Computer”所指的还是那些进行计算任务的人，人类计算人员收到的指令想必也都是一些日常所用的英语，而绝非一串0、1码。
当图灵定义好这些由一串串数字构成的算法后，就可以描述通用计算机。这种计算机能够将算法、数据作为输入，然后将数据套用到算法上。这是一个非常重要的理念。通用图灵机可以模拟任何一台图灵机。因此，通用图灵机能够完成其他图灵机能够完成的全部任务——运行所有的算法。
所有的现代计算机都是存储程序式计算机——数据和程序以完全相同的方式得到处理。这一想法实际上也源自图灵。当我们追随图灵的论证逐步深入时，我们就是在做计算，我们也就是计算机。在某一时刻，我们会突然意识到该如何将一串数字分解成两部分：一部分是算法，另一部分是将由算法处理的数据。实际上，从我们能够听从别人的指令完成任务开始，我们就已经变成了通用计算“机”。我们发现人类不仅是通用计算机，人类的计算能力能够媲美现有甚至未来可能出现的最强大的超级计算机器。
通用计算机显然非常重要，但是图灵将更多的注意力放到了将算法编码成数字串的过程中。他希望证明一些看起来并不难处理的问题，实际上完全超出了任何一台计算机的能力范畴。为了证明这一点，图灵借鉴了哥德尔的论断，后者则是从康托尔的对角论证法中获得启发。
图灵用来反驳那个著名的判定问题的方法是一段绝美的论证，有着很多环环相套的想法。我们将仔细研读这些论证，理解其中的每一个步骤。
我们将站在两个不同的角度评价图灵的这篇论文。一方面，这是一篇关于数学逻辑基础的论文，成功证明了判定问题的根本缺陷，从而终结希尔伯特计划。另一方面，正是这篇论文按下了计算理论以及计算机科学研究的启动键。这是一个旧时代的终结，也是一个新时代的开始。第一种审视方式着重强调了逻辑，第二种方式则强调了程序运行。在撰写这篇论文的时候，图灵显然采用了第一种方式，当这些理论被搬上讲台时，将它们与当今的计算机联系起来就更有意义，因此我们也倾向于以第二种方式看待这篇论文。
虽然我反复强调图灵论文如何优雅，但实际上这仍然是一篇相当难阅读的论文。学生们看到的往往是图灵想法的当代简化版。1958年，马丁·戴维斯（Martin Davis）根据自己在伊利诺伊大学教授的课程出版了《可计算性与不可解性》（Computability and Unsolvability）一书。1967年，麻省理工学院人工智能实验室联合创始人马文·明斯基根据当时在麻省理工学院教授的一门课程，出版了《计算：有限和无限机器》（Computation:Finite and Infinite Machines）一书。这两本书有着极大的影响力，它们以一种更简单易懂的方式呈现了图灵的想法，它们让计算理论的研究成为计算机科学的一部分，也让计算机科学发展成了一个独立的学科。很多现代的方法都与这两位计算机科学家有关。例如，在解释图灵的判定问题之前，通常都会介绍更易理解的停机问题，而这一问题最早出现在戴维斯的书中。在本书中，我们也将以这种现代的方式解析图灵的著作。
新的理解方式并没有改变图灵的基本思路，只是着眼点不同。比起计算机能够计算怎样的数字，我们这些生活在现代的人可能对计算机能够运行怎样的程序更感兴趣。我们希望提出问题，看看是否有算法或者程序能够解答这些问题。图灵对判定问题的证明也带来了一个问题：一些特定的判定问题是不可判定的。
非确定性是图灵论文中的主要观点，也是研究他的想法的一个绝佳的着眼点。在下一章中，我们将看到一些不可判定的判定问题的例子，更清楚地了解这一术语的真正含义。第二章一些不可判定的判定问题
在本章中，我们将探讨三个不可判定的判定问题，每个问题都有相当的知名度。第一个问题是希尔伯特的“第10个问题”，第二个问题是波斯特的对应问题，第三个是停机问题。我们先准确描述一下什么样的问题才能成为判定问题。
我们将从一个简单的例子开始。考虑一下这个问题：给定两个正整数x和y，x2 + y2是一个正整数的平方吗？这个问题的答案取决于x和y的取值。如果我们选择x = 3，y = 4，那么x2 + y2 = 9 + 16 = 25，是5的平方。在这种情况下，这个问题的答案是“是的”。如果我们输入x = 1，y = 1，那么2x + y2 = 2，我们知道2不是某个整数的平方。所以在这种情况下，答案是“不是”。给定输入参数的特定值，问题就有明确的答案。这就是判定问题的本质，即“是否为判定问题”取决于输入参数。一旦输入参数确定，它就变成一个是非问题。
如果能够设计一个算法或计算机程序，在所有情况下都能给出正确的答案，那么这个问题是可判定的。如果无法设计一个在所有情况下都能给出正确答案的算法，那么这个问题是不可判定的。
我们上面提到的“x2 + y2是否是某个整数的平方”是一个可判定问题。我们很容易就可以写出一个程序，输入x和y，让它告诉我们，x2 + y2是不是一个整数的平方。
证明一个判定问题是不可判定的，这个过程通常十分困难。只埋头研究不足以设计出能够回答这个问题的算法。为了证明一个问题是不可判定的，你必须证明不存在能够解决这个问题的算法。证明某个东西不存在通常要比证明某个东西存在困难。证明某个东西存在的直接方法是找到一个你需要的具体实例，但是这离证明“不存在”还有十万八千里。为了证明某个东西不存在，你必须证明不可能找到这样的实例。
在下文中，我们将描述已知的不可判定的问题。我们将详细描述并讨论为什么它们是不可判定的。在后面的章节中，我们将深入研究蕴含在不可判定性证明之中的思想。
首先，让我们来看看波斯特的对应问题。在此之前，我们先介绍一下这位理论计算界的巨擘。埃米尔·波斯特
1920年，埃米尔·波斯特（Emil Post）从哥伦比亚大学毕业，拿到了自己的博士学位。在博士论文中，他研究了罗素和怀特海的《数学原理》，证明了奠定零阶逻辑的公理——命题演算同时具备一致性和完整性。毕业后，波斯特来到普林斯顿大学，进行了为期一年的博士后研究。他的目标是研究《数学原理》中涉及的全部公理，并证明这些公理的一致性和完整性。
在研究过程中，波斯特采用了一种自创方法——标签系统（我们将在后面介绍这种方法）。他证明了《数学原理》中的公理在理论上可以简化为一种更简单的形式，类似于他的标签系统。他意识到，对《数学原理》中的公理的证明过程可以简化为对符号字符串进行的简单操作。
他的研究具有高度的原创性和突破性。他发现了构成哥德尔的不完备性定理和判定问题反证基础的主要概念。1921年时波斯特就在研究这一领域的问题。哥德尔在1931年发表了自己的研究成果，邱奇和图灵在1936年发表了他们的研究成果。因此，波斯特领先他们10年。不幸的是，当时他并未发表任何研究成果。波斯特患有双相情感障碍，1921年，他第一次发病。在此后的生命中，他必须定期住院，接受电击治疗——这是当时的标准疗法。1在第一次住院治疗后，他与医生一起研究病情，探讨自己能否免受未来狂躁情绪的影响。
他限制了自己研究的工作量，每天准备两个问题。如果一个问题让他太过兴奋，还可以研究另一个。他的妻子和家庭给了他莫大的支持。但是即便如此，直到1930年他还是没有发表任何论述。
1935年，波斯特入职纽约城市学院，并在这里一直工作到离世。在这段时间中，他的早期工作变得家喻户晓，他也继续保持高产和原创。芝加哥大学数学家罗伯特·索尔（Robert Soare）写道：“1939年，图灵提出纯计算性理论的主题。波斯特继续了之前的传统，用简单、直观的方式探索最基本的概念，比如计算性和可计算枚举集合，以及相关计算性和图灵可归约性。从1940年到1954年波斯特辞世，15年来他在这一领域的贡献可谓举足轻重。”
1946年，波斯特发表了他的对应性问题。这是一类非常容易描述的不可判定问题，我们将以此为切入点。波斯特的对应问题
想象一个目录列出了很多种“瓷砖”。目录中的每块瓷砖都包含两个由1和2组成的序列，其中一个序列在另一个序列下面。你可以随意订购任意数量的各种瓷砖。最终目标是找出一种瓷砖组合——当这些瓷砖排成一排的时候，顶部所有数字组成的序列与底部所有数字组成的序列相等。为了说明这个问题，我们来看两个例子。第一个目录
第一个目录有如下三种类型的瓷砖（如图2–1所示）。图2–1 第一个目录的三种瓷砖
我们可以任意选择各种类型的瓷砖，不限数量（包括0，但是至少要选择一种类型的瓷砖）。我们将这些瓷砖排成一排，以检查顶部序列是否等于底部序列。
在这种情况下，选择4块瓷砖就可以解决这个问题：一块A、一块C和两块B，并且按照BABC的顺序来摆放（如图2–2所示）。图2–2 第一个目录的4块瓷砖
按照这个顺序，我们得到了1121211121这个序列，而且顶部和底部的序列一致。所以，我们找出了这个目录的解决方案。
现在，我们来看一下另一个没有解决方案的目录。第二个目录
还是有三种类型的瓷砖（如图2–3所示）。图2–3 第二个目录的三种瓷砖
我们要尝试设计一个算法，认真执行所有可能的步骤。我们将从最左侧的瓷砖开始，向右依次增加瓷砖。
很明显，我们不能将瓷砖D放在最左侧，因为如果我们这样做，顶部的字符串会以1开始，而底部的字符串会以2开始。
如果将E作为第一块瓷砖，让我们来看看会发生什么。在这种情况下，顶部字符串以112开始，底部字符串以11开始。为了找到解决方案，我们需要一个底部以2开始的瓷砖。因此，下一步我们必须选D。来看ED，我们将在顶部得到112122，底部得到11212。我们需要一块底部字符串以2开始的瓷砖作为下一块瓷砖。因此我们必须继续选择D，这样我们就得到了EDD。顶部字符串为112122122，底部字符串为11212212。我们还需要一块底部字符串以2开始的瓷砖。另一个D被添加到右侧——这个过程会一直重复下去。在每个阶段，我们都必须向右侧增加D，但是我们永远找不到解决方案，因为顶部字符串总比底部字符串长一点。这告诉我们，不存在以E开始的解决方案。
我们已经看到，不存在以D或E开始的解决方案。唯一的可能性是以F开始。在这种情况下，顶部的字符串以1开始，底部的字符串以121开始。为了找到解决方案，我们需要一块顶部字符串以2开始的瓷砖。很不幸，不存在这样的瓷砖。因此，没有以F开始的解决方案。我们已经考虑了所有可能性，所以我们知道这种目录不存在解决方案。
给定任意瓷砖目录，有两种可能性：要么存在一种解决方案，要么不存在解决方案。给定一个目录，我们希望找到一个过程，告诉我们这个问题是否存在解决方案。波斯特证明了这种判定问题是不可判定的。这意味着不存在算法或等价的计算机程序，可以将这些瓷砖目录作为输入，告诉我们每个目录是否存在解决方案。这是一个令人震惊的结论！需要明确的是，这并不是说没有人发现能够奏效的算法，而是不存在这样的算法。
我们将深入挖掘这一点，并通过设计一个“看似能够奏效”的算法来研究它的影响。一个算法
这里有一个算法，我们称其为算法I：给定含有有限瓷砖数的任意目录，首先查看是否存在一块瓷砖是对应问题的解决方案。如果存在，我们就不用再做其他工作，并且得到了解决方案；如果没有一块瓷砖能够解决这个问题，尝试使用两块瓷砖可能的解决方案。如果有解决方案，我们将找到它。如果没有两块瓷砖的解决方案，尝试所有可能的三块瓷砖的组合，以此类推。
如果我们在第一个目录上尝试这个算法，我们首先会看A、B或C是否能够给出解决方案。因为没有一块瓷砖能够给出解决方案，我们会检查AA、AB、AC、BA、BB、BC、CA、CB或CC是否能够给出解决方案。因为没有解决方案，我们将查看三块瓷砖的组合（这里有33 = 27种可能）。再次没有解决方案后，我们来看4块瓷砖的组合，这里有34种可能组合。我们会在这次迭代中找到解决方案。
很明显，我们的算法不够高效，运行起来相当缓慢。举个例子，如果A不是解决方案，那么AA或AAA也不会是解决方案；如果能够排除这些组合，就可以提高运算速度。但是，我们的目标是给出一个容易描述的简单算法，效率或运行速度并不是我们关心的问题。我们唯一的兴趣在于这个算法如何实现，是否能够在有限时间内停止。
尽管很消耗时间，如果解决方案存在，算法I最终能够找出它。因此，算法I能够在所有存在解决方案的对应问题中奏效。如果我们给出的目录不存在解决方案，算法I不会奏效——它会一直运转下去。
是否存在一个不同的算法，能够告诉我们某个目录不存在解决方案？答案是没有。如果存在这样一个算法，我们称之为算法II，我们可以设计算法III，给定一个目录，让算法I和算法II同时运行。如果目录存在一个对应问题的解决方案，那么在有限时间后，算法I将告诉我们。如果目录不存在解决方案，那么算法II将在有限时间后告诉我们。这意味着算法III是一个“能够告诉我们目录是否存在解决方案”的算法，但是波斯特的结论证明并不存在这样的算法。因此算法II并不存在。
我们有必要深入挖掘一下这一点究竟意味着什么。因为我们已经注意到算法I相当缓慢，但是如果在一台高速计算机上运行这个算法，并且给它一段相当长的时间，结果又会怎样？如果在世界上最快的计算机上运行这个算法，我们输入第一个目录，它一瞬间就可以给出答案。给定任意目录，我们能将它输入这台计算机。我们可以让算法I运行一段相当长的时间（比如10年），如果它没有在这段时间内得出结果，我们是否能够得出“它会一直运行下去，因此我们输入的目录不存在解决方案”这个结论？答案还是不能。如果答案是可以，我们就得到了算法II。然而，前面已经提到，这个算法并不存在。从这个论证中，我们可以推断出，一定存在一个有解决方案的目录，但是即使在世界上最快的计算机上运行算法I10年，还是找不出解决方案。
从波斯特的结论中我们获知，存在没有解决方案的对应问题，或者说这等同于没有算法能够判定这个判定问题。另外，我们推导出了一些令人震惊的事实：第一个事实是给定任意时间间隔（比如一个世纪）和任意一个试图解决对应问题的算法，一定存在一个有解决方案的目录，让这个程序在这个时间间隔内无法找出答案；第二个事实是没有解决方案的目录背后隐藏着真实问题。当答案是“是”的时候，一定存在算法能够正确回答判定问题，尽管这些算法可能耗费相当长的时间，但是当答案是“否”的时候，一定不存在能够给出正确答案的算法。含有更多符号的对应问题
我们前面讨论的是有1和2的字符串。我们可以考虑一些拥有不止两个符号的情况。在这些情况下，因为增加符号不会使事情变得更简单，所以“判断瓷砖目录是否有对应问题的解决方案”仍然是不可判定的。在下面的例子中，我们使用了符号0、1、A、B和*（如图2–4所示）。图2–4 多种符号的目录
这个例子将与下一章产生联系。它有很多解决方案。读者可以尝试自己找出一些。
你可能会提问：如果我们将状态数减少到1会发生什么？在这种情况下，问题就变成是否存在一种排列方案，让顶部序列的符号数等于底部序列的符号数。
这里有一个例子（如图2–5所示）。图2–5 存在解决方案的案例
当我们只有一个符号的时候，存在一种简单的处理方式。我们赋予每块瓷砖一个数字，这个数字是顶部符号数减去底部符号数（在本例中，A被赋值–2，B被赋值3，C被赋值–2）。如果存在瓷砖被赋值0，那么它本身就是一个解决方案。如果在目录中至少存在一个正数，一个负数，那么这个对应问题就存在解决方案。如果所有瓷砖的赋值都是正数，或者都是负数，就不存在解决方案。据此，我们得出了一个判断瓷砖目录是否存在解决方案的算法。如果我们将瓷砖限制为只有一个符号，对应问题就是可判定的。
在我们的例子中，有一块正数瓷砖和一块负数瓷砖。因此，一定存在解决方案。为了找到这个解决方案，我们先要找出等于0的组合。三个A和两个B分别得到–6和+6。因此，AAABB是一个解决方案。希尔伯特的第10个问题
1900年，希尔伯特列出23个他认为数学中尚未解决的最重要的问题。这些问题对20世纪上半叶的数学研究方向产生了至关重要的影响。第一个问题是康托尔连续性假设，之后我们会讨论。第二个问题是证明算术公理是连续的。正如我们提到过的，哥德尔证明了“无法在这个系统内证明公理的连续性”。第10个问题与丢番图方程有关。
丢番图方程是有整数系数的多项式方程。我们希望找到这个方程[1]的整数解决方案。一个著名的例子就是毕达哥拉斯定理：x2 + y2 = z2。解决方案是毕达哥拉斯三元组，分别对应直角三角形的三条边。我们熟知的三元组有两个：3、4、5和5、12、13。尽管x2 + y2 = z2有很多整数解决方案，但x3 + y3 = z3却没有正整数解决方案。所以，一些丢番图方程有解决方案，一些没有解决方案。2
希尔伯特的第10个问题本意是设计一个算法：将丢番图方程作为输入，告诉我们是否存在正整数解决方案。这是一个判定问题。如果你输入x2 + y2 = z2，它会回答存在。如果你输入x3 + y3 = z3，它会回答不存在。这再一次证明，这个问题是一个不可判定的判定问题。尤里·马季亚谢维奇（Yuri Matiyasevich）在1970年给出了完整的证明。该证明建立在马丁·戴维斯（Martin Davis）、希拉里·帕特南（Hilary Putnam）和朱莉娅·罗宾逊（Julia Robinson）的研究基础上。这个证明已经超出本书的范畴，但是让我们再次感受这个证明对于不可判定的问题有什么意义。
考虑一下这个算法：首先，数清丢番图方程中的变量个数。然后，将1带入所有变量，检查是否是解决方案。如果发现解决方案就停止，否则尝试将1和2的组合代入变量。如果没有发现解决方案，尝试代入1、2、3的组合，以此类推。
如果存在一个整数解决方案，我们的算法就会找到这个答案。对于x2 + y2 = z2，在尝试从1到5所有可能的组合后就会发现答案。但是，如果我们把x3 + y3 = z3输入这个算法，它会一直运行下去。因此，我们知道希尔伯特的第10个问题是不可判定的，而且如果存在解决方案，我们已经找出一个能够正确回答这个问题的算法。我们可以推导出，没有算法能够正确识别不存在正整数解决方案的丢番图方程。停机问题
我们已经将所有内容输入一台计算机，并且看到计算机死机了。如果有算法能够告诉我们，一个程序将会在某个给定数据上死机，这会十分有帮助，这就是所谓的停机问题。给定一个程序和初始数据，判断这个程序是否会在这段数据上停止。这是另一个判定问题，并且它也是不可判定的。它与另外两个判定问题拥有相同的性质。当答案存在的时候，存在算法能够起效，但是当答案不存在的时候，没有算法能够起效。在这种情况下，这个算法只会让程序去运行这段数据。如果它停止了，就输出“是的”。3剑桥的图灵
当然，图灵在撰写自己的论文时，并不知道任何不可判定的判定问题的例子。图灵和邱奇最早理解了“哪些问题是不可判定的”。希尔伯特的判定问题是给定一个判定问题，找出在任意情况下都能正确回答这个问题的算法。希尔伯特假设这种算法是存在的，即所有判定问题都是可判定的。如果图灵能够证明一些问题是不可判定的，那么他就能证明希尔伯特研究判定问题的方法是存在根本缺陷的。他面临一个相当大的挑战。他需要找出一个可以证明为“不可判定”的非确定性判定问题。他的证明必须展示出没有算法可以解决这个问题。但是在当时，算法究竟意味着什么并没有一个明确的定义。所以，图灵的第一步就是给这个术语一个准确的定义。图灵在发明理论计算机器的时候完成了这项工作。
[1] 毕达哥拉斯定理，即中国的勾股定理。——译者注
试读结束[说明：试读内容隐藏了图片]