停机问题

概述

停机问题（Halting Problem）是阿兰·图灵于 1936 年证明的第一个不可判定问题：不存在一个通用算法，能判定任意给定程序在任意输入上是否最终停止运行——这是数学上的必然，而非技术上的局限。

关键内容

问题陈述

是否存在一台图灵机 H(M, w)，使得对任意图灵机 M 和输入 w：若 M 在 w 上停机则输出"是"，否则输出"否"，且 H 自身总是停机？

回答：不存在。

对角化证明

Turing 采用反证法 + Cantor 对角化思想：

步骤 1：假设 H 存在。

步骤 2：构造矛盾机器 D

D(M) = {
  调用 H(M, M)
  if H 回答"是"（M 在自身输入上停机）:
    D 永不停机（故意进入无限循环）
  if H 回答"否"（M 在自身输入上不停机）:
    D 立即停机
}

步骤 3：运行 D(D)，产生悖论 - 若 D(D) 停机 → H(D,D) 回答"是" → D 故意不停 → 矛盾 - 若 D(D) 不停机 → H(D,D) 回答"否" → D 立即停 → 矛盾

两种情况均矛盾，故 H 不可能存在。

对角化的本质：D 被构造为"与 H 对每台机器的判断反着来"，类比 Cantor 构造与所有已列出实数都不同的新实数——自指引发不可解的矛盾。

与判定问题的关系

Turing 进一步证明：若判定问题（Hilbert 的 Entscheidungsproblem）可解，则停机问题也可判定。但停机问题不可判定，∴ 判定问题也不可判定，否定回答了 Hilbert 1928 年的提问。

归约（Reduction）技术

停机问题是"归约"证明的标准起点：要证明问题 A 不可判定，只需证明"若 A 可判定，则停机问题也可判定"：

已证明通过归约不可判定的问题举例： - Rice 定理（1953）：图灵机的所有非平凡语义性质均不可判定 - Post 对应问题（1946） - Hilbert 第十问题：整系数多项式方程是否有整数解（Matiyasevich，1970） - 字问题（word problem for groups）（Novikov，1955）

软件工程中的影响

停机问题的不可判定性直接约束了软件工程能做什么：

愿景	不可能的原因
完美的程序验证器（检查所有 bug）	等价于判定停机问题
完美的编译器死代码消除	判定代码是否可达 = 停机问题变形
完美的恶意软件检测器	语义性质不可判定（Rice 定理）

实践意义：任何静态分析工具都必须在精确性（soundness）和完备性（completeness）之间取舍——要么漏报，要么误报。没有第三条路。

来源

raw/books/计算机科学/01-turing-on-computable-numbers.md
01-turing-on-computable-numbers — 详细分析