Alan Turing · 1912–1954

图灵

他把「机械地算」这四个字说清楚了，也画出了计算机的第一张蓝图

\delta:\ Q \times \Gamma \to Q \times \Gamma \times \{L, R\}

图灵机 · 「机械地算」这件事的定义

艾伦·图灵生于伦敦。中学在舍伯恩，功课平平，只有数学与化学出挑；十七岁那年挚友克里斯托弗·莫科姆病死，此后他反复追问的问题变成了同一个：心智能不能脱离承载它的那团物质。1931 年入剑桥国王学院，1935 年二十二岁当选研究员。那年春天他听纽曼讲希尔伯特的判定问题——有没有一套机械的手续，能判定任一数学命题的真假。要回答「没有」，先得说清「机械」是什么。他的办法不是给「算法」下定义，而是去看一个人拿着纸笔算数时到底在做什么：一次只看纸上的一小块，凭眼前所见和自己有限的几种「心情」，决定写下什么、往哪边挪一格。把无关的东西全部去掉，剩下的就是一条纸带、一个读写头、一张有限的规则表。1936 年那篇《论可计算数》交出了这台机器，也顺手交出了另一件东西：既然每台机器都由一张有限的表决定，那就把表本身写到纸带上——机器的描述也是数据。通用机由此而来，那一年他二十四岁。

1938 年他在丘奇门下拿到博士学位，冯·诺依曼请他留下做助手，他回了英国。战时在布莱切利园八号棚屋主攻德国海军的恩尼格玛，Bombe 与序贯统计的「班」都出自他手；这段工作到 1970 年代才解密，同代人多半不知道他做过什么。战后他在国家物理实验室写下 ACE 的设计方案，那是把 1936 年那台通用机落到电路上的第一次认真尝试；1948 年转去曼彻斯特。1950 年《计算机器与智能》提出模仿游戏；1952 年《形态发生的化学基础》问的是另一件事——一团均匀的东西怎么会自己长出斑纹。也是 1952 年，他因与男性的关系被判「严重猥亵」，选择激素注射代替入狱，安全许可被吊销。1954 年 6 月 7 日他死于氰化物中毒，四十一岁，床头一个咬过一口的苹果，从未送检。2009 年英国政府正式道歉，2013 年获王室赦免，2017 年生效的「图灵法」为数万名同样被定罪的人平反。

Elliott & Fry 摄，1951-03-29 · Wikimedia Commons，公有领域

生平

1912
生于伦敦
父亲在印度供职，他与哥哥寄养在英国。中学功课平平，只有数学与化学出挑。
1930
克里斯托弗·莫科姆病死
十七岁失去挚友。此后他反复追问：心智能不能脱离承载它的那团物质。
1936
《论可计算数》
纸带、读写头、一张有限的规则表。「机械地算」第一次有了定义，判定问题随之落地。
1938
从普林斯顿回国
丘奇门下拿到博士学位；冯·诺依曼请他留下做助手，他回了英国。战争快来了。
1940
布莱切利园八号棚屋
Bombe 投入使用，专攻德国海军的恩尼格玛。这段工作到 1970 年代才解密。
1945
ACE 设计方案
国家物理实验室：把 1936 年那台通用机落到电路上——程序与数据存在同一处。
1950
模仿游戏
《计算机器与智能》：与其争论「机器能思考吗」，不如换成一个能操作的游戏。
1952
《形态发生的化学基础》
同年因与男性的关系被判「严重猥亵」，选择激素注射代替入狱，安全许可被吊销。
1954
卒于威姆斯洛
氰化物中毒，四十一岁。床头一个咬过的苹果，从未送检。2013 年获王室赦免。

展品厅

绝大多数展品都可以亲手把玩——这是本馆的立馆之本；少数以叙述为主的，做成故事展签。

镇馆之宝 · 亲手玩

一条纸带，一张规则表

他把「照着规则算」拆到不能再拆：读一格，写一格，挪一步。

\delta(q, s) = (q', s', d)

1935 年之前，「算法」是个人人在用、谁也没定义的词。希尔伯特问：有没有一套机械的手续，能判定任一数学命题的真假？要回答「没有」，得先说清「机械」是什么意思——否则你无从证明某件事机械地办不到。图灵的办法不是下定义，而是观察：一个人拿纸笔算数时，一次只看得见纸上的一小块，脑子里的状态也只有有限多种，他凭这两样决定写下什么、往哪边挪。把与算无关的东西全部剥掉，剩下的就是这台机器。此后「可计算」有了确切含义，而这个含义至今没被推翻：不管是量子计算机还是你手上这台，能算的一个不多、一个不少，差别只在快慢。

挑一台机器，一步步看它读、写、挪；或者放它自己跑到停机

111+11 → 11111。把加号改成一竖，再把末尾多出来的那一竖擦掉。

_________111+11____

q0读到 1 → 写 1，右移，转 q0

规则表——机器的全部，就这么多
状态＼读到	_	1	+
q0	—	1 R q0	1 R q1
q1	_ L q2	1 R q1	—
q2	—	_ L halt	—

第 0 步

读一格、写一格、挪一步、换个状态——这四件事之外，机器什么也不会。图灵想说的正是：所谓「机械地算」，拆到底就只有这些。

机器的描述，也是数据

把一台机器的规则表写到纸带上，另一台机器就能扮演它。

U(\langle M \rangle, x) = M(x)

1936 年那篇论文里真正改变世界的不是那台机器，是下一页。既然每台机器都由一张有限的规则表决定，那就把这张表编成一串符号，写到纸带上。于是存在一台通用机 U：喂给它「M 的编码 + M 的输入」，它就一步步扮演 M，结果与 M 自己跑一模一样。这一步把「造一台专门算某件事的机器」换成了「给同一台机器换一段纸带」——硬件与软件从此分家。1945 年图灵在 ACE 方案里把这件事落到电路上，冯·诺依曼那份 EDVAC 报告讲的是同一件事：程序与数据存在同一处，因为它们本来就是同一种东西。你正在用来读这行字的设备，就是那台 U。

专用机 M：本事焊死在自己的表里走了 0 步

_______1011____

通用机 U：只会读纸带上写着的规则走了 0 步

纸带前半段——M 的规则表，编成了一串字符

q0,0>0,R,q0q0,1>1,R,q0q0,_>_,L,q1q1,0>1,R,haltq1,1>0,L,q1q1,_>1,R,halt

纸带后半段——数据区

_______1011____

状态 q0，读到 1——正在编码区里挨条找规则

上排那台机器的本事焊死在它自己的规则表里。下排这台什么都不会，它只会一件事：读纸带前半段写着的规则，照做。U 的一步这里按「看一条规则」算——真正的通用机还要在纸带上一格格地爬，步数还要再大得多。

停机问题

没有哪个程序，能对所有程序判断出「它到底会不会停」。

\neg\exists H\ \forall \langle P, x \rangle:\ H(\langle P, x \rangle) = \mathrm{halts}(P, x)

假设有这样一台预言机 H：喂给它任意一段程序和输入，它总能在有限时间内回答「会停」或「不会停」。这台机器强得离谱——把哥德巴赫猜想写成「逐个搜索反例」的程序喂给它，它一答，猜想当场就解决了。图灵证明它不存在，办法是拿它造一台专门与它作对的机器 D：D 拿到一段程序 p，先问 H「p 拿自己当输入会不会停」；H 说会停，D 就进死循环；H 说不停，D 就立刻停下。然后把 D 喂给 D 自己——两条路都自相矛盾。所以 H 不存在。这同时答完了希尔伯特的判定问题：若真有一套判定手续，就能拿它造出 H。用的还是康托尔那一招，只是对角线画在了程序上。

预言机 H姑且当它存在

喂给它一段程序和一份输入，它总能在有限时间里回答：这段程序会不会停下来。

注意 H 有多强：只要它存在，一大批悬而未决的猜想都能被它一句话了结——把「逐个搜索反例」的程序喂进去就行。图灵证明它不存在的办法，是拿它造一台专门与它作对的机器。

字母永远不会是它自己

恩尼格玛最得意的那处设计，恰好是它唯一的破绽。

恩尼格玛每按下一个键，电流穿过三只转子撞上反射器，再沿另一条路折回来。反射器保证了加密与解密是同一套动作——同样的设置，把密文打进去就出明文，用起来极方便。代价是一条谁也改不掉的性质——没有哪个字母会被加密成它自己。这条性质看着无害，却是整台机器的死穴。拿一段猜得到的明文——德军电文里几乎必然出现的 OBERKOMMANDODERWEHRMACHT——沿着密文滑过去，凡是有任何一列字母与自己重合的位置，一律排除，一次就能砍掉一多半。图灵的 Bombe 干的正是这件事的自动化：它不去寻找正确的设置，而去证伪错误的设置，一天证伪几十万个，剩下的交给人。

这个位置活下来了二十四列没有一列撞上自己。还得靠 Bombe 逐个试才知道是不是它。

对齐位置 0

30 个位置，只凭「没有哪个字母会被加密成它自己」这一条，就排掉了 18 个，只剩 12 个还站着。一个 24 字母的猜词，整段躲开自己的概率约 (25/26)²⁴ ≈ 0.39——剩下的正是这个比例。恩尼格玛最得意的那处设计，是它唯一的破绽。

斑马为什么有条纹

1952 年他问：一团均匀的东西，怎么会自己长出花样？

\partial_t u = D_u \nabla^2 u + f(u,v), \quad \partial_t v = D_v \nabla^2 v + g(u,v)

这是他生前最后一篇论文，也是他自己最看重的一篇。受精卵是近乎均匀的一团，长出来的却是有斑有纹的动物——花样从哪儿来？他给的机制只要两样东西：一种物质既促进自己也促进它的抑制剂，而抑制剂扩散得更快。这两条凑在一起，均匀态就是不稳定的：任何一点微小的涨落都会被放大，长成间距固定的斑或纹，间距由两个扩散系数定，与胚胎多大无关。他用曼彻斯特那台刚能用的机器算了这套方程，那大概是史上最早的一批计算机数值实验之一。今天在斑马鱼的色素细胞、小鼠上腭的皱褶、沙丘与天上的云街里，都验出了同一套机制。

F = 0.0367　k = 0.0649

斑点长到一定大小就一分为二，再各自长大——豹与瓢虫身上的那种。三种花样出自同一套方程，差别只在那两个参数。图灵 1952 年给的是失稳的机制与花纹间距的公式；这里跑的是后来被用得最多的一个具体实例（格雷—斯科特方程），属于同一类。他当年是用曼彻斯特那台刚能开机的机器算的——那大概是史上最早的一批计算机数值实验。

「机器能思考吗」——他把问题换掉了

他没有回答那个问题，他换了一个能操作的问法。

1950 年那篇《计算机器与智能》开门见山：「机器能思考吗」这个问题毫无意义，因为「机器」和「思考」都没有定义，照字面讨论只会沦为统计人们平时怎么用词。于是他把它换掉——一间屋里坐着一个人和一台机器，你隔着打字机同时与两者交谈；若你分不出哪个是哪个，那么坚持「它不能思考」就得另外给出理由。论文后半他一口气预先回应了九条反驳：神学的、「后果太可怕所以不能是真的」的鸵鸟式的、以及最难缠的那条——哥德尔的不完备定理。他承认那条定理确实框住了机器，随即补上一句：凭什么认定人的心智不受同一条框？他预测二十世纪末的机器能在五分钟对话里骗过三成的人。七十多年过去，这个游戏仍然叫图灵测试，而它究竟测出了什么，仍然在吵。

故事展签故事展签：一个问题被换掉之后，一门学科才有了可以开工的地方。

传承

他的工作没有留在十八世纪——每条链的终点，都是你今天正在使用的东西。

图灵机⟶「可计算」有了定义⟶可计算性、复杂性与整个计算机科学

通用图灵机⟶ACE 与 EDVAC 的存储程序式数字计算机⟶硬件与软件分家

Bombe 与恩尼格玛⟶序贯分析与现代密码分析⟶加密与信息安全

模仿游戏⟶人工智能这门学科的开场⟶机器学习与今天的对话系统

反应扩散与图灵斑图⟶形态发生的数学模型⟶发育生物学里的图案形成

语录

「我们只能看到前方很短的一段距离，但我们能看到那里有大量的事情亟待完成。」
—— 《计算机器与智能》结语，《心灵》第 59 卷，1950

「如果指望一台机器永不犯错，那它也就不可能有智能。」
—— 1947 年 2 月 20 日伦敦数学会讲演，收于《图灵文集·机械智能》1992

「科学是一个微分方程。宗教是一个边界条件。」
—— 写给罗宾·甘迪的便条，见霍奇斯《艾伦·图灵：谜》1983