Turing 1936 可计算性

待复核

是什么

Turing 1936 这篇论文做了一件事：给”机器能算什么”画了一条数学边界。

日常类比：想象一个只会按表格走格子的机器人——它面前有一条长长的纸带（一格一格写着符号），它能往左走一步、往右走一步、读当前格子的符号、改写当前格子的符号。它脑子里只有有限张”卡片”（状态），每张卡片上写着”看到什么符号就做什么动作 + 切到哪张卡片”。

这个看起来弱到不行的机器人，就是 Turing 定义的”图灵机”。它能算的东西，正好就是”机械过程能算的所有东西”。

更狠的是：Turing 还构造了一个”超级机器人”——它能读另一台机器人的指令表当作自己的输入，然后模仿那台机器人。这就是通用图灵机（CPU 的数学祖宗）。

最后他证明：有一个具体问题，所有这种机器人都解不了——叫停机问题。

为什么重要

不理解 Turing 1936，下面这些事都没法解释：

为什么 CPU 是 CPU——它的数学定义就是”通用图灵机”，所有现代电脑都是它的物理实现
为什么 IDE / linter / 死循环检测器永远做不到 100% 准确——这不是工程不够好，是数学上的不可能
为什么”程序”和”数据”在内存里长得一模一样（冯诺依曼架构的灵感来源）
为什么”图灵完备”是个需要斟酌的标签——它意味着”什么都能算”也意味着”什么都分析不准”
为什么 lambda-calculus 和图灵机被并列——它们是同一件事的两种说法

核心要点

理解这篇论文，抓住三块：

图灵机长什么样：一个有限状态控制器 + 一条无限长的纸带 + 一张5 元组规则表。每条规则：「状态 q + 读符号 a → 写 a’ + 左/右移 + 新状态 q’」。下文用现代教材的「接受就停」讲法（Sipser 风格）；原文更侧重打印可计算实数的数字，骨架同一台机器。
通用图灵机（UTM）：一台机器 U，输入是「另一台机器 M 的描述」+「M 的输入 w」，输出和 M(w) 一模一样。关键洞察：M 的描述本身是有限符号——可以塞进纸带当数据。这就是”程序即数据”的最早形态。
停机问题不可判定：不存在一台图灵机 H，对任何「机器 M + 输入 w」都能正确回答”M 在 w 上会不会停”。证明用对角线法：假设 H 存在，构造 D = “如果 H 说我会停，我就死循环；否则就停”，然后让 D 读自己——两种情况都矛盾，所以 H 不存在。

这三块加起来，顺手摧毁了 Hilbert 的”机械数学判定机”梦想（godel-1931 已经摧毁了”完备性”，Turing 摧毁了最后一根柱子”可判定性”）。

实践案例

案例 1：写一个最小图灵机识别 “abab”

任务：纸带是 “abab” 就进接受态 q4；读到不符符号进拒绝态 qrej。

当前状态	读到	写	方向	切到
q0	a	a	R	q1
q1	b	b	R	q2
q2	a	a	R	q3
q3	b	b	R	q4
任一 qi	不符/空白	原样	R	qrej

逐步走格子（输入 abab）：

q0 读 a → 右移，切 q1
q1 读 b → 右移，切 q2
q2 读 a → 右移，切 q3
q3 读 b → 右移，切 q4（接受，停）

若第 2 步读到 a（输入是 aab...），直接切 qrej。整台机器就是一张表。

案例 2：通用图灵机 = 现代 CPU 的祖先

三步跟做：

编码：把 M 的每条 5 元组写成固定串，例如 q0,a→a,R,q1 拼成 ⟨M⟩
U 读描述：纸带上放 ⟨M⟩#w，U 先解析出「当前状态 + 当前符号」对应哪条规则
模拟一步：按那条规则改写 w 区、移动虚拟磁头、更新当前状态；循环直到 M 停

U(desc, w):
  state, head = start(desc), 0
  while state not in {accept, reject}:
    rule = lookup(desc, state, w[head])
    w[head], head, state = rule.write, head+rule.dir, rule.next

对照：CPU≈U，二进制程序≈⟨M⟩，输入≈w。1945 年 EDVAC 的程序存储思想，与通用图灵机一脉相承。

案例 3：停机问题的对角线证明（简化版）

假设有万能死循环检测器 H(M, w)：停返回 1，不停返回 0。写变态程序 D：

D(M):
  if H(M, M) == 1: 死循环
  else: 立即停

问 D(D) 会不会停？

若会停 → 须走「立即停」→ 须 H(D,D)=0 → 即不停 → 矛盾
若不停 → 须走「死循环」→ 须 H(D,D)=1 → 即会停 → 矛盾

所以 H 不存在。

踩过的坑

图灵机是慢的？错——图灵机不是真实硬件，没”快慢”概念。它是可计算性的定义工具，不是性能模型。算法书里的 “O(n)” 用的是 RAM 模型，不是 TM 步数，两者别混。
图灵完备一定好？错——图灵完备意味着”能算一切可计算函数”，但也继承了停机问题不可判定。Datalog / 标准 SQL 故意不图灵完备，换来了”查询必停”的可分析性。设计 DSL 时这是关键 trade-off。
量子计算能突破？错——量子图灵机在可计算性上和经典图灵机等价。能算的东西完全相同，只是某些问题更快（指数级加速）。停机问题在量子计算机上仍然不可判定。
现代 CPU 是图灵机？严格说错——你的电脑只有有限内存，本质上是有限状态自动机或线性有界自动机。但抽象上等价——理论分析时假装内存无限是有用的简化。

适用 vs 不适用场景

用图灵机思维分析：

问”原则上能不能算完”——可判定性（停机、等价性等）
设计 DSL 时权衡表达力 vs 可分析性——要不要图灵完备
理解”为什么 IDE 不能 100% 检测死循环”
入门复杂性时认清底座——P/NP 建立在 TM 上，但那是多快，不是能不能

不要用图灵机思维分析：

真实硬件性能——用 RAM / cache profiler（别拿 TM 步数当 O 记号）
Spectre 类微架构漏洞——TM 没有推测执行
并发 / 分布式——用 actor / CSP / 共享内存模型
Web 前端状态——有限状态机就够，不必上 TM

历史小故事（可跳过）

1900 年：Hilbert 在巴黎数学家大会上提了 23 个问题，第 2 个是”算术系统的相容性”。后来发展成 Hilbert 计划：完备性 + 相容性 + 可判定性。
1931 年：godel-1931 干掉了完备性——任何包含算术的形式系统都有”既证不出也反不出”的命题。
1936 年初：Hilbert 计划只剩”可判定性”一根柱子。
1936 年 5 月：23 岁的 Turing（剑桥研究生）递交这篇论文，把最后一根柱子也推倒了。同年 4 月，普林斯顿的 Alonzo Church 用 lambda-calculus 独立证明了等价结果——但 Turing 的形式化更直观、更接近物理机器，最终成为标准。
1936 年秋：Turing 去普林斯顿做 Church 的博士生，两人一起把”图灵机 = λ-演算 = 递归函数”三种定义证明了完全等价。这就是 Church-Turing 论题。
1945 年：EDVAC 报告把”程序当数据存进内存”写成工程方案，与通用图灵机同一脉络。

学到什么

形式化是革命的前提——把”机械过程”这个直觉概念翻译成数学对象，才能证明”某些东西原则上不可机械化”。这是 20 世纪计算机科学的奠基操作。
自指 + 对角线 = 强力武器——Cantor 的实数不可数性、Russell 悖论、godel-1931 不完备、Halting Problem 不可判定，都是同一招。学会这一招你能看穿很多”原则上不可能”的证明。
理论上的不可能 ≠ 工程上的无用——停机问题不可判定，不代表 IDE 不能检测大部分死循环。理论给 worst-case 保证；工程做 average-case 启发式。两者不矛盾。
抽象的层次很重要——可计算性用 TM，复杂性用 RAM 模型，性能优化用 cache profiler。同一段代码在不同层次有不同模型。学习时分清”现在问的是哪一层”。

关联

lambda-calculus —— 同年 Church 给出的等价定义；图灵机和 λ-演算是”可计算性”的两条定义路径
godel-1931 —— 不完备定理；和图灵 1936 一起摧毁了 Hilbert 形式主义计划
mccarthy-lisp —— 第一个把 λ-演算工业化的编程语言
hindley-milner —— 给 λ-演算加类型系统的方法，TypeScript / OCaml / Haskell 的根基
cook-1971 —— 把可计算性细化为”多快能算”，开启 NP-completeness 时代
chomsky-1956 —— 形式语言层级（FSA ⊊ PDA ⊊ LBA ⊊ TM）
von-neumann-edvac —— 通用图灵机的工程实现，现代计算机的架构起点

反向链接

algol-60 —— ALGOL 60 — BNF 与块结构
belady-1966 —— Belady 1966 — 缓存替换的理论最优与 FIFO 异常
cook-levin —— Cook-Levin 定理 — NP-完全性的诞生
diffie-hellman —— Diffie-Hellman 密钥交换
diffie-hellman-1976 —— New Directions 1976 — 给协议世界写下公钥宪法
dijkstra-1965 —— Dijkstra 1965 — N 个进程怎么轮流上厕所而且谁也别卡死
dijkstra-goto —— Dijkstra 1968 — Go To Statement Considered Harmful
dijkstra-shortest-path —— Dijkstra 最短路径 — 一杯咖啡时间想出来的贪心算法
donar-2010 —— DONAR 2010 — 把 DNS 全球调度写成一道可解的优化题
feynman-simulating-physics-1982 —— Feynman 1982 — 量子计算从模拟物理开始
fielding-rest-2000 —— Fielding 2000 — 用约束推导法把 Web 的成功讲成了一门方法
godel-1931 —— Gödel 1931 — 不完备性定理
hamming-1950 —— Hamming 纠错码
huffman-1952 —— Huffman 编码
kajiya-1986-rendering-equation —— Kajiya 渲染方程 — 把所有渲染算法统一成一个积分方程
karp-21 —— Karp 21 — 21 个 NP-完全问题
knuth-taocp —— Knuth TAOCP — 计算机程序设计艺术
lambda-calculus —— λ-演算 — 用三条规则表达所有可计算函数
minhash-broder-1997 —— MinHash — 用最小哈希值估算两个集合的重叠度
neumann-2015-large-joins —— Adaptive Optimization of Very Large Join Queries — 100 张表也敢精确求解
polar-codes-2009 —— Polar 极化码 — 把好坏不一的信道整成”完美/全错”两组
prolog-colmerauer —— Prolog 的诞生 — 让逻辑式子直接当程序跑
rest-fielding-2000 —— REST — Fielding 2000 给 Web API 写下的设计宪法
rsa —— RSA 公钥密码
scott-strachey-denotational —— Scott-Strachey 指称语义 — 给程序找一个独立于实现的数学含义
sel4-2009 —— seL4 — 第一个被数学证明”代码和规范完全一致”的操作系统内核
shannon-1948 —— Shannon 1948 — 信息论的诞生
shor-1994 —— Shor 1994 — 量子傅里叶变换把分解整数变成找周期
simhash-charikar-2002 —— SimHash — 用随机超平面把余弦相似度变成汉明距离
smalltalk-80 —— Smalltalk-80
wadler-prettier —— Wadler Prettier — 函数式优雅打印器
zk-snark —— zk-SNARK 零知识证明