跳转到内容
Jason's Study

Turing 1936 可计算性

是什么

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

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

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

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

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

为什么重要

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

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

核心要点

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

  1. 图灵机长什么样：一个有限状态控制器 + 一条无限长的纸带 + 一张5 元组规则表。每条规则的形状是「现在状态 q + 读到符号 a → 写新符号 a’ + 移动方向（左/右）+ 切到新状态 q’」。机器从初始状态出发，按规则走，碰到接受状态就停。就这么简单。

  2. 通用图灵机（UTM）：一台机器 U，输入是「另一台机器 M 的描述」+「M 的输入 w」，输出和 M(w) 一模一样。关键洞察：M 的描述本身是有限符号——可以塞进纸带当数据。这就是”程序即数据”的最早形态。

  3. 停机问题不可判定：不存在一台图灵机 H，对任何「机器 M + 输入 w」都能正确回答”M 在 w 上会不会停”。证明用对角线法：假设 H 存在，构造 D = “如果 H 说我会停，我就死循环；否则就停”，然后让 D 读自己——两种情况都矛盾，所以 H 不存在。

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

实践案例

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

任务：判断输入纸带是不是 “abab”，是就停在接受状态。

状态表（5 个状态 q0~q4，q4 是接受）：

当前状态读到写方向切到
q0aaRq1
q1bbRq2
q2aaRq3
q3bbRq4

读到任何不符的字符就直接拒绝。这就是一台完整的图灵机——你看，所有”复杂的计算机”本质都是这种结构的扩展。

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

把一台图灵机 M 的状态表用 “01010110…” 这种字符串编码（每条规则按固定格式写下来），就能塞进另一台机器 U 的纸带当输入。U 的程序是”读这段编码，模拟 M 的行为”。

这正是你电脑里发生的事：

  • CPU = 通用图灵机 U
  • 你写的程序（编译后的二进制） = M 的描述 ⟨M⟩
  • 程序输入 = w
  • CPU 执行程序 = U(⟨M⟩, w)

冯诺依曼 1945 年的 EDVAC 报告里直接致敬了这个想法。

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

假设有个万能死循环检测器 H(M, w)：M 在 w 上停就返回 1，不停返回 0。

我写一个变态程序 D：

D(M):
  if H(M, M) == 1:    # 如果"M 读自己"会停
    死循环
  else:
    立即停

现在问：D 读自己（D(D)）会不会停？

  • 如果 D(D) 会停 → 按 D 的定义走”立即停”分支 → 但要走这个分支必须 H(D, D) = 0，即 D(D) 不停 → 矛盾
  • 如果 D(D) 不停 → 按 D 的定义走”死循环”分支 → 但要走这个分支必须 H(D, D) = 1，即 D(D) 停 → 矛盾

两种情况都矛盾，所以 H 不存在。这就是停机问题不可判定。

踩过的坑

  1. 图灵机是慢的？错——图灵机不是真实硬件，没”快慢”概念。它是可计算性的定义工具，不是性能模型。算法书里的 “O(n)” 用的是 RAM 模型，不是 TM 步数，两者别混。

  2. 图灵完备一定好？错——图灵完备意味着”能算一切可计算函数”，但也继承了停机问题不可判定。Datalog / 标准 SQL 故意不图灵完备，换来了”查询必停”的可分析性。设计 DSL 时这是关键 trade-off。

  3. 量子计算能突破？错——量子图灵机在可计算性上和经典图灵机等价。能算的东西完全相同，只是某些问题更快（指数级加速）。停机问题在量子计算机上仍然不可判定。

  4. 现代 CPU 是图灵机？严格说错——你的电脑只有有限内存，本质上是有限状态自动机或线性有界自动机。但抽象上等价——理论分析时假装内存无限是有用的简化。

适用 vs 不适用场景

用图灵机思维分析：

  • 想知道某个问题”是否原则上可解”——可计算性问题
  • 设计编程语言 / DSL 时判断表达力——是否需要图灵完备
  • 研究算法复杂性的下界——P / NP / PSPACE 等都建立在 TM 上
  • 理解”为什么 IDE 不能 100% 检测死循环”

不要用图灵机思维分析：

  • 真实硬件的性能优化——用 RAM 模型 / cache profiler
  • 安全漏洞分析（如 Spectre / Meltdown）——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 的”程序存储”思想来自通用图灵机。

学到什么

  1. 形式化是革命的前提——把”机械过程”这个直觉概念翻译成数学对象，才能证明”某些东西原则上不可机械化”。这是 20 世纪计算机科学的奠基操作。

  2. 自指 + 对角线 = 强力武器——Cantor 的实数不可数性、Russell 悖论、godel-1931 不完备、Halting Problem 不可判定，都是同一招。学会这一招你能看穿很多”原则上不可能”的证明。

  3. 理论上的不可能 ≠ 工程上的无用——停机问题不可判定，不代表 IDE 不能检测大部分死循环。理论给 worst-case 保证；工程做 average-case 启发式。两者不矛盾。

  4. 抽象的层次很重要——可计算性用 TM，复杂性用 RAM 模型，性能优化用 cache profiler。同一段代码在不同层次有不同模型。学习时分清”现在问的是哪一层”。

延伸阅读

  • Sipser, Introduction to the Theory of Computation —— 标准教材，TM 章节极清晰，建议从这里入门
  • Petzold, The Annotated Turing —— 逐行解读 1936 原论文，配着原文读非常顺
  • Davis, The Universal Computer —— 历史脉络（Hilbert → Gödel → Turing → 冯诺依曼），不需要数学背景
  • Hofstadter, Gödel, Escher, Bach —— 把不完备 / 自指 / 计算用文学方式串起来
  • 自己写：用 Python 30 行内实现一个 TM 模拟器，跑一个识别 “0ⁿ1ⁿ” 的小机器，比读 10 篇论文更快理解

关联

  • 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 —— 通用图灵机的工程实现，现代计算机的架构起点

反向链接