01 / THE MACHINE ON PAPER
计算机还不存在,“计算”凭什么先被定义?
在一九二八年的国际数学家大会上,年过六旬的希尔伯特重申了一个宏大的愿望:是否存在一套机械程序,输入任何数学命题,都能自动判定它真还是假?“机械”二字意味着不需要灵感、不需要天才,任何人照着执行就能得到答案。可奇怪的是,当时竟没有人能说清——“机械地算”究竟是什么意思?
问题难就难在:要回答“这样的程序存在吗”,得先把“程序”变成一个能被数学讨论的对象。1936 年,24 岁的剑桥国王学院研究员艾伦·图灵交出了答案——他定义了一台只存在于纸上的机器:一条无限长的纸带、一个读写头、有限个状态、一张规则表。凡这台机器能算出的,就叫可计算;它算不出的,任何“机械程序”都算不出。
1936 年发表的《论可计算数及其在判定问题上的应用》在同一篇文章里完成了两件事:先用图灵机精确定义“可计算”,再证明一道看似工程问题的题目——停机问题——永远无解,从而给希尔伯特的判定问题盖棺定论。写论文的人,就是艾伦·图灵。
这台机器在 1936 年一台也造不出来,它完全由定义构成。可十五年后,第一台存储程序计算机开始运转,它的每一步依然在执行“读写头 + 规则表”的逻辑;今天你口袋里的手机,在数学家眼里仍是这台纸上机器的后代。要理解它为什么有这么大的力量,最好的办法是亲手驱动它一次。
怎么就构成“计算”?图灵机 ↗02 / 一个反证假设判定器 H 存在,
为什么必然自相矛盾?停机问题 ↗03 / 一段遗产从“模仿游戏”出发,
走出了怎样的世界?身后遗产 ↗
实验 A 里的机器每一步只做一件小事:读一个格子,按一条规则改写,左移或右移。你只需要“照章办事”的直觉就能跟着跑;实验 B 的推理只需要看懂一种矛盾——从假设 A 出发,推出了非 A。
02 / A LIFE HALF IN SECRET
一半在讲台与纸页上,一半在保密档案里的四十二年
图灵于 1912 年 6 月 23 日出生在伦敦麦达维尔。父亲任职于印度文官系统,父母长年旅居印度,幼年的图灵与哥哥被托付给一对退役军官夫妇照看。1926 年他进入舍伯恩寄宿学校——据传记记载,开学当天恰逢全国大罢工、公共交通停摆,13 岁的他独自骑车约 60 英里从南安普顿赶到学校报到。他在学校里数学天赋早显,却常被更受校方重视的古典科目拖住总成绩。
1931 年他进入剑桥大学国王学院,1935 年凭一篇概率论论文当选研究员,年仅 22 岁;次年春天,《论可计算数》问世。1936—1938 年他在普林斯顿跟随逻辑学家丘奇攻读博士;回国后不久,二战爆发。1939 年秋起,图灵进入布莱切利园的政府密码学校:波兰数学家雷耶夫斯基、鲁日茨基与齐加尔斯基早在 1932 年就用数学方法破解了 Enigma 的内部结构,1939 年 7 月把全部成果移交英法;图灵据此设计出英国 Bombe 密码分析机(威尔士曼随后补上关键的“对角线板”改进),并领导负责海军 Enigma 的 8 号小屋。这段工作保密数十年,直到战后档案陆续解密才为人所知。1945 年他转到国家物理实验室主持 ACE 计算机设计,因行政掣肘进展缓慢,1948 年转赴曼彻斯特大学,为早期存储程序计算机编写程序与手册;1950 年发表《计算机器与智能》。
- 6 月 23 日出生
父亲任职于印度文官系统,父母长年驻印,幼年的图灵与兄长由寄养家庭照看。
- 进入寄宿学校
据传记记载,开学当天恰逢全国大罢工,他独自骑车约 60 英里赶到学校;数学天赋早显。
- 22 岁当选研究员
论文研究概率论中的中心极限定理;次年春《论可计算数》完成。
- 《论可计算数》发表
用一台纸上的机器定义“可计算”,并在同一篇论文里证明停机问题不可判定,回应希尔伯特的判定问题。
- 丘奇门下攻读博士
与丘奇各自独立抵达同一结论,合称丘奇—图灵论题;1938 年获博士学位后回国。
- 破译 Enigma 与 Bombe
在波兰数学家的开创性工作基础上主导英国 Bombe 设计,领导 8 号小屋破解海军 Enigma;工作保密数十年。
- ACE 受阻,转赴曼彻斯特
在国家物理实验室主持 ACE 设计,1948 年离开;在曼彻斯特为早期存储程序计算机编写程序与手册,1950 年提出“模仿游戏”。
- 定罪、化学“治疗”与去世
1952 年因同性恋被定罪(当时英国法律视为犯罪);1954 年 6 月 7 日氰化物中毒去世,41 岁,死因研讯裁定自杀、家人存疑。
布莱切利园的工作保密数十年,相关叙述以战后解密档案与专业史料为准;“骑车 60 英里报到”一类细节出自霍奇斯等人的传记,按传记记载转述。图灵之死:官方死因研讯裁定自杀,家人则认为更可能与实验用氰化物的意外有关——两种说法并存,本页如实保留。1952 年定罪依据的是当时英国法律;后来的道歉、赦免与纪念属于身后之事,本页把它们与生前分开陈述。
03 / A MACHINE ANYONE CAN DRIVE
纸带、读写头、规则表:一台谁也没见过的机器如何算题?
图灵机的全部工作方式可以写在一张便签上:每一步,机器根据当前状态和读写头下的符号查规则表,然后写一个符号、左移或右移一格、进入新状态。没有别的花样。下面这三台小小的机器共用这套引擎:一台做二进制加一,一台连续计数,一台检查回文——它们都由几条到十几条规则构成。
实验 A / 亲手驱动一台图灵机
先用滑块选一条程序,再按“单步执行”逐条跑规则,或按“自动执行”让它自己跑。观察读写头如何移动、进位如何在纸带上连锁传播。
三条程序共用同一台引擎:纸带由格子组成(▢ 为空白,x 为已划掉的符号),读写头每步按“(状态,读到)→(写入,移动,新状态)”执行一条规则。“二进制加一”从最低位开始:1011 + 1 = 1100,而 111 + 1 = 1000 会进到新的最高位;“二进制计数”把加一连续执行 10 轮;“回文检查”首尾配对、划掉后向中间推进,0110 判定为回文。规则表已在本页写死并逐步执行,全部计算在浏览器本地完成。
论文标题里的“可计算数”指小数展开能被某台图灵机逐位打印出来的数:整数、根号 2、π 都在其中——前提只是存在一台能不停算下去的机器。而真正震动数学界的,是论文的后半部分:连“这台机器自己会不会停机”都无法判定(下一章)。普林斯顿两年(1936—1938),图灵在逻辑学家丘奇门下完成博士论文;“凡直觉上可计算的,都等价于图灵机可计算的”——这条今天称为丘奇—图灵论题的原则,是整个计算机科学的地基。
在图灵之前,“机械地算”只有直觉;在此之后,它有了精确的数学对象。“哪些问题原则上算不了”由此变成可以证明的定理——下一章的停机问题就是第一个。
哥德尔 1931 年证明:足够强的公理系统里存在既真又不可证的命题。图灵把“真 / 假”换成“停 / 不停”,用更具体的对象得到不可判定性——两条路径在数学上深度等价,常被视作同一枚硬币的两面。
04 / WHY NO DECIDER CAN EXIST
为什么“永远正确”的停机判定器不可能存在?
把问题问得再具体一点:给你一段程序 P 和一个输入 I,能否写出一个判定器 H(P, I)——它自己永远停机,且永远正确地回答“P 处理 I 时会不会停机”?听起来只差把代码写完:直接模拟 P 不就行了?可如果 P 恰好不停,模拟就永远不会结束——你只是把“不知道”原封不动地传给了未来。要一劳永逸地回答,必须有比“跑一遍”更聪明的办法。图灵证明:这样的办法不存在。
实验 B / 停机问题为什么无解
拖动“推演阶段”滑块,分四步走完对角构造;也可以换 H 的判定方向——两个方向都会在阶段 4 爆发矛盾。
对角构造分四步:假设 H 存在(阶段 1)→ 用 H 定义程序 Q(阶段 2)→ 把 Q 喂给 H,得到判定(阶段 3,橙色箭头)→ 沿 Q 的定义推演,结论与 H 的回答相反(阶段 4,矛盾爆发)。两个方向的判定都导致矛盾,因此“永远正确且总会停机的判定器”不存在。图示为逻辑推演,不涉及真实程序执行。
H 判 Q“会停”→ 按定义 Q 进入死循环 → Q 实际不停机;H 判 Q“不停”→ 按定义 Q 立刻停机 → Q 实际会停机。无论回答哪个方向,H 都错——而 H 的定义要求它永远正确。矛盾不在程序里,在假设本身。
许多实际判定都能归约到停机问题:程序会不会崩溃、两段代码是否等价、这段代码有没有恶意行为——通用的判定算法一律不存在。工程上的杀毒与静态分析之所以只能给出“近似答案”,根子就在这里。
矛盾一旦成立,推倒的是一大片:1936 年论文标题里的“判定问题上的应用”正是最后一步——若存在判定一切数学命题的机械程序,停机问题就能被它顺手解决;既然停机不可判定,希尔伯特的期望便落了空。哥德尔 1931 年的“不完备”与图灵 1936 年的“不可判定”,就此接上同一根接力棒:数学里不仅有解不出的题,还有被证明“不可能有通用解法”的题。
05 / WHAT GREW FROM HIS PAGES
从一台纸上的机器,到 50 英镑纸币上的人像
图灵机的思想落地比想象中快:1945—1947 年他在国家物理实验室主持 ACE 计划,因行政掣肘未能完成;1948 年转赴曼彻斯特大学,为早期存储程序计算机编写程序与手册。1950 年,他在哲学期刊《心》(Mind)上发表《计算机器与智能》,提出“模仿游戏”——若提问者隔着文字交谈分不清对面是机器还是人,就没什么理由否认机器在“思考”,这就是今天通称的图灵测试。1951 年他当选皇家学会会士;1952 年转向数学生物学,用反应—扩散方程解释动物皮毛的斑纹,至今仍是活跃的研究方向。计算机学界的最高荣誉——ACM 图灵奖——自 1966 年起以他的名字命名。
他人生的最后几年却与这些荣誉无关:1952 年,图灵因同性恋被依照当时英国法律定罪,接受化学“治疗”,安全许可被吊销;1954 年 6 月 7 日,他在威姆斯洛家中因氰化物中毒去世,年仅 41 岁——官方死因研讯裁定为自杀,家人对此始终存疑。平反来得太迟:2009 年英国政府正式道歉;2013 年女王予以赦免;2017 年立法赦免数万名同类历史定罪者;2021 年 6 月 23 日——他的生日——图灵头像登上 50 英镑纸币。
在实验 A 里把“加一”“计数”“回文”各跑一遍,注意一条规则如何在纸带上引起连锁反应。
试着给图灵机设计“二进制乘 2”(左移一位补 0)的规则,再回到实验 A 验证你的直觉。
丘奇—图灵论题、递归函数与 Rice 定理是下一步;把本页实验 B 与哥德尔不完备定理对照着读。
《论可计算数》(1936)与《计算机器与智能》(1950)均有公开译本与注释版;剑桥国王学院的图灵数字档案可在线查阅原稿。
图灵留下的不是一个答案,而是一台谁也没见过的机器——先用思想造出工具,再等世界把它实现。
06 / SOURCES & FURTHER READING
史料与进一步阅读
生平与著作年代以数学史专业资料与战后解密档案为准;布莱切利园部分只保留多源一致的内容,不采信无从核实的传闻。两组互动实验是现代教学模型:图灵机按本页写定的规则表在浏览器本地逐条执行,停机问题演示为逻辑推演,均不上传数据。
JACKNOTE / MATH · 2026 年 11 月 · 文章、图表与互动实验原创编写;数字模拟均在浏览器本地完成,不上传数据。