图灵相信机器会思考。图灵和男人睡觉。所以机器不会思考。

— 艾伦·图灵，致诺曼·劳特利奇的信（1952）

这个苦涩的三段论，是图灵在被定罪后不久写给一位朋友的，它概括了他的一生：一个用逻辑思考的人，被不理解他的人审判。然而，他留下的成果无处不在。

在计算机科学中

图灵机仍然是“计算”的正式定义。当计算机科学家说一个问题“没有算法”时，意思是没有图灵机能解决它；当他们说一个问题“难”时，数的是图灵机需要走多少步。

从这种计数中产生了这个领域最著名的问题——P 与 NP：每个解很容易验证的问题，是否也都很容易找到解？拼一幅拼图很难；检查一幅拼好的拼图很容易。没有人知道这种差别是真实存在的，还是只是我们不够聪明。克雷研究所悬赏一百万美元，奖给回答这个问题的人。

自 1966 年起，美国计算机协会每年颁发图灵奖，它被视为计算机领域的诺贝尔奖。

在密码学和统计学中

对恩尼格玛的战争表明，一种密码的安全不在于密钥的数量，而在于没有能一下子排除大部分密钥的缺陷。现代密码学就诞生于这个教训。而分班经由 I. J. 古德，帮助把贝叶斯统计带回了科学的中心。

在生物学和人工智能中

形态发生的方程是一整个领域——图案的数学生物学——的基础。而模仿游戏在机器已经能够对话的今天，仍是任何关于机器能否思考的讨论的参照。

曼彻斯特萨克维尔公园里的图灵雕像，2001 年揭幕。他坐在长椅上，手里拿着一个苹果。
曼彻斯特萨克维尔公园里的图灵雕像，2001 年揭幕。他坐在长椅上，手里拿着一个苹果。David Dixon · Wikimedia Commons · CC BY-SA 2.0

补偿

几十年里，图灵在战争中的工作是国家机密，他的定罪则是不被提起的话题。1983 年，数学家安德鲁·霍奇斯写的传记出版，情况开始改变。随后有了：

  • 2001 年，在大学旁边的一座公园里，竖起了曼彻斯特的雕像；
  • 2009 年，英国政府的道歉；
  • 2013 年的王室赦免，以及 2017 年赦免其他被定罪者的法律；
  • 印有他头像的 50 英镑纸币，于 2021 年 6 月 23 日——他的生日——发行。

要记住的

  • 1936 年：图灵机定义了什么是计算，通用机预示了存储程序计算机。
  • 1936 年：停机问题表明有些问题没有机器能回答，可计算数表明几乎每个实数都遥不可及。
  • 1939–1945 年：恩尼格玛的计数与缺陷、炸弹机，以及带着分班的班伯里法。
  • 1950 年：模仿游戏用一个测试取代了“机器会思考吗？”这个问题。
  • 1952 年：形态发生解释了扩散如何产生图案。
练习：验证很容易

有人说 $8633=89\cdot97$。验证它要花多少功夫？如果没有提示，要找到这两个因数又要花多少功夫？

验证只需一次乘法：$89\cdot97=89\cdot100-89\cdot3=8900-267=8633$。寻找则要试除到 $\sqrt{8633}\approx93$ 为止：从 2 到 89 一共 24 个素数，只有最后一个成功。对于几百位长的数，验证仍然瞬间完成，寻找却变得不可行。互联网的密码学就建立在这种不对称上。

练习：图灵的三段论

题记中的三段论有效吗？错在哪里？

它无效。前提说的是图灵，结论说的却是机器。一个人持有某种观点、过着别人不赞成的私人生活，这与那个观点是否正确毫无关系。图灵写下这个三段论，正是为了嘲讽这种推理。

来源： Andrew Hodges, Alan Turing: The Enigma（1983）· 图灵奖，ACM · P vs NP, Clay Mathematics Institute · 英格兰银行，50 英镑纸币。

艾伦·图灵的全部主题 · ← 形态发生：方程里的豹斑 · 图片来源 →

图片来源.