1936年，英国剑桥。
一个24岁的年轻人正在写论文。他的论文题目很奇怪：《论可计算数及其在判定问题上的应用》。
这篇论文里没有电路图，没有齿轮设计，没有一行代码。它只描述了一种假想的机器——一种只存在于纸面上的、极度简化的计算装置。
这个年轻人叫艾伦·图灵。他提出的这种机器，后来被称为图灵机。
它被认为是计算机的理论祖先。
一个奇怪的问题 #
图灵为什么要发明这种机器？
这要从数学家希尔伯特说起。
1928年，希尔伯特提出了一个著名的问题：Entscheidungsproblem（判定问题）——是否存在一种算法，可以判定任何数学命题的真假？
换句话说，希尔伯特想知道：数学能不能被完全自动化？ 能不能造一台机器，输入任何数学命题，它就能告诉你这个命题是对还是错？
这个问题困扰了数学界多年。图灵决定攻克它。
图灵机：最简单的计算模型 #
图灵的思路是：先定义什么是"计算"，再判断哪些东西可以计算。
他设计了一种极度简化的机器——图灵机。
图灵机只有三个部分：
- 一条无限长的纸带：纸带分成一个个格子，每个格子里可以写一个符号（比如0或1）
- 一个读写头：可以读取当前格子的符号，也可以写入新符号，还可以左右移动
- 一个状态表：告诉机器在当前状态、读到当前符号时，应该做什么（写入什么、往哪移动、变成什么状态）
就这样！没有内存，没有硬盘，没有CPU，只有纸带、读写头和状态表。
但图灵证明了一个惊人的结论：这台简陋的机器，可以计算任何可计算的东西。
它可以做加法、乘法、开方、解方程。它可以模拟任何复杂的计算过程。如果一个问题能被图灵机解决，那它就是"可计算的"；如果不能，那它就是"不可计算的"。
图灵的回答 #
回到希尔伯特的问题：是否存在一种算法，可以判定任何数学命题的真假？
图灵用他的机器给出了答案：不存在。
他证明，有些问题是图灵机无法解决的——比如"停机问题"：给定一个程序和输入，判断这个程序是否会停止运行。
这个证明过程很复杂，但结论很明确：数学不能被完全自动化。有些问题，机器永远无法回答。
这个结论震惊了数学界。但图灵机的意义，远不止于此。
图灵机为什么重要？ #
你可能会问：图灵机只是一纸面上的假想，它和真正的计算机有什么关系？
关系非常大。
第一，图灵机定义了计算的边界。 它告诉我们，哪些问题可以计算，哪些问题不能计算。这是计算机科学的理论基础。
第二，图灵机证明了通用计算的可能性。 图灵提出了一种"通用图灵机"——它可以模拟任何其他图灵机。这就是现代"通用计算机"的理论原型：一台机器，可以运行任何程序。
第三，图灵机的简单性。 图灵机只有纸带、读写头和状态表，但它能计算任何可计算的东西。这说明，计算的本质是简单的——我们不需要复杂的机器，只需要简单的规则和无限的存储。
后来的所有计算机——从ENIAC到你的手机——在理论上都是图灵机的实现。它们能做的事情，图灵机都能做；图灵机不能做的事情，它们也不能做。
图灵的一生 #
图灵1912年出生于伦敦。他从小就表现出非凡的数学天赋，但也显得格格不入——他不爱运动，不善社交，喜欢独自思考奇怪的问题。
在剑桥大学，他写出了那篇关于图灵机的论文，但当时并没有引起太大反响。数学家们觉得这只是又一个理论模型，和现实没什么关系。
然后，第二次世界大战爆发了。
图灵被招募到布莱切利园，参与破解纳粹德国的密码。德国人使用一种叫"恩尼格玛"的加密机器，它的密码每天变化，理论上无法破解。
但图灵做到了。他设计了一种叫"Bombe"的机电装置，可以快速尝试各种可能的密钥。在他的领导下，布莱切利园每天破解数千条德军情报，为盟军胜利做出了巨大贡献。
历史学家估计，图灵的工作缩短了战争2-4年，拯救了1400万人的生命。
悲剧的结局 #
战后，图灵继续研究计算机和人工智能。他提出了著名的"图灵测试"：如果一台机器能和人对话，而人分辨不出它是机器，那就可以说这台机器"会思考"。
但他的生活并不顺利。1952年，他因同性恋行为被英国政府起诉。当时同性恋在英国是非法的。图灵被迫接受"化学阉割"——注射雌激素来"治疗"同性恋。
两年后，1954年6月7日，图灵被发现死在家中，床头有一个咬了一口的苹果。验尸报告显示，他死于氰化物中毒。
他只有41岁。
迟来的正义 #
图灵去世多年后，世界才开始认识到他的伟大。
1966年，美国计算机协会设立了图灵奖，奖励对计算机科学做出重大贡献的人。图灵奖被称为"计算机界的诺贝尔奖"。
2009年，英国首相戈登·布朗代表政府向图灵道歉：“代表英国政府，以及所有因你的工作而自由生活的人，我要说：我们很抱歉。”
2013年，英国女王正式赦免图灵。
2014年，电影《模仿游戏》上映，讲述了图灵破解恩尼格玛的故事。主演本尼迪克特·康伯巴奇说：“图灵是计算机科学之父，也是战争的英雄。”
图灵的遗产 #
今天，每当你在手机上运行一个APP，每当你在电脑上打开一个网页，你都在使用图灵的思想。
图灵机告诉我们：计算的本质是简单的，但简单的规则可以产生无限的可能。
这个思想，在图灵之后被另一个人发扬光大。他把图灵机的理论变成了具体的工程设计，定义了现代计算机的架构。
他叫约翰·冯·诺依曼。
他的故事，我们明天继续。
今日知识点 #
图灵机（Turing Machine） 一种理论上的计算模型，由无限纸带、读写头和状态表组成。图灵机可以计算任何"可计算"的东西，是计算机科学的理论基础。现代计算机在理论上都是图灵机的实现。
停机问题（Halting Problem） 图灵证明的一个不可判定问题：不存在算法可以判断任意程序是否会停止运行。这说明了计算的边界——有些问题是机器无法解决的。
图灵测试（Turing Test） 图灵提出的一种判断机器是否具有智能的方法：如果一台机器能和人对话，而人无法分辨它是机器还是人，就可以说这台机器具有智能。这是人工智能领域的重要概念。
思考题 #
- 图灵机只有纸带、读写头和状态表，但它能计算任何可计算的东西。你觉得这说明计算的"本质"是什么？
- 图灵因为同性恋被迫害，最终自杀。你觉得一个社会应该如何对待"与众不同"的人？
明天预告：冯·诺依曼与存储程序计算机——如何把图灵的理论变成真正的机器？