图灵机、可计算性与停机问题

计算的数学定义、它的能力边界，以及有些良定义的问题没有算法——停机问题与 Rice 定理。本章是计算模型的严格版本。

图灵机

图灵机：七元组 $(Q, \Sigma, \Gamma, \delta, q_0, B, F)$——有限状态、输入/纸带字母表、转移函数 $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$（读、写、左/右移）、停机状态。无限纸带可随机读写——与一切现代计算机等价（忽略资源）。

变体都等价：多带图灵机（多项式加速）、非确定性图灵机（时间上界指数）、λ 演算、寄存器机器——Church–Turing 论题：一切"有效可计算"的函数都能被图灵机计算；这是论题而非定理（直觉概念无法形式化证明），靠反复确证（→ 计算模型）。

通用图灵机与可枚举

通用图灵机（UTM）：输入是"另一台图灵机的编码 + 它的输入"，输出是模拟结果——存在一台机器能模拟任何机器。"程序是数据"的数学表述：操作系统、编译器、解释器都活在这一步。

语言类：

• 递归可枚举（RE）：图灵机接受的语言（可能不停机）；
• 递归（可判定）：图灵机总能停机判定的语言——递归 ⊊ 递归可枚举，差的那部分就是不可判定的。

停机问题：对角线证明

停机问题：给定程序 $M$ 与输入 $w$，$M$ 是否在 $w$ 上停机？

定理：不可判定。证明是对角线法（Cantor 技巧的程序版）：

假设存在判定停机的程序 $H(M, w)$。构造：

P(M):  若 H(M, M) 说"停" → 死循环
       若 H(M, M) 说"不停" → 停

问 $P(P)$：若 $P(P)$ 停机 → $H(P,P)$ 说不停 → $P(P)$ 死循环——矛盾；反之亦然。没有这样的 $H$。□

对角线法是可计算性的核心证明技术：自我指涉 + 逃逸构造。停机不可判定的直接推论：

• 没有程序能判断任意程序是否终止——调试器的"会不会死循环"自动检测不存在；
• Rice 定理：程序的任何非平凡语义性质都不可判定——"这个程序是否会输出 42"、"是否是排序函数"、"是否有 bug"（语义性质的任何判定）都不可判定——形式验证的天花板（语义性质不可判定；语法性质可以）。

不可判定的实际后果

不可判定不妨碍对特定实例给出答案：

• 停机不可判定 ≠ 每个实例都判不了——多数程序明显终止或不终止，只是没有通用算法；
• 实践的分层：受限的模型可以判定（正则/上下文无关都有判定算法）→ 通用模型不可判定（图灵完备 = 不可判定的代价）；
• 图灵完备是双刃剑：表达力与不可判定性绑定——配置语言故意不图灵完备（YAML、SQL 的子集、正则表达式）就是为了可判定（静态检查、终止保证）；
• 形式验证（程序证明）绕开不可判定：人提供不变式与证明，机器检查——可判定的部分自动化，不可判定的部分靠人（Coq、Lean 的模式）。

归约与不可判定性

证明新问题不可判定的标准方法：把已知不可判定问题（停机）归约到它——若新问题可判定，停机也可判定，矛盾。不可判定的大家庭：停机、Post 对应问题、一阶逻辑的有效性、Hilbert 第十问题（丢番图方程）。

本章要点

• 图灵机 = 无限纸带 + 有限状态；所有变体与 Church–Turing 论题给出能力上界
• 通用图灵机即"程序是数据"；递归 ⊊ 递归可枚举，差的就是不可判定
• 停机问题对角线证明：自我指涉 + 逃逸构造
• Rice 定理：程序的任何非平凡语义性质都不可判定——形式验证的天花板
• 不可判定不妨碍对特定实例给出答案；图灵完备 = 不可判定的代价，受限模型可判定

相关阅读

资源维度的版本（能算但要多少资源），见P、NP 与归约与复杂度类全景。