不可计算性的蔓延：从停机问题到丢番图方程

引言：不可计算性会"传染"

上一章我们见证了图灵的对角线证明：停机问题不可判定。但停机问题位于计算机科学的腹地——它谈的是"程序是否停机"。一个自然的疑问是：不可计算性是否仅仅是计算机科学的内部现象，还是会蔓延到纯数学的腹地？

本章给出一个令人震撼的回答：不可计算性渗透到数学的每一个分支——代数（丢番图方程）、群论（字问题）、拓扑（流形同胚）、几何（铺砖问题），都存在不可判定的自然问题。这些问题没有提到"程序"或"图灵机"——它们是 19 世纪以来数学家就在追问的纯数学问题。但它们都被证明不可计算。

这一章的核心机制是归约（reduction）：把停机问题"伪装"成另一个数学问题。如果新问题能解，停机问题也能解；但停机问题不能解，于是新问题也不能解。归约就像传染病——一旦一个问题被证明不可判定，它就成了"种子"，可以感染一切能编码它的数学结构。

一、什么是"可计算"？人类有限步骤能解的终极集合

在追问"什么不可计算"之前，我们必须先弄清楚"什么算可计算"。整个第 19 章的震撼力，都建立在一个 1936 年才出现的精确答案上：人类用有限步骤能机械解决的问题，恰好等于图灵机能判定的问题——不多不少，一个集合。这个集合就是本章所有不可计算性结论的"边界线"。

三个等价的"可计算"定义在同一年汇聚

1936 年是数学史上最神奇的年份之一。三位数学家几乎同时给出了三个看起来完全不同的"可计算"形式定义：

\begin{array}{l|l|l} \text{年份} & \text{作者} & \text{定义} \\ \hline 1936 & \text{Alonzo Church} & \lambda\text{-演算可定义函数} \\ 1936 & \text{Alan Turing} & \text{图灵机可计算函数} \\ 1934\text{–}36 & \text{Gödel \& Kleene} & \text{一般递归函数} \\ 1943 & \text{Emil Post} & \text{Post 系统(产生式重写)} \\ 1936 & \text{Church} & \mu\text{-递归函数（与 Kleene 等价）} \end{array}

令人震撼的是：这五个完全不同的形式定义，定义出的可计算函数集合一字不差地相同。再往后，所有合理的"机械计算"形式化（寄存器机、组合子逻辑、Markov 算法、量子图灵机的可计算函数 = 经典图灵机）都收敛到同一个集合。

Church-Turing 论题：物理-逻辑的奇迹

这一汇聚催生了 20 世纪逻辑学最大的"经验断言"——Church-Turing 论题：

Church-Turing 论题（CT）。
"一个函数能被人类用一套有限明确的机械规则在有限步内算出"
当且仅当
它是图灵机可计算的。

注意"当且仅当"前一半是非数学的直觉概念（"机械计算"），后一半是精确的数学定义。CT 论题不能被证明——它是直觉与形式之间的桥梁，是一个关于"可计算"这个直觉概念到底指什么的论断。它至今未被任何反例推翻：每当有人提出新的计算模型（DNA 计算、模拟计算、量子计算……），最后总能证明它的可计算函数集合等于图灵可计算函数集合。

CT 论题有强弱两个版本：

逻辑 CT
（弱）：所有"算法"概念汇聚于图灵可计算——这是数学事实
物理 CT
（强，Deutsch 1985）：物理上可实现的任何计算装置，其可计算函数集合 ⊆ 图灵可计算——这是关于宇宙的物理猜想

本章后面所有"X 不可判定"的结论，都是相对 CT 论题而言的："不存在算法判定 X" = "不存在图灵机判定 X"。如果 CT 论题被推翻——例如发现某个超图灵的物理过程——本章定理就需要重新审视。这就是 CT 论题的地位：它定义了"算法"这个概念的范围，从而决定了"不可计算"的精确含义。

可计算 vs 可判定：一字之差的深渊

关于人类有限步骤能解决的问题，必须区分三层概念，否则后面所有讨论都会混乱：

\begin{array}{l|l|l} \text{术语} & \text{形式定义} & \text{直觉} \\ \hline \text{可计算函数} & \text{图灵机总停机并输出 } f(x) & \text{算得出值} \\ \text{可判定集 } (\Delta_1) & \text{特征函数 } \chi_S \text{ 可计算} & \text{能算

关键定理（Post 1944）：

\boxed{\;S \text{ 可判定} \;\;\Longleftrightarrow\;\; S \in \Sigma_1 \cap \Pi_1.\;}

这就是为什么停机问题不可判定——它是 Σ₁（停机能确认），但不是 Π₁（不停机无法确认）。如果某个问题"是答案能在有限时间确认，否答案也能在有限时间确认"，那它就在 Δ₁ 中——这正是"人类有限步骤能解决的问题"的精确数学定义。

判定边界 Δ₁：人类有限步骤能解的"终极集合"

把上面所有线索拢起来，可以给出本章最关键的概念：

定义（终极判定边界 Δ₁）。
"人类用任何有限明确的机械规则、在有限步骤内能解决的判定问题"
等于
Δ₁ = 递归集 = 图灵机能判定的集合。

这个集合有几个反直觉的性质：

可数
：图灵机本身是可数的（每个图灵机由有限程序描述），所以 Δ₁ 中只有可数无穷个集合
稀有
：自然数子集共有
2^ℵ₀
个（连续统），其中绝大多数
不在
Δ₁ 中——可判定问题在所有问题中"几乎全为零测度"
有具体边界
：停机问题、希尔伯特第十问题、字问题、流形同胚……这些都是
具体的
、
自然的
问题位于 Δ₁
之外
——不是病态构造，是数学家长期感兴趣的问题
边界是绝对的
：没有"更努力"或"更聪明"能突破 Δ₁，因为 CT 论题断言"任何机械方法"都收束于此

本章接下来的工作可以重新表述为：展示 Δ₁ 之外的数学家自然问题有多么丰富。Δ₁ 不是"一些尚未解决的问题"——它是数学问题宇宙中一道原则上无法跨越的墙。

图 1：可计算性的同心结构。Δ₁ = 可判定集合 = "人类有限步骤能解决的终极集合"，是 Σ₁ 与 Π₁ 的交集。停机问题、第十问题等"自然问题"位于 Σ₁ \ Δ₁ 中——是答案可确认，否答案永远不可确认。

二、归约：把停机问题"埋"进新问题

归约的形式定义

设 A、B 是两个判定问题。"A 多一归约到 B"（记作 $A \leq_m B$ ）的意思是：存在一个可计算函数 $f$ ，把 A 的实例翻译为 B 的实例，使得

x \in A \;\;\Longleftrightarrow\;\; f(x) \in B.

归约的逻辑后果非常强：

若 B 可判定，则 A 也可判定（用 f 翻译再调 B 的判定器）
反过来，若 A 不可判定，则 B 也不可判定（否则 A 就该可判定了）

这正是"不可判定性传染"的机制。把不可判定问题归约到 X，等于证明 X 也不可判定。整个第 19 章可以看作一句话的扩展——「停机问题归约到了多少自然的数学问题」。

归约的工作方式：编码即翻译

具体怎么把"程序停机"翻译成"丢番图方程有解"或"瓷砖能铺满平面"？答案是编码——把图灵机的运行轨迹用对应数学结构的语言写出来：

\text{图灵机 } M \text{ 在输入 } x \text{ 上停机} \;\;\Longleftrightarrow\;\; \text{某个数学对象 } \mathcal{O}(M, x) \text{ 拥有某种性质}.

编码越自然，归约越深刻——这一章下面四个例子的震撼程度，正比于"图灵机"如何隐藏在最普通的数学对象中。

三、希尔伯特第十问题与 MRDP 定理：数论中的图灵机

希尔伯特纲领的乐观图景

1900 年巴黎国际数学家大会上，大卫·希尔伯特发布了 23 个跨世纪问题。这份清单的精神底色，是希尔伯特的"形式主义乐观主义"——他坚信数学可以彻底机械化：每一个数学问题，原则上都可以被一套形式系统判定。他的座右铭"Wir müssen wissen, wir werden wissen（我们必须知道，我们终将知道）"道尽这一信念。

这一信念在三个具体计划中展开：

第一问题
（连续统假设）：基数算术能否完全
第二问题
（算术一致性）：能否在算术内部证明算术不矛盾
第十问题
（丢番图判定）：能否对一切多项式方程给出整数解判定算法

第十问题写道：

给定一个具有有限个未知数和整系数的丢番图方程，
设计一个程序
，能在有限步内判定该方程是否有整数解。

所谓丢番图方程，就是整系数多项式方程

P(x_1, x_2, \ldots, x_n) = 0, \quad P \in \mathbb{Z}[x_1, \ldots, x_n],\; \text{求 } (x_1, \ldots, x_n) \in \mathbb{Z}^n.

例如 $x^2 + y^2 = z^2$ （毕达哥拉斯方程）、 $x^n + y^n = z^n$ （费马大定理）、 $x^2 - 2y^2 = 1$ （佩尔方程）……希尔伯特的提问极其朴素：能否写一个万能程序，对任何丢番图方程都能判断"有整数解还是没有"？

注意 1900 年时图灵机还不存在。希尔伯特说"程序"用的是直觉性词汇 "process"。1936 年图灵给出形式化定义后，第十问题才有了精确的数学陈述：是否存在图灵机 M，对任何丢番图方程的编码 ⟨P⟩，停机并输出"有解/无解"？

希尔伯特的信念是：当然存在。整数论是 19 世纪研究最透彻的领域，多项式方程是其中最朴素的对象——如果连这个都不可判定，那希尔伯特的整个机械化纲领都会动摇。这是为什么第十问题的答案如此关乎根本。

解答的四十年长征：DPRM 路径

第十问题没有像费马大定理那样靠一位天才在最后时刻一举破解——它由四位数学家在 40 年里通过一条层层逼近的路径解决。这个解题路径本身就是数学史上的杰作：

\begin{array}{l|l|l} \text{年份} & \text{贡献者} & \text{进展} \\ \hline 1949 & \text{Martin Davis} & \text{猜想 r.e. = Diophantine, 部分结果（Davis 标准型）} \\ 1959 & \text{Davis–Putnam} & \text{用指数函数刻画, 但需要

关键节点是 1961 年 DPR 把目标缩到一个具体的"缺失的拼图"——Robinson 假设：

Robinson 假设。
存在一个 Diophantine 关系 R(a, b)，使得 R 蕴含 b ≤ aᵃ 但允许 b 至少像 aᵃ 那样指数增长。

Julia Robinson 在 50 年代独自工作多年，证明如果这个关系存在，那么 r.e. = Diophantine。但她未能构造它。这个假设悬挂了将近 20 年——直到 1970 年 1 月 17 日，22 岁的列宁格勒研究生尤里·马蒂亚谢维奇（Yuri Matiyasevich）发现：Fibonacci 数列 F_n 的指数增长性 F_{2n} ≈ φ^(2n) 恰好满足 Robinson 假设的所有条件，并且 F_{2n} 整除 F_{2m} 这一可整除关系是 Diophantine 的。这一发现一举打通了最后一扇门。

MRDP 定理：r.e. 集合 = 丢番图集合

整理 DPR + Matiyasevich 的工作，得到本章最深刻的定理：

MRDP 定理（Matiyasevich-Robinson-Davis-Putnam, 1970）。
一个集合 S ⊆ ℕᵏ 是 Diophantine 的当且仅当它是递归可枚举的：

\boxed{\;\text{Diophantine sets} \;=\; \text{recursively enumerable sets} \;=\; \Sigma_1.\;}

这是一个跨界级的定理。让我们具体看它的两个方向：

易方向（→）
：每个丢番图集是 r.e. 的——给定 P(a, x⃗) = 0，只需逐个枚举 (a, x⃗) ∈ ℕ^(1+m)，遇到使 P = 0 的就输出 a。这显然是图灵机能枚举的
难方向（←）
：每个 r.e. 集是丢番图的——这是 DPRM 的实质，需要把任意图灵机的"运行轨迹"
编码为一个具体多项式方程的可解性条件
。Fibonacci 数的整除关系给了关键的"指数级权重"，让多项式有足够表达力模拟无界循环

这个等式的哲学冲击是：整数论这个最古老的学科，在表达力上等同于完整的通用计算。任何图灵机能做的事，都能伪装成"找一个多项式方程的整数解"。数论不再是"特殊"的——它就是计算的另一面孔。

第十问题的不可判定性

由 MRDP，停机问题这个 r.e. 但不可判定的集合，对应一个具体的丢番图方程族。从而：

\boxed{\;\text{希尔伯特第十问题（丢番图方程整数解的判定）不可判定}.\;}

具体地，存在一个具体的 $P(a, x_1, \ldots, x_m) \in \mathbb{Z}[a, x_1, \ldots, x_m]$ （参数 a 是图灵机和输入的编码），使得"图灵机 M_a 在空输入下停机"等价于"P(a, x₁, …, xₘ) = 0 关于 (x₁,…,xₘ) 有自然数解"。判定后者就等于判定前者，所以前者不可判定就强迫后者也不可判定。

"通用方程"的参数压缩史

MRDP 不仅是定性结论，更有具体的边界。压缩"通用丢番图方程"的未知数个数与次数是一项延续 50 年的工作：

\begin{array}{l|l|l} \text{时间} & \text{未知数 / 次数} & \text{贡献者} \\ \hline 1970 & \approx 200 \text{ 未知数} & \text{Matiyasevich 原版} \\ 1970\text{s} & 26 \text{ 未知数, 次数极大} & \text{Matiyasevich-Robinson} \\ 1981 & 9 \text{ 未知数, 次数} \approx 10^{45} & \text{Matiyasevich} \\ \text{开放} & \text{次数 4, 58 未知数（猜想下界）} & \text{Jones 1982} \\ \text{开放} & 3 \text{ 个未知数是否够用？} & \text{尚未解决} \end{array}

当前最强结果（Matiyasevich 1981）：仅 9 个未知数的多项式方程族，足以编码任何停机问题。也就是说，存在一个具体的、可写下来的多项式 P(a, x₁,…,x₉) ∈ ℤ[a, x⃗]，第十问题的"通用版本"在9 元 ℤ-多项式这个最普通的代数对象族里就已经不可判定了。整数论这个数学最古老的分支，藏着图灵机。

哲学冲击：黎曼猜想 = 一个方程的可解性

MRDP 还有一个令人震撼的推论：每个 Π₁ 的数学猜想都可以转化为"一个具体丢番图方程是否无整数解"。这是因为：

"对所有自然数 n，性质 φ(n) 成立"（Π₁ 陈述）等价于 "{n : ¬φ(n)} = ∅"
{n : ¬φ(n)} 是 r.e.（如果可以一步步检验 ¬φ）
由 MRDP，它对应一个丢番图方程 P_φ = 0
"猜想 φ 成立" ⟺ "P_φ = 0 在自然数中无解"

具体可以转化的著名猜想：

\begin{array}{l|l} \text{猜想} & \text{Diophantine 形式} \\ \hline \text{哥德巴赫猜想} & \exists\, P_{GC} \in \mathbb{Z}[x_1,\ldots,x_k]: P_{GC} = 0 \text{ 无解} \\ \text{黎曼猜想} & \exists\, P_{RH} \in \mathbb{Z}[x_1,\ldots,x_k]: P_{RH} = 0 \text{ 无解} \\ \text{孪生素数} & \exists\, P_{TP}: P_{TP} = 0 \text{ 在某约束下无解} \\ \text{ZFC 一致性} & \exists\, P_{\mathrm{ZFC}}: P_{\mathrm{ZFC}} = 0 \text{ 无解} \end{array}

Jones 等人甚至给出过具体的表达 RH 的多项式（数十个未知数，几百项）。"黎曼猜想正确"等价于"某个具体的丢番图方程在自然数中无解"——这一转换原则上把分析学最深的猜想还原为初等数论的问题。当然不是说这就让 RH 简单了——只是表达力的本质等价。

与哥德尔不完备的合奏

MRDP 与哥德尔不完备定理共振，给出最强的"算术不完备"结论：

定理（Diophantine 不完备性）。
对任何一致、可有效公理化、足以描述初等算术的形式系统 T，存在一个具体的丢番图方程 P，使得"P 无自然数解"在标准模型中为真，但 T 既不能证明也不能反驳它。

哥德尔的 G 句子原版是自我指涉的元数学陈述（"我不可证"），需要 Gödel 编码才能写出。MRDP 把这种不可判定性下放到纯数论形式——存在不带任何元数学包装、纯纯整数系数多项式方程，使其"无解性"超出 PA、ZFC 等一切合理形式系统的判定能力。希尔伯特纲领在这里彻底落幕：不仅形式系统不能证明所有真命题，连整数论这一最具体的真命题集合都已经超出形式系统。

恰好相等

⇒ 停机不可判定 ⇒ 第十问题不可判定

图 1：MRDP 定理建立的双向归约——图灵机停机性与丢番图方程可解性互相编码。停机问题的不可判定性"传染"为第十问题的不可判定性。

四、字问题：群论中的不可判定性

有限表示群

把图灵机藏进数论已经够意外，那它能藏进群论吗？答案是肯定的——这就是字问题（Word Problem）。

一个群可以用有限表示描述：

G \;=\; \langle\, s_1, s_2, \ldots, s_n \;\big|\; r_1 = e,\; r_2 = e,\; \ldots,\; r_k = e\,\rangle.

意思是：G 由生成元 $s_1, \ldots, s_n$ 通过乘法与求逆得到，并且关系 $r_i = e$ 在 G 中成立（其中每个 $r_i$ 是生成元的有限字）。任何元素都是生成元的字（word），但同一个元素可能有不同的字——比如在交换群里 $s_1 s_2 = s_2 s_1$ 。

字问题：给定 G 的有限表示和 G 中的两个字 $w_1, w_2$ ，判定 $w_1 = w_2$ 是否在 G 中成立（即 $w_1 w_2^{-1}$ 是否等于 e）。这是一个看起来纯代数的问题：把字按关系反复改写、能否化为同一形式？

Novikov-Boone 定理

1955–1957 年，Novikov 与 Boone 独立证明：

Novikov-Boone 定理（1955/57）。
存在一个有限表示群 G，其字问题不可判定。

即存在具体的生成元和关系列表，使得"两个字是否相等"无法用任何算法判定。证明的核心是把图灵机模拟到群表示里——构造的关系编码了图灵机的转移规则，从而图灵机的"停机"对应"特定字等于 e"。

这个结论令人毛骨悚然：群论是 19 世纪以来抽象代数的中心，"两个表达式是否相等"是最基本的代数操作之一——居然没有通用算法。判定群元素相等，原则上需要等待无穷长时间。具体的群里（如阿贝尔群、有限群、自由群、双曲群）字问题可判定，但对一般有限表示群，字问题与停机问题等价。

群论的更多不可判定问题

由 Novikov-Boone 出发，群论中的多个判定问题接连倒下：

\begin{array}{l|l} \text{群论判定问题} & \text{状态} \\ \hline \text{字问题（两字相等？）} & \text{不可判定（Novikov-Boone 1955/57）} \\ \text{共轭问题（两元素是否共轭？）} & \text{不可判定} \\ \text{同构问题（两群是否同构？）} & \text{不可判定（Adyan-Rabin 1958）} \\ \text{平凡性问题（群是否平凡？）} & \text{不可判定} \\ \text{有限性问题（群是否有限？）} & \text{不可判定} \end{array}

这就是 Adyan-Rabin 定理的精神：群论中几乎所有的"自然"性质，对一般有限表示群都不可判定。

五、流形同胚问题：拓扑中的不可判定

从代数蔓延到拓扑。流形是高维"曲面"——光滑空间的局部欧氏化。同胚问题问：给定两个流形 $M_1, M_2$ 的有限组合描述（如三角剖分），它们是否同胚？

低维情形相对温和：

1 维：所有连通紧 1-流形都是圆周或区间，可判定
2 维：紧曲面由亏格 + 可定向性完全分类（19 世纪结果），可判定
3 维：可判定（Perelman 完成 Geometrization 后由 Kuperberg 等给出算法）
≥ 4 维：不可判定

关键定理：

定理（Markov 1958）。
对每个 n ≥ 4，n-维紧流形的同胚问题不可判定。

证明思路：对一个有限表示群 G 用 Novikov-Boone 选定的字问题，构造一个 4 维流形 $M(G)$ ，使得 $\pi_1(M(G)) = G$ 。然后"两个流形同胚"包含"两个基本群同构"——而群同构由 Adyan-Rabin 已知不可判定。归约链条：

\text{停机问题} \;\leq_m\; \text{字问题} \;\leq_m\; \text{群同构问题} \;\leq_m\; \text{流形同胚问题}.

这解释了为什么 4 维拓扑特别困难。同样原因，判定一个 4-流形是否同胚于 4-球面也不可判定——这是 Poincaré 猜想在高维度的一种"算法版本"。Poincaré 猜想（每个 3 维同伦球同胚于 3 球）虽被 Perelman 在 2003 年证明，但同维度的"识别问题"（给定流形，是否同胚于球面）只在 3 维可判定，4 维起不可判定。

六、王浩的铺砖问题与非周期镶嵌

问题陈述

1961 年，逻辑学家王浩（Hao Wang）提出了铺砖问题：给定有限多种正方形瓷砖（每边染一种颜色），能否用它们的拷贝铺满整个无限平面 $\mathbb{R}^2$ ，使相邻瓷砖的相邻边颜色匹配（且瓷砖不能旋转）？

王浩本人猜想：如果一组瓷砖能铺满平面，那它一定能周期性地铺满（即存在两个独立的平移使铺砖整体不变）。如果这个猜想成立，铺砖问题就可判定（试有限范围）。

Berger 的反驳与不可判定性

1966 年王浩的学生 Robert Berger 证明：

Berger 定理（1966）。
王浩铺砖问题不可判定。同时，存在能铺满平面但
不能
周期铺满的瓷砖组——
非周期铺砖集
。

证明同样基于归约：把图灵机的运行轨迹编码为铺砖——每行瓷砖代表图灵机一步运行的纸带状态，相邻边颜色匹配确保转移规则正确。"图灵机不停机"对应"能铺满整个平面"，"图灵机停机"对应"铺到某行就卡住"。归约直接把停机问题的不可判定性搬到了铺砖问题上。

关键副产品是非周期镶嵌：Berger 最初构造了 20426 块瓷砖的非周期集，后被简化到 13 块（Culik 1996）、再到 11 块（Jeandel-Rao 2015）。1974 年彭罗斯（Roger Penrose）发现了仅用 2 块菱形瓷砖即可非周期铺满平面的彭罗斯镶嵌——这种镶嵌后来在 1984 年的准晶体（quasicrystal）发现中得到了物理实现，2011 年的诺贝尔化学奖颁给了 Shechtman 关于准晶的工作。

图 2：王浩铺砖问题对图灵机的编码。每块瓷砖编码一步转移，铺满平面等价于图灵机永不停机。归约把停机问题不可判定性传染为铺砖问题不可判定性，副产品是非周期镶嵌的存在性。

七、不可计算性的统一图景

归约网络

把本章所有结果连成一张图：所有这些"自然的数学问题"都和停机问题多一归约等价——它们都是 r.e.-完全的（recursively enumerable complete）。

图 3：不可判定问题的归约网络。以停机问题为枢纽，归约辐射到代数（丢番图、字问题）、拓扑（流形同胚）、几何（铺砖）、计算（莱斯定理）、分析（微分方程）。所有问题

等可计算

——同一个不可解性的不同伪装。

更多蔓延：分析、逻辑、动力系统

归约的疾病传染力远不止上面四例。下面是数学其他分支中的不可判定问题清单：

\begin{array}{l|l|l} \text{领域} & \text{不可判定问题} & \text{文献} \\ \hline \text{微分方程} & \text{含 } e^x, \sin x \text{ 的初等函数零点} & \text{Richardson 1968} \\ \text{符号积分} & \text{初等函数的初等原函数判定} & \text{Risch 之后}\\ \text{动力系统} & \text{矩阵幂的可达性（} 3 \times 3 \text{ 整数矩阵）} & \text{Mortality}\\ \text{逻辑} & \text{一阶逻辑有效性（} \mathrm{FOL} \text{）} & \text{Church 1936}\\ \text{语言学} & \text{无限制文法等价性 / 接受性} & \text{Post 1947}\\ \text{物理学} & \text{量子多体系统能隙存在性} & \text{Cubitt-Pérez-García-Wolf 2015} \end{array}

最后一项尤其值得注意——2015 年 Nature 上的工作证明了量子物理中"基态是否有能隙"也不可判定。不可计算性甚至渗透到了物理学——某些物理系统的宏观性质，原则上无法从微观哈密顿量算出。

统一的"病原体"：编码 + 自指

所有这些不可判定性归根到底都来自同一个"病原体"——足够强的表达力 + 自我指涉的能力：

多项式方程足够丰富，能"模拟"图灵机的状态转移（MRDP）
有限表示群足够丰富，能"嵌入"图灵机（Novikov-Boone）
瓷砖匹配规则足够丰富，能"编码"图灵机纸带（Berger）

每当一个数学结构的表达力强到能模拟通用计算，它就继承了停机问题的不可判定性。这就是为什么 19 世纪才出现的群论、20 世纪才出现的量子物理，都被一个 1936 年的对角线证明所"诅咒"——它们的表达力过界了。

八、可计算性的终极地图：算术层级

到目前为止我们建立了一道墙：Δ₁ 是"人类有限步骤能解的终极集合"。但 Δ₁ 之外并不是均匀的"不可计算"——它本身有着精细的内部层级。把这层级画出来，就得到了 20 世纪逻辑学最优雅的成果：算术层级（Arithmetical Hierarchy），由 Kleene 1943 与 Mostowski 1947 独立建立。这张地图回答了本章的终极问题——"不可计算"也分轻重缓急吗？答案是：分得清清楚楚。

算术层级的递归定义

用一阶算术（语言中只含 +、×、=、< 和量词 ∀ ∃）定义自然数集合时，量词交替的次数恰好刻画了"求解难度"：

\begin{array}{l|l|l} \text{层级} & \text{量词形态} & \text{含义} \\ \hline \Sigma_0 = \Pi_0 = \Delta_0 = \Delta_1 & \text{无量词 / 有界量词} & \text{可判定 (递归)} \\ \Sigma_1 & \exists\, \vec{y}\; R(x, \vec{y}) & \text{r.e.（停机集所在层）} \\ \Pi_1 & \forall\, \vec{y}\; R(x, \vec{y}) & \text{co-r.e.（不停机集 / 大多数 \

关键事实是这是真正的层级——每一层严格大于前一层：

\Delta_1 \subsetneq \Sigma_1, \Pi_1 \subsetneq \Delta_2 \subsetneq \Sigma_2, \Pi_2 \subsetneq \Delta_3 \subsetneq \cdots

这一不塌陷性叫做层级定理（Kleene 1943）：每升一层，都有具体的集合从下一层"逃出来"。证明用对角线——和图灵证明 Σ₁ ⊋ Δ₁（停机集不在 Δ₁ 中）的方式完全平行，只是把图灵机替换为"带 oracle 的图灵机"。

跳跃定理：层级如何"竖起来"

算术层级不是凭空堆叠出的，它由跳跃运算 A → A′ 驱动。给一个集合 A，定义它的"停机问题相对版本"

A' \;=\; \{\, e : \text{第 } e \text{ 个图灵机, 配上 oracle } A, \text{ 在输入 } e \text{ 上停机}\,\}.

跳跃就是"用上一层 oracle 重做停机证明"。

Kleene 跳跃定理。
对任意集合 A，A 严格归约到 A′ 但 A′
不
归约到 A。从而 ∅ < ∅′ < ∅″ < ∅‴ < ⋯ 是一条严格上升链。并且：

\Sigma_{n+1} = \{\,S : S \text{ 相对 } \emptyset^{(n)} \text{ 是 r.e.}\,\}, \quad \emptyset^{(n)} \in \Delta_{n+1}\setminus \Delta_n.

形象地说：Σ₁ 是"图灵机能枚举"，Σ₂ 是"图灵机带停机问题 oracle 能枚举"，Σ₃ 是"图灵机带 Σ₂-oracle 能枚举"……每一层都是"上一层的停机问题"。整个算术层级就是这样一节一节竖起来的——像一座没有终点的塔。

具体例子：本章问题在层级中的位置

把本章所有问题按算术层级"对号入座"：

\begin{array}{l|l|l} \text{问题} & \text{层级} & \text{量词形态} \\ \hline \text{毕达哥拉斯方程有解 (具体方程)} & \Delta_1 & \text{可判定} \\ \text{停机问题 HALT} & \Sigma_1 \setminus \Delta_1 & \exists t\, [M(x) \text{ 在 } t \text{ 步内停机}] \\ \text{第十问题（HALT 等价）} & \Sigma_1 \setminus \Delta_1 & \exists \vec{x}\, [P(a,\vec{x})=0] \\ \text{字问题 / 王浩瓷砖} & \Sigma_1 \setminus \Delta_1 & \exists \text{ 重写步骤 / 铺砖} \\ \text{哥德巴赫猜想 / RH（作为陈述）} & \Pi_1 & \forall n\, [\varphi(n)] \\ \text{TOT}=\{e : \forall x\, M_e(x)\!\downarrow\} & \Pi_2\text{-完全} & \forall x\, \exists t\, [\ldots \text{停机}] \\ \text{FIN}=\{e : W_e \text{ 有限}\} & \Sigma_2\text{-完全} & \exists N\, \forall x>N\, [\ldots] \\ \text{COF}=\{e : W_e \text{ 余有限}\} & \Sigma_3\text{-完全} & \exists N\, \forall x>N\, \exists t\, [\ldots] \\ \text{REC}=\{e : W_e \text{ 是递归的}\} & \Sigma_3\text{-完全} & \text{Rogers}\\ \text{真算术 } \mathrm{Th}(\mathbb{N}, +, \times) & \bigcup_n \Sigma_n \text{ 之外} & \text{Tarski: 不可算术定义} \end{array}

令人震撼的是："判定问题判定性"本身的复杂度需要 Σ₃——也就是说，"给一个程序的索引 e，判断 W_e 是否递归"这个元层次问题，比停机问题难整整两层。Δ₁ 的边界本身从 Δ₁ 之内是看不见的。

Δ₁ 在所有问题中的稀有性

我们把 Δ₁ 与整个算术层级做一个测度论比较：

Δ₁ 是可数的
：每个图灵机由有限程序描述，至多 ℵ₀ 个
每一层 Σ_n、Π_n 也都可数
：算术公式数量可数
整个算术层级 ⋃ₙ (Σ_n ∪ Π_n) 仍是可数的
——它只是 ℕ 上"算术可定义"集合的全部
但自然数子集共有 2^ℵ₀ 个
——绝大多数集合
连算术公式都写不出来
，更别说判定

用这个测度尺度衡量，Δ₁ 在自然数子集的"宇宙"里是测度零的尘埃。然而这粒尘埃恰好包含了所有有限步骤可判定的问题——人类、计算机、甚至外星智能（在 CT 论题成立的前提下）能解的判定问题，全部装在这粒尘埃中。

Δ₁ 之外的"难度梯度"

算术层级澄清了一件外行常常误解的事："不可计算"不是一个均匀的标签。Σ₁ 中的停机问题虽然不可判定，但它是 r.e. 的——"有限时间内能确认停机"。Π₁ 中的"程序对所有输入停机"则更难——"否答案能确认，是答案永远不能确认"。再往上：

TOT
（程序对所有输入停机？）是 Π₂-完全——比停机问题
本质
更难
FIN
（程序的接受集有限？）是 Σ₂-完全——含有"存在 N 后再普适"
真算术
（ℕ 中所有真公式集合）
不在任何 Σ_n 中
——超出整个算术层级（Tarski 真理不可定义性）

本章前几节的所有不可判定问题（第十、字、流形、王浩）恰好都站在 Σ₁ \ Δ₁ 这个"最浅一层"上——它们是 r.e.-完全的。这是它们被归约自停机问题的直接后果。整个数学的判定难度梯度像一座金字塔，停机问题位于地面以上的第一层，上面还有无穷多层。

物理 Church-Turing 论题：Δ₁ 是宇宙的边界吗？

逻辑 CT 论题断言"算法 = 图灵可计算"，这把"人类有限步骤能解"等同于 Δ₁。但还有一个更深的问题：物理可实现的任何过程，能否突破 Δ₁？

物理 Church-Turing 论题（Deutsch 1985）。
任何有限可实现的物理装置，都能被图灵机以多项式开销模拟。等价地：物理上可计算的函数集合 ⊆ Δ₁。

这是一个关于宇宙的物理猜想，不能由数学证明。如果它成立，那么即使是未来不可预知的物理——量子引力、霍金辐射、闭合类时曲线（CTC）——也无法把人类拉出 Δ₁。如果它不成立——例如有人构造了"超图灵"装置（Hypercomputer）——那么本章所有"不可判定"结论都需要相对化重写。

目前所有候选的"超图灵物理"都失败了：

量子计算机：可计算函数集合 = Δ₁（量子图灵机定理）
模拟计算 / 实数寄存器：实际可实现版本受噪声限制，回归 Δ₁
Malament-Hogarth 时空（CTC 类型）：依赖永不被观测的极限过程，不可物理实现

所以截至当前知识，Δ₁ 既是逻辑边界，也是物理边界——人类有限步骤能解的问题，等于物理上能用任何机器解的问题，等于图灵机能判定的集合。这三者重合不是一个数学定理，而是一个关于宇宙结构的深刻经验事实。

图 4：算术层级金字塔。Δ₁（绿色基座）是"人类有限步可解的终极集合"——可数、稀有、有清晰边界。本章四大不可判定问题（停机/第十/字/王浩）齐聚于 Σ₁ \ Δ₁ 这一最浅的不可判定层；上面还有 Σ_n、Π_n 无穷多层，更上是 Tarski 不可算术定义的"真算术"——一座没有顶的塔。

结语：数学的内在边界

本章的故事可以浓缩为一句话：不可计算性不是计算机科学的人造问题，而是数学结构表达力的内在副作用。当一个数学领域足够丰富以模拟图灵机时，它就不可避免地包含不可判定的自然问题。

这一发现颠覆了希尔伯特 1900 年的乐观主义。希尔伯特在巴黎演讲的结尾宣告："我们必须知道，我们终将知道（Wir müssen wissen, wir werden wissen）。"——这句话被刻在他的墓碑上。然而 1931 年哥德尔证明了不完备性，1936 年图灵证明了停机不可判定，1970 年 Matiyasevich 解决了第十问题——希尔伯特的乐观蓝图在自己的清单第十题上崩塌：对一类最朴素的丢番图方程，不存在判定算法。

但这不是数学的失败，而是数学的自我认识。正如哥德尔不完备定理告诉我们"形式系统的能力有内在边界"，本章告诉我们"数学结构的判定能力也有内在边界"。这些边界不是技术性的——它们是结构表达力的逻辑后果。我们不是没找到算法，而是没有这种算法，正如平方根 2 不是没找到分数表示，而是没有这种分数。

把全章拢成一句最简的总结：人类有限步骤能解的问题，恰好是 Δ₁——一个可数、稀有、却有清晰边界的集合。本章四大问题（第十、字、流形、王浩）都坐落在 Δ₁ 之外的第一层（Σ₁），更高层 Σ_n / Π_n 一直延伸到无穷，再往上是 Tarski 真算术——一座永无顶端的塔。希尔伯特"我们终将知道"在 Δ₁ 之内仍然成立，但 Δ₁ 只是一粒尘埃；真正广袤的数学世界，原则上就是人类有限步骤进入不了的。

下一章我们将进一步探究：在不可计算的世界里，问题之间是否还有"难度差异"？答案是肯定的——这就是 Oracle 图灵机与图灵度的理论，它给不可计算性本身建立了精细的层级结构。停机问题只是冰山一角，冰山之下还有无穷无尽的"更难"的问题。