有个古老而经典的逻辑游戏：如果一个人说“我正在说谎”，那么他到底在不在说谎呢？如果他不在说谎，那么“我正在说谎”这句话就是真的；如果他在说谎，那么“我正在说谎”这句话就是假的。无论从哪个方向推演，得到的都是自相矛盾的结论，我们无从判定他在不在说谎。

这就是公元前4世纪，由哲学家欧布里德（Eubulides）提出的著名的说谎者悖论。
与之类似的，还有伯特兰·罗素（Bertrand Russell）在1901年提出的罗素悖论，它的通俗化版本是流传更广的理发师悖论：如果一位理发师只给不为自己理发的人理发，那他给不给自己理发呢？

罗素悖论直接动摇了整个数学大厦的根基——集合论。为使命题合理，当那位理发师圈定服务对象的范围时，必须把自己排除在外。这也就意味着，没有包罗万象的集合——至少它不能轻易包含自己。

这些悖论都源自“罪恶”的自指——当一套理论开始描述自身，就难免要出现悖论。
即使再不情愿，人们也不得不承认数学是不完美的，至少它没有自圆其说的能力。
尽管如此，仍有数学家想在限定的范围内负隅顽抗，他们找到一个完备的系统^[1]，寻求能够判定命题真假的通用算法。这就是德国数学家大卫·希尔伯特（David Hilbert）和威廉·阿克曼（Wilhelm Ackermann）在1928年提出的判定问题（Entscheidungsproblem/decision problem）。

只可惜没过几年，这种可能性也被否定了。

1936年，两位年轻的数学家分别用不同的方法给出了判定问题的解答。一位是来自美国的阿隆佐·邱奇（Alonzo Church），他引入了一种叫λ演算的方法，并最终证明没有任何通用算法可以判定任意两个λ表达式是否相等；另一位就是来自英国的艾伦·图灵（Alan Turing），和枯燥的数学推理不同，他使用了一种更有趣、更形象的模型，邱奇给了它一个响亮的名字——图灵机（Turing machine）。

图灵早年经历

艾伦·麦席森·图灵（Alan Mathison Turing），1912-1954，英国数学家、计算机学家、逻辑学家、密码学家、哲学家、理论生物学家。（图片来自维基百科）

1912年6月23日，图灵出生于英国帕丁顿一个没落的贵族家庭，由于父母常年在印度工作，他和年长4岁的哥哥一起被寄养在一对军人夫妇的家中。图灵的童年十分平凡，和普通男孩一样，经历过调皮捣蛋和孤僻寡言的的阶段，他天性聪敏却有着严重偏科的倾向，许多教过他的老师对他的评价并不高。

10岁那年，图灵接触到一本改变了他一生的童书——《儿童必读的自然奇迹》，这本科普读物打开了一扇新世界的大门，图灵发现门的那边堆满了一种对他来说最有吸引力的知识——科学。他开始疯狂地寻找和自学有关科学的一切知识，并用日用品做一些简单的化学实验。他很快意识到手头的科普读物过于浅显，妨碍了他了解事物背后更深层的原理。他甚至写信给父母讨要真正的科学书籍，而不是儿童百科。他写到：“《儿童必读的自然奇迹》中说，二氧化碳在血液里变成苏打，又在肺里变回二氧化碳。如果可以，请把苏打的化学名称，最好是化学式寄给我，好让我看看这个过程到底是怎么进行的。”13岁时，他已经对酒精等有机物的分子式和结构式了如指掌。

1926年，聪明好学而又对科学知识近乎偏执的图灵考入了舍尔伯尼中学。开学当天正赶上英国大罢工，公共交通瘫痪，图灵竟用两天时间靠自行车征服了到学校的60英里（近100公里）路程。这不是一次冲动之举，而是精心策划之下的行动，当地报纸还专门刊载了这一令人吃惊的事迹。

图灵很有才，也很有执行力，却在与人沟通上遇到了大麻烦。知子莫若母，图灵的母亲在为他寻找合适的中学时就一度担心他没法适应公学^[2]生活，成长为高智商、低情商的怪人。在讲究教条与制度而不重视理性和科学的舍尔伯尼，图灵显得格格不入，被多数同学孤立和欺负，连老师也经常拿他的小习惯开涮，这对一个心智尚未成熟的男孩来说非常可怕。他们的校长倒看得十分透彻，曾警告图灵的父母：“我希望他不要两头都落空。如果他要留在公学，就必须以好好接受我们的教育为目标；如果他只是想做科学家，那么呆在公学就是浪费时间。”

舍尔伯尼是当时英国社会的一个缩影，中学的经历也预示着图灵不被理解的一生。

1931～1934年，成年后的图灵在剑桥大学国王学院攻读数学专业。尽管这里的制度依旧古板，像个放大版的舍尔伯尼，图灵依旧孤僻，但接触到了世界顶级的数学家和一流的学术专著，他可以更专注于自己喜欢的领域，并包揽了许多数学方面的奖项。毕业后，图灵以优异的成绩成为国王学院研究员。他在希尔伯特的问题上花费了整整一年的时间，最终在1936年的《伦敦数学协会会刊》上发表了那篇改变世界的论文——《论可计算数及其在判定问题中的应用》，提出了使其成为“计算机科学之父”的图灵机。

图灵机

工作原理

图灵机是图灵受打字机的启发而假想出来的一种抽象机器，其处理对象是一条无限长的一维纸带。纸带被划分为一个个大小相等的小方格，每个小方格可以存放一个符号（可以是数字、字母或其他符号）。有个贴近纸带的读写头，可以对单个小方格进行读取、擦除和打印操作。为了让读写头能访问到纸带上的所有小方格，可以固定纸带，让读写头沿着纸带左右移动，每次移动一格，或者固定读写头，让纸带左右移动——后一种方式类似当时穿孔带以及后来磁带和磁盘的做法，但在纯理论讨论时为了方便说明，我们通常选用前一种方式。

图灵机纸带示意图

那么读写头该如何移动，移动之前或移动之后又该作何操作呢？这取决于机器当前的状态，以及读写头当前所指小方格中的内容，机器中有着一张应对各种情况的策略表。这就好比有一只小猫，你往它碗里放些食物，它会根据自己饿不饿以及食物的类别判断吃还是不吃，我们可以大体列出一张策略表：

小猫进食策略表

在这个例子中，小猫就好比图灵机，碗就是纸带上的小方格，食物就是小方格中的符号。当然这只是一个简化的类比，也有很多不挑食的小猫会吃白米饭，或者贪食的小猫即使吃饱了看见鱼还是会继续吃。在理想情况下，当我们提供一排足够多的碗，并在碗中放置更多种类的食物和玩具，猫在碗与碗间来回走动，就更像一台图灵机了。

为了更精确地说明，我们构造一台简单的图灵机，实现对纸带上所有3位二进制数的+1操作（超过3位的进位将被丢弃），相邻两个二进制数之间通过一个空的小方格隔开，形如下图所示，读写头从最右侧二进制数的最低位开始扫描，遇到连续2个空方格时认为已处理完所有数，机器停机。

图灵机示例纸带

策略表如下表所示，其中E表示擦除、P表示打印、L表示左移。

图灵机示例策略表

该图灵机有3种工作状态：

1. S₁是+1状态，也是机器的初始状态。如果读写头遇到的是0，则直接将0改为1即完成了+1任务，左移一格后进入状态S₂；如果遇到的是1，则将1改为0，由于需要进位，即对下一位+1，左移一格后仍留在状态S₁；如果遇到的是一个空方格，即使当前需要进位，也不做处理（将进位丢弃），左移一格后进入状态S₃。
2. S₂是左移状态，此时已实现当前二进制数的+1，需要将读写头移到下一个数的最低位。如果遇到0或1，说明读写头还在当前二进制数上，继续左移；如果遇到空方格，后面等着它的可能是下一个二进制数，也可能是永无止境的空方格，左移一格之后进入状态S₃。
3. S₃是判断状态，根据情况判断是否还有二进制数要处理。如果读写头遇到的是0或1，说明当前位置是一个新的二进数的最低位，直接交给S₁处理；如果遇到的仍是空方格，说明后续不再有数据，停机。

根据以上策略，该图灵机处理纸带的过程为：

如法炮制，我们可以设计出具有各种功能的图灵机，而策略表的制定则类似于编程。图灵想到，如果把策略表中的信息以统一的格式写成符号串（比如上表可以表达成S1/0/EP1L/S2 S1/1/EP0L/S1 S1//L/S3 ……），然后放在纸带的头部，再设计一台能在运行伊始时从纸带上读取这些策略的图灵机，那么针对不同的任务，就不需要设计不同的图灵机，而只需改变纸带上的策略即可。这种能靠纸带定制策略的图灵机，称为通用图灵机UTM（universal Turing machine）。

不单是策略表，其实用于描述图灵机的所有信息（包括所使用的符号、初始状态等）都可以表达成纸带上的符号串。这就意味着，一台图灵机可以成为另一台图灵机的输入。

判定问题的解答

在试想一下，在有些情况下，一台图灵机如果长时间没有输出结果，那么它很可能陷入了死循环或永无止境的计算中。这是我们不愿看到的，因为机器可能运行1分钟后停机，也可能运行10天半个月甚至几十年才停机，亦或者永远也不会停机，这个很难靠人为判断。假设我们构建出一台图灵机H，它接收其他图灵机及其输入信息作为输入，并能够判定其是否会停机，就解决了上面的烦恼——构建这样的机器难度虽大，但理论上是可行的。

这就是著名的停机问题（halting problem）。

H所处理的，本质上正是一种判定问题：某台图灵机在某输入上是否会停机。只要找到一台H判定不了的机器，希尔伯特的美梦就破灭了。

令H表现如下图所示，如果其判定对象会停机则输出1，反之输出0。

图灵机H运行流程

我们再构建一台图灵机G，其运行流程如下图所示。如果H输出1，说明G会停机，但事实上它将陷入循环；如果H输出0，说明G不会停机，但事实上它将停机。

图灵机G运行流程

悖论已经出现，H无法对G的停机问题进行判定。又一次归因于尴尬的自指：当一个系统强大到一定程度时，终究会遇到无法处理自己的窘境。

因此，不存在一台图灵机，可以判定任意图灵机是否会停机。图灵机不是万能的，判定问题的答案也是否定的。而这个看似有点耍赖的证明方式，有着图灵长达36页的数学论证支撑。

深远的意义

图灵的工作不仅回答了希尔伯特的问题，更参透了数学和计算机的本质关系——计算机是为解决数学问题而诞生的，却又基于数学，因而数学自身的极限也便框定了计算机的能力范围。

图灵虽然证明了没有任何机器可以解决所有数学问题，却也证明了机器可以完成所有人类能完成的计算工作，从如今的应用看来，后一个结论的意义重大得多。

从图灵开始，计算机有了真正坚实的理论基础，更多人开始投身计算机的理论研究，而不仅是尝试构建一台机器。从如今的应用来看，图灵机之于计算机领域的价值远高于数学领域，毕竟判定问题还有λ演算和许多其他解答，但计算机的原始公式，只有图灵机这一个。

如今的所有通用计算机都是图灵机的一种实现，两者的能力是等价的。当一个计算系统可以模拟任意图灵机（或者说通用图灵机）时，我们称其是图灵完备的（Turing complete）；当一个图灵完备的系统可以被图灵机模拟时，我们称其是图灵等效的（Turing equivalent）。图灵完备和图灵等效成为衡量计算机和编程语言能力的基础指标，如今几乎所有的编程语言也都是图灵完备的，这意味着它们可以相互取代，一款语言能写出的程序用另一款也照样可以实现。

后话

论文正式发表之前，图灵只身前往美国普林斯顿，在那里找到了领先一步发表成果的邱奇，并师从他继续深造。1937年，图灵嗅到了纳粹德国引战的可能，开始把业余时间花在密码学的研究上。1938年，图灵在取得博士学位后返回了正在紧张备战的英国，不多久，他便参与到政府的密码破译^[3]项目中，和全国各地顶尖的数学家们一起，在白金汉郡的布莱切利公馆（Bletchley Park）中深居简出，左右世界战争的格局。

二战时期，各国已经使用无线电进行作战指挥，由于信号可以轻易被敌国接收，需要对无线电内容进行加密，比如将“ABCD”改成“BCDE”发出去，当然军用的加密方式不会如此简单。当时的德国使用一种叫谜机（Enigma machine）的加密机器，按下某个字母的按键，其加密后对应的字母小灯就会亮起。内部的转轮和接插线板将这种对应关系随意打乱，每按一次按键，转轮就会转动一次，组合成新的对应关系，比如第一次按下A，D灯亮起，再按一次A，亮起的可能是Z灯，毫无规律可循。更棘手的是，德军几乎每天都会变更其中的接线。

3转轮谜机（图片来自维基百科）

解密的方式是穷举，即遍历所有可能的对应关系，直到找出有意义的关键词，而这恰恰是机器最擅长的事。英国的同盟国波兰在战前就成功研制了破解谜机的炸弹机（bomba），可惜德国在1938年年底将谜机上的转轮从3个增加到了5个，解密的复杂度呈爆炸式增长，针对3转轮谜机设计的炸弹机还未在二战发挥价值就已经宣告报废。解决这个难题的关键人物正是图灵，新建的炸弹机（bombe）成功破解了5转轮谜机。其难度之大，大到英国首次利用破解的信息破坏德军行动时，德国的密码专家首先排除了谜机被破解的可能性。

图灵炸弹机（图片来自维基百科）

随后，对密码学有着深刻认识的图灵还探索出一种高效的解密算法，人称图灵方法（Turingery），该算法成为布莱切利破解德国密码的核心理论。

布莱切利的工作是图灵在短暂的一生中，为人类所做的第二项伟大贡献。他的成果使战争至少提前2年结束，挽救了至少1400万人的生命。前英国首相温斯顿·丘吉尔曾表示，二战的胜利最该感谢的人就是图灵。

战后，图灵进入国家物理研究所，并设计了属于最早一批电子计算机之一自动计算机ACE（Automatic Computing Engine），首次实现了他心目中的通用图灵机。1950年3月10日，ACE的简化版Pilot ACE开始运行，完整的ACE直到图灵去世之后才建成。

Pilot ACE（图片来自维基百科）

1948年，图灵成为曼彻斯特大学数学系讲师，并于次年担任学校计算机实验室的副主任，负责计算机软件的研究。他还成为计算机企业的顾问，帮助其研发商用电子计算机。1951年，英国皇家学会将图灵吸纳为会员。

这些年间，图灵的主要智慧仍留给了数学和计算机的理论研究。1950年，第二篇影响世界的论文《计算机与智能》问世，在那个电子计算机才刚刚起步的年代，高瞻远瞩的图灵用一个问题就叩开了人工智能的大门：“机器会思考吗？”文中提出了著名的图灵测试（Turing test）：让一台机器躲在挡板后回答测试人员的提问，看测试人员能否判断自己面对的是机器还是真人。能否通过图灵测试，是衡量机器智能程度的重要指标。这位“人工智能之父”过于乐观地预言：到2000年，计算机应该能“骗过”30%的测试人员。

图灵机、炸弹机、人工智能……图灵献给世界太多伟大的作品，却没能在生前得到应有的名誉乃至起码的认可。人们始终觉得他是个难以亲近的怪人，对其二战时期涉密的功绩更是一无所知。1952年，他因同性恋的罪名被起诉，在坐牢和化学阉割之间，他无奈选择了后者，旁人的偏见和药物的副作用使他承受着精神和肉体的双重痛苦。1954年6月7日晚上，他躺在家里因氰化物中毒离开了人世，床头放着一个咬过的苹果，还有16天就是他42岁的生日。尸检的结果认定图灵是通过毒苹果自杀的，却没有对这个苹果做氢化物检测，他的母亲和哥哥却坚持认为这是一场化学实验导致的意外，而真相只有图灵自知。

2009年，超过3万人在线请愿为图灵平反，英国首相戈登·布朗代表政府公开道歉。2013年，英国女王伊丽莎白二世正式颁发皇家赦免，图灵终于得到了迟来的公道。
1966年，美国计算机协会ACM（Association for Computing Machinery）设立计算机领域的最高奖项，命名为图灵奖。图灵奖素有“计算机界的诺贝尔奖”之称，图灵的名字当之无愧。

2019年，英国的中央银行——英格兰银行宣布，图灵的肖像将出现在新版的50英镑纸币上，以此纪念这位改变了国家乃至整个世界命运的伟人。

参考文献

• 本特利 P J. 计算机：一部历史[M]. 顾纹天, 译. 北京: 电子工业出版社, 2015.
• 张桢胜. 图灵的“数字宇宙”：逻辑原理与哲学意蕴[D]. 昆明: 云南师范大学, 2018.
• 方弦. 计算的极限（零）：逻辑与图灵机[EB/OL].
• Wikipedia. Entscheidungsproblem[EB/OL].
• Wikipedia. Alan Turing[EB/OL].
• 霍奇斯 A. 艾伦·图灵传：如谜的解谜者[M]. 孙天齐, 译. 长沙: 湖南科学技术出版社, 2012.
• Hodges A. Alan Turing: The Enigma[M]. Princeton: Princeton University Press, 2014.
• Turing A M. On Computable Numbers, with an Application to the Entscheidungsproblem[J]. Proceedings of the London Mathematical Society, 1936, 43(43):13-115.
• Wikipedia. Halting problem[EB/OL].
• Wikipedia. Turing completeness[EB/OL].

1. 逻辑学中的一阶谓词演算是完备的，感兴趣的读者可以深入了解。 ↩

2. 公学是英国的公共学校，是面向富裕家庭的精英学校，只招收中产和贵族阶级的孩子。 ↩

3. 本书所提及的二战期间的密码（cipher）与现今我们登陆账号所用的密码（password）不是同一概念，前者是对明文按照一定规则转换后生成的密文，后者则是通行口令，切勿混淆。 ↩