跳转到内容
← 返回数学家
现代计算理论约 15 分钟阅读

图灵

Alan Turing

英国·1912–1954
图灵机停机问题图灵测试恩尼格玛可计算性

生平

艾伦·图灵（Alan Turing，1912—1954）是英国数学家、计算机科学之父和人工智能先驱。他出生于英国伦敦帕丁顿，父亲是印度民政部的公务员。图灵从小就展现出对科学和数学的浓厚兴趣。

1926年，图灵进入谢伯恩公学学习。他对数学和自然科学的热情远超其他学科，以至于他的老师抱怨他"只关心科学，忽视了人文学科"。1931年，他获得奖学金进入剑桥大学国王学院学习数学。

1935年，图灵在剑桥大学获得数学学位，同年被选为国王学院研究员。他的研究兴趣转向了数学基础——特别是希尔伯特的判定问题（Entscheidungsproblem）：是否存在一个算法能够判定任意数学命题的真假？

1936年，图灵发表了《论可计算数及其在判定问题上的应用》，引入了图灵机的概念，证明了停机问题的不可判定性。这篇论文不仅解决了希尔伯特的判定问题，还为现代计算机科学奠定了理论基础。

1938年，图灵获得普林斯顿大学博士学位，导师是阿隆佐·丘奇（Alonzo Church）。丘奇独立于图灵发展了λ演算，得出了与图灵等价的结论——这就是著名的丘奇-图灵论题。

1939年，第二次世界大战爆发。图灵加入英国政府密码学校（GC&CS），在布莱切利园（Bletchley Park）从事破解德国恩尼格玛密码的工作。他设计了英国版的"炸弹"（Bombe）解密机——这一工作建立在波兰密码学家雷耶夫斯基（Marian Rejewski）等人此前研制的"bomba"之上，而图灵的同事韦尔奇曼（Gordon Welchman）又在 1940 年加上了关键的"对角板"（diagonal board）改进，大幅提升了破解效率。换言之，恩尼格玛的攻破是波兰先驱 + 图灵 + 韦尔奇曼及布莱切利园整个团队接力的成果，不应只归功于一人。

战后，图灵加入了国家物理实验室（NPL），设计了自动计算引擎（ACE）——最早的电子计算机设计方案之一。1948年，他加入曼彻斯特大学，成为计算机实验室的副主任。

1950年，图灵发表了《计算机器与智能》，提出了图灵测试——判断机器是否具有智能的标准。他还研究了形态发生学，用数学模型解释生物体的图案形成。

1952年，图灵因同性恋行为被起诉。在当时的英国，同性恋是犯罪行为。图灵选择接受化学阉割（注射雌激素）以避免入狱。1954 年 6 月 8 日，他被发现死于家中（验尸推断死亡时间为 6 月 7 日），旁边是一个咬了一口的苹果。验尸官裁定为氰化物中毒自杀。但这一结论近年受到认真质疑：那个苹果从未被检测是否含氰化物，而图灵当时正在家中用氰化钾做镀金实验——逻辑学家杰克·科普兰（Jack Copeland）等人据此提出，他更可能是吸入氰化物蒸气意外中毒，且当时并无任何表明他打算轻生的证据。因此"咬毒苹果自杀"虽是流传最广的版本，却并非定论。

2013 年 12 月，英国女王伊丽莎白二世动用"皇家赦免特权"正式赦免了图灵（1945 年后极少使用的特权）。2019 年 7 月，英格兰银行宣布图灵将成为新版 50 英镑纸币的人物；该纸币于 2021 年 6 月 23 日——图灵的生日——正式发行。

核心贡献

图灵机

图灵引入了图灵机（Turing machine）——一个抽象的计算模型，精确地定义了"可计算"的含义。

图灵机的组成： 1. 无限长的纸带：划分为单元格，每个单元格可以存储一个符号 2. 读写头：可以读取、写入和移动纸带上的符号 3. 状态寄存器：存储机器的当前状态 4. 转移函数：根据当前状态和读取的符号，决定写入什么符号、如何移动读写头、转移到什么状态

形式定义：图灵机是一个七元组 M=(Q,Γ,b,Σ,δ,q0,F)M = (Q, \Gamma, b, \Sigma, \delta, q_0, F)： - $Q$：有限状态集合 - Γ\Gamma：纸带字母表 - b∈Γb \in \Gamma：空白符号 - Σ⊆Γ∖{b}\Sigma \subseteq \Gamma \setminus \{b\}：输入字母表 - δ:Q×Γ→Q×Γ×{L,R}\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}：转移函数 - q0∈Qq_0 \in Q：初始状态 - F⊆QF \subseteq Q：接受状态集合

丘奇-图灵论题：一个函数是"能行可计算的"（即直觉上"可以机械地一步步算出来的"），当且仅当它可以被图灵机计算。这里要点破一个常见误区：丘奇-图灵论题不是一条已证明的定理，而是一个关于"如何用数学模型刻画'可计算'这个直觉概念"的论断——因为"直觉上的可计算"本身不是一个形式化对象，无法被严格证明。它之所以被广泛接受，是因为所有为"可计算"提出的独立形式化（图灵机、丘奇的 λ 演算、哥德尔-埃尔布朗的一般递归函数、寄存器机……）最后都被证明彼此等价——殊途同归，这是支持论题的最强经验证据。图灵的论文之所以特别有说服力，正因为他不是凭空给出定义，而是从"一个人按固定规则用纸笔计算"这一物理图像出发，论证了任何这样的过程都能被图灵机模拟。

停机问题的不可判定性

图灵证明了停机问题的不可判定性：

定理：不存在一个算法（图灵机）能够判定任意程序在给定输入下是否会终止。

证明（对角线法）：

假设存在这样的判定器 $H$，使得： H(P,x)={accept如果程序 P 在输入 x 上停机reject否则H(P, x) = \begin{cases} \text{accept} & \text{如果程序 } P \text{ 在输入 } x \text{ 上停机} \\ \text{reject} & \text{否则} \end{cases}

构造程序 $D$： D(P)={loop forever如果 H(P,P)=accepthalt如果 H(P,P)=rejectD(P) = \begin{cases} \text{loop forever} & \text{如果 } H(P, P) = \text{accept} \\ \text{halt} & \text{如果 } H(P, P) = \text{reject} \end{cases}

考虑 $D(D)$： - 若 $D(D)$ 停机，则 H(D,D)=acceptH(D,D) = \text{accept}，但 $D$ 的定义使 $D(D)$ 不停机，矛盾 - 若 $D(D)$ 不停机，则 H(D,D)=rejectH(D,D) = \text{reject}，但 $D$ 的定义使 $D(D)$ 停机，矛盾

因此 $H$ 不存在。

这个对角线论证与康托尔证明实数不可数、以及哥德尔构造不可证命题用的是同一招——都是"假设有一个能判定一切的东西，然后把它用在自己身上，逼出自相矛盾"。值得澄清两点常被混淆之处：第一，停机问题的不可判定性说的是不存在统一的算法对所有程序-输入都判定停机，而不是说"任何具体程序都判不出停不停"——很多具体程序当然能判断。第二，图灵的真正目标是用停机问题的不可判定性，推出希尔伯特的"判定问题"（Entscheidungsproblem，是否存在算法判定任意一阶逻辑命题是否可证）也无解；这才是 1936 年那篇论文标题里"判定问题"的由来。丘奇用 λ 演算几乎同时得到了同样的否定结论——两人的工作合在一起，宣告了希尔伯特"机械地判定一切数学真理"之梦的终结。

图灵测试

图灵在1950年提出了图灵测试——判断机器是否具有智能的标准。

测试方法：一个人（裁判）通过文本与两个参与者（一个是人，一个是机器）进行对话。如果裁判无法可靠地区分人和机器，则机器通过了图灵测试。

图灵测试避免了"什么是智能"的哲学争论，而是提供了一个操作性的标准。虽然图灵测试至今仍有争议，但它深刻影响了人工智能的发展方向。

恩尼格玛密码的破解

图灵在二战中破解了德国的恩尼格玛（Enigma）密码系统。恩尼格玛机使用转子系统进行加密，理论上可能的密钥组合约为 $158,962,555,217,826,360,000$ 种。图灵设计了"炸弹"（Bombe）解密机，利用德国通信中的已知片段（cribs，如每天天气预报的固定格式）来排除海量错误密钥、缩小搜索范围。到战争中期，布莱切利园每天能破解大量恩尼格玛加密的通信。

关于贡献的大小，需要给出准确的来源与口径：英国情报史官辛斯利（Harry Hinsley）的估计是，布莱切利园整体的破译工作把欧洲战争缩短了"不少于两年、很可能达四年"——这是史学家的估计，针对的是整个团队的成果，而非图灵一人，更不是一个被证实的精确数字。还要澄清一处广为流传的伪引语：常被归于丘吉尔的"图灵作出了对盟军胜利最大的单一贡献"一语，并无任何史料支持（国际丘吉尔学会明确指出查无实据，这是 1990 年代以来被反复转述的讹传）；丘吉尔本人确曾在 1941 年批示优先满足布莱切利园的资源请求（著名的"立即照办"——Action This Day 批条），但他从未公开把功劳单独记在某一个人头上。

形态发生学

图灵在生命的最后几年研究了形态发生学——生物体图案形成的数学模型。他提出了反应扩散方程：

∂u∂t=Du∇2u+f(u,v)\frac{\partial u}{\partial t} = D_u \nabla^2 u + f(u, v) ∂v∂t=Dv∇2v+g(u,v)\frac{\partial v}{\partial t} = D_v \nabla^2 v + g(u, v)

其中 $u, v$ 是两种化学物质的浓度，Du,DvD_u, D_v 是扩散系数，$f, g$ 是反应项。图灵发现，即使反应项不具有空间结构，扩散也可以导致空间图案的自发形成——这被称为图灵不稳定性。这一理论解释了动物身上的条纹、斑点和螺旋图案的形成机制。

历史背景

图灵生活在20世纪上半叶的英国。这一时期英国经历了两次世界大战和大英帝国的衰落。图灵的计算理论和密码学工作直接服务于战争需要。在数学方面，20世纪30年代是数理逻辑的黄金时代。哥德尔的不完备定理（1931）终结了希尔伯特的纲领，图灵和丘奇的可计算性理论（1936）进一步揭示了数学的局限性。同时，这些理论工作催生了计算机科学——图灵机成为现代计算机的理论模型。

思想遗产

图灵的影响深远而持久：

  1. 计算理论：图灵机成为计算理论的基础，所有现代计算机本质上都是通用图灵机的实现
  2. 人工智能：图灵测试至今仍是讨论机器智能的标准框架
  3. 密码学：图灵的解密工作开创了现代密码分析
  4. 生物学：形态发生学模型解释了自然界图案的形成
  5. 计算机科学：图灵被称为"计算机科学之父"

图灵奖是计算机科学领域的最高荣誉，被称为"计算机界的诺贝尔奖"。

与其他数学家的关系

  • 哥德尔：图灵的停机问题从计算角度重新证明了哥德尔不完备定理
  • 丘奇：独立发展了λ演算，与图灵的图灵机等价
  • 冯·诺伊曼：受到图灵机概念的启发，设计了存储程序计算机
  • 香农：图灵在贝尔实验室与香农讨论过机器智能
  • 希尔伯特：图灵的停机问题解决了希尔伯特的判定问题

跨域连接

  • 偏微分方程：反应扩散方程组给出一个反直觉结论：扩散通常抹平差异，但两种物质扩散速度相差足够大时，均匀定态会对某一段波长的扰动失稳。判据来自线性稳定性分析——把扰动按波数展开，看哪些波数的增长率为正，图案的特征间距由此定下。
  • 演化发育生物学：条纹与斑点因此不必逐条写进基因，只要有一对扩散速度相差够大的激活与抑制信号。这给出可检验的预言：图案的特征间距应随组织尺度与扩散系数变化，而不是固定不变；同一套机制在大小不同的胚胎上应当产生条数不同的图案。
  • 化学平衡：斑图只能在持续供能、远离平衡的体系中维持。平衡态下浓度梯度必然被抹平，因为自由能已取极小，任何空间结构都是自发退化的方向。所以图灵机制不是"化学自己长出花纹"，而是耗散结构，撤掉输入花纹就会消失。
  • 行为主义：图灵测试把"机器是否思考"换成"行为能否被区分"，这是彻底的行为主义策略。代价很明确：一切关于内部状态的主张都被排除在检验之外。因此通过测试既不能证明也不能否证机器有心灵，它检验的只是可观察行为的可区分性。
  • 第二次世界大战：破译工作靠的是已知明文片段大幅缩小密钥搜索空间，再用机电装置并行排除。这说明密码强度不只取决于密钥空间大小，也取决于使用规范：格式固定的日常报文本身就是漏洞。功劳属于一整条接力的团队，把它记在某一个人头上并不符合史实。

参考文献

  1. Alan Turing, On Computable Numbers (1936)
  2. Alan Turing, Computing Machinery and Intelligence (1950)
  3. Andrew Hodges, Alan Turing: The Enigma (1983)
  4. Jack Copeland, Turing: Pioneer of the Information Age (2012)

延伸阅读

  1. 梁宗巨, 《数学历史典故》, 辽宁教育出版社, 1992

「机器能思考吗？」——图灵