Oracle 图灵机与图灵度：不可计算性的光谱

停机问题不可计算——这是 Turing 留下的"硬墙"。我们已经知道：所有非平凡的语义性质都被 Rice 定理一并扔到了墙的另一边。但一个自然的问题接着冒出来：

不可计算的问题之间，有没有"难度"差别？

"程序是否停机"不可计算；"程序是否对所有输入都停机"也不可计算。但后者是不是比前者更难？换句话说，如果我有一台能瞬间回答停机问题的"超能机器"，它够不够用来回答"对所有输入都停机"？

1944 年，Emil Post 把这个问题正式提出来：能不能给不可计算性建立一个"难度阶梯"？它不会让任何问题变得可计算，但它能让我们看清"不可计算性"内部的丰富结构。回答这个问题的工具，叫Oracle 图灵机；得到的层级结构，叫图灵度（Turing degrees）。

这一章我们走进这个奇妙的世界——你会看到，不可计算性远不是一片漆黑，而是一架壮丽无比的金字塔。

一、Oracle 图灵机——给图灵机配一个"神谕"

普通图灵机靠一条带子和一组状态来计算。Oracle 图灵机比它多一样东西：一个神谕（oracle）。

具体地，固定一个集合 A ⊆ ℕ。带 A-oracle 的图灵机是这样的：

  • 它和普通图灵机几乎一样，状态、纸带、转移函数都有；

  • 但它额外有一条

    询问带

    和一个特殊状态 q_? ；

  • 当机器进入 q_? 时，它读出询问带上的数字 n，

    瞬间

    得到答案"n ∈ A 吗？"，并据此进入下一状态。

换句话说，oracle 是一个可以一步查询的黑盒，它能回答关于 A 的成员资格问题——哪怕 A 本身不可计算。

用通俗的话说：你有一台普通电脑，再加一根电话线连到上帝那里——你随时可以问"x 在 A 里吗"，上帝立刻回答。这下你能解决多少问题？

例子：用停机集 K 当 oracle

设 K = {⟨P, x⟩ : P 在 x 上停机}（停机集）。K 不可计算。但有了 K-oracle 后：

  • "程序 P 在输入 x 上停机吗？" — 一查 K 即可，O(1)；

  • "程序 P 是否对所有输入都停机？" — 这需要"对所有 x 查一次"，但你不能查无限多次……所以 K-oracle 还

    不够强

    来解决这个问题。

这个观察提示我们：oracle 的力量是有边界的——它能突破自身那一层，但不能无限突破。这就是图灵度阶梯的源头。

二、图灵归约——把"难度"形式化

有了 oracle，就能定义"问题之间的难度比较"。

定义

集合 A 图灵归约到 B，记作 A ≤_T B，当且仅当存在一台 B-oracle 图灵机能判定 A。

A \le_T B \;\iff\; \exists\, M^{B} \text{ 判定 } A.

含义：给我 B 的答案，我就能算 A——所以 B 至少和 A 一样难。

它和我们熟悉的"多项式归约"不同：

  • 多项式归约管的是"复杂度等价"——A ≤_p B 表示 A 不比 B 难太多（多项式倍）；

  • 图灵归约管的是"可计算性等价"——A ≤_T B 表示给了 B 就能算 A，

    不论用多长时间

    。

图灵归约比多项式归约宽松得多，但也因此更适合刻画"不可计算性"的内部结构。

图灵等价

如果 A ≤_T B 且 B ≤_T A，我们说 A 和 B 图灵等价，记 A ≡_T B：

A \equiv_T B \;\iff\; A \le_T B \;\text{ 且 }\; B \le_T A.

这是一个等价关系。每个等价类就是一个图灵度。

三、图灵度——不可计算性的"等高线"

所有集合 ⊆ ℕ 在 ≡_T 下分成等价类。每个等价类叫一个图灵度。

  • 0

    （最小度）：所有

    可计算集合

    构成一个度，记作

    0

    。这是"最容易"的一层——因为可计算集互相之间根本不需要 oracle 帮助。

  • 0'

    （图灵跳跃 / "0 prime"）：停机集 K 的度。它

    严格大于

    0——K ∉ 0，即 K 不可计算。

  • 0''、0'''、…

    ：依次往上跳——0'' 是"K 的停机问题"的度，0''' 是再上一层，etc.

  • 所有度构成一个

    偏序

    ：a ≤ b ⟺ a 中任一集合可被 b 中任一集合归约。这个偏序结构叫

    图灵度的格

    。

图灵跳跃算子

对任意度 a，它的跳跃 a' 定义为"以 a 中集合为 oracle 的停机问题"的度：

a' \;=\; \mathrm{deg}\big(\, \{\,e \mid \Phi_e^A(e) \!\downarrow \,\} \,\big), \quad A \in a.

关键性质：a' 严格大于 a（即 a' > a 总成立）。这就保证了从 0 出发，对图灵跳跃迭代下去，得到一条无尽上升的阶梯：

\mathbf{0} \;<\; \mathbf{0}' \;<\; \mathbf{0}'' \;<\; \mathbf{0}''' \;<\; \cdots \;<\; \mathbf{0}^{(\omega)} \;<\; \cdots

每一阶都是真实存在的不可计算性"层级"。这就是图灵度的金字塔。

0 · 可计算 0' · 停机问题 · Σ₁ 完全 0'' · "∀ 程序都停机" · Σ₂ 完全 0''' · Σ₃ 完全 ⋮ 0^(ω) · 超限跳跃 图灵跳跃算子构造的无穷上升塔——每一步都是"严格更难"

图灵度阶梯：从可计算往上的不可计算性金字塔

四、图灵度的格结构——比阶梯更复杂

如果你以为图灵度只是一条直线，那就太低估它了。它不是线性的——它是一个格（lattice），有上界、下界，但不可比的度也很多。

下确界与上确界

对任意两个度 a、b：

  • 上确界

    a ∨ b 总存在：把 A 和 B "合在一起"作 oracle，能算的就是 a ∨ b。具体地 A ⊕ B = {2n : n∈A} ∪ {2n+1 : n∈B} 是一个代表。

  • 下确界

    a ∧ b 通常不存在！这是图灵度格不是

    分配格

    的根源。

不可比的度

1956 年 Kleene-Post 证明：在 0 和 0' 之间存在两个互不可比的度——即存在 a, b 使得 a ≰ b 且 b ≰ a。这些度对应的集合："各有所长，谁也算不过谁"。

这告诉我们：不可计算性不是一条线，而是一棵树（甚至是一片森林）。两个问题可能都比停机问题简单，但又互相之间没有归约关系。

五、Post 问题与优先级方法——递归论的"广义相对论"

Emil Post 1944 年的另一个深刻问题：0 和 0' 之间，有没有 r.e. 集的中间度？

r.e.（递归可枚举）集是"可半判定的"——你能枚举它的所有元素，但可能枚举不完。所有 r.e. 集都满足 0 ≤ deg ≤ 0'：因为 r.e. 集都可归约到 K。问题是：除了"完全可计算"和"完全像停机问题那么难"之外，r.e. 集中间的"中等难度"是否真实存在？

Friedberg-Muchnik 定理（1956-1957）

独立证明者 Richard Friedberg（美国，本科生）和 Albert Muchnik（苏联）几乎同时给出肯定答案：

存在两个互不可比的 r.e. 度 a, b，且 0 < a, b < 0'。

证明用了一个全新的方法——优先级论证（priority argument）。

思想是：要构造两个集合 A, B 同时满足无穷多个"需求"（requirement），每个需求都说"A 不能用 B 算出"或反之。这些需求会互相干扰。优先级方法给每个需求编号，让低编号需求胜过高编号——一个需求被打破时，可以重新启动它，但保证它最终被永久满足。

这是一种"无穷的官僚体系"：每个需求都在排队等待被实现，但有人能插队、有人会被推迟，但只要队列管理得当，所有需求最终都能满足。

优先级论证后来发展成递归论的核心技术——它的复杂度堪比代数几何里的概形语言。它打开了r.e. 度结构的研究，至今仍有大量开放问题。

六、算术层级——量词复杂度的阶梯

图灵度有一个对偶视角，叫算术层级（arithmetical hierarchy）。它从"逻辑量词的复杂度"刻画问题难度：

  • Σ₀ = Π₀ = Δ₁

    ：可计算集（无量词，或所有量词都是有界量词）。

  • Σ₁

    ：r.e. 集——形如 {x : ∃y. R(x,y)}，R 可计算。停机集是 Σ₁ 的代表。

  • Π₁

    ：co-r.e. 集——形如 {x : ∀y. R(x,y)}。例如"所有输入都停机"是 Π₁。

  • Σ₂

    ：{x : ∃y ∀z. R(x,y,z)}。

  • Π₂

    ：{x : ∀y ∃z. R(x,y,z)}。"全函数"集 = Π₂。

  • ……

\Sigma_n \;=\; \big\{\, x \mid \exists y_1\, \forall y_2\, \exists y_3 \cdots Q\, y_n.\; R(x, \vec{y}) \,\big\}, \quad R \in \Delta_1.

Post 定理：层级与跳跃同构

这两个塔不是巧合——它们是同一座塔的两副面孔。Post 定理（1948）建立了精确对应：

A ∈ Σ_{n+1} 当且仅当 A 是 r.e. 相对于一个 0^(n) ； 更强：Σ_n 完全集恰好是 0^(n) 的代表。

这是一个深刻的同构：

  • "用更多量词"（语法层面）= "用更强 oracle"（语义层面）；

  • "逻辑复杂度"= "计算复杂度"。

这道桥梁在 1948 年架起，把模型论、证明论、可计算性论结合到一起，是 20 世纪逻辑学最优雅的结果之一。

Δ₁ = 可计算（无量词） Σ₁ = ∃y. R Π₁ = ∀y. R Σ₂ = ∃∀ Π₂ = ∀∃ Σ₃ Π₃ ⋮ ≡ 0 ≡ 0' ≡ 0'' ≡ 0''' ⋮ Post 定理：算术层级 Σₙ / Πₙ 与图灵跳跃 0^(n) 一一对应

算术层级金字塔——逻辑量词的复杂度即是计算的难度

七、相对可计算性的哲学冲击

(1) "可计算"是一个相对概念

没有 oracle 时，可计算 = 图灵机能算的。但只要给一个不可计算的 oracle，"可计算"就变了：原本不可解的问题变成可解。计算性不再是绝对，而是"相对于某个信息基"的概念。

这把"算法 vs 不可算法"的二分，升级成"问题在哪一层"的连续光谱。它的精神类似爱因斯坦把绝对时间换成相对时间：没有绝对的'计算'，只有'相对的'计算。

(2) 不可计算性也有"形状"

"不可计算"曾被想像成均一的"黑暗"。但图灵度告诉我们：黑暗里有等高线、山峰、森林。这种结构不是形而上学的——它有具体的数学定理（Friedberg-Muchnik、Sacks、Shoenfield 等）支撑。

(3) 给"知识递增"建模

有人把图灵跳跃理解为"获取新知识的过程"：你站在 0 这一层，能解所有可计算问题；学会了停机问题，你跳到 0'，能解更多；再学会"全停机问题"，你跳到 0''……每一次跳跃都对应"理解力的飞跃"。

这只是直观比喻，但它启发了相关研究——比如归纳推断（inductive inference）、认知逻辑等领域，都借用这个结构来建模"知识增长"的极限。

七 ½、Sacks 稠密性与 Shoenfield 极限引理——结构远比想象丰富

给图灵度的故事再加点料。两个 20 世纪 60 年代的深刻定理告诉我们，r.e. 度的内部结构精彩得像一部小说：

Sacks 稠密性定理（1964）

对任意两个 r.e. 度 a < b，都存在 r.e. 度 c 使得 a < c < b。

这意味着 r.e. 度作为偏序集是稠密的——就像有理数集那样"挤得满满"。Sacks 用了改进版的优先级方法（"无穷损害"）来证明这件事，技术高度堪称神迹。

Shoenfield 极限引理

A ≤_T 0' 当且仅当 A 是某个可计算函数序列 {f_n} 的"逐点极限"——即对每个 x，f_n(x) 终将稳定在 A 的特征函数 χ_A(x)。

这是一个奇妙的"动态描述"：0' 这一层的集合，恰好是可计算近似最终稳定下来的极限。它把"图灵跳跃"和"机器学习里的 PAC 收敛"在精神上联系起来——你永远不知道何时收敛了，但你知道最终会收敛。

0' 之间的几何

把上面两件事合起来：r.e. 度集既稠密、又有极限刻画，还有不可比的元素、不可数的"度链"。它形成了一个极其复杂的偏序拓扑。今天关于"r.e. 度格的初等理论"是否可判定，仍是开放问题——这是不可判定性研究自身的深层结构所滋生的元层级问题。

八、几个常见误区

误区 1："Oracle 让不可计算变可计算"

不准确。Oracle 让对应那一层的不可计算变可计算。但 oracle 自己所在那一层之上的问题，仍然不可解。Oracle 不是"上帝"，只是"上一层的图灵机"——你永远爬不到顶（顶根本不存在）。

误区 2："图灵度是离散阶梯"

错。它有阶梯（0', 0'', …），但更复杂的格结构（不可比的度、稠密性、无穷下降链等）让它远比阶梯丰富。事实上，r.e. 度集是稠密的（任两个 r.e. 度之间都有第三个）。

误区 3："实际计算用不到 oracle"

表面是。但现代密码学、神经网络分析、机器学习理论中，"假设有一个 X-oracle 能 ……"是非常常见的论证手段（例如假设 SAT-oracle、假设量子 oracle）。Oracle 是把问题分层、模块化的关键工具。

误区 4："优先级论证太抽象，没用"

错。它是现代递归论的"代数几何"——优先级方法的发明，让 r.e. 度结构、可计算函数族、算法学习理论等领域都成为可研究对象。它的影响还在扩散。

九、结语：黑暗中的光谱

不可计算性曾是计算理论的"边界"——一旦撞上这堵墙，故事就结束了。Post 用一个简单想法颠覆这种悲观：越过墙之后还有世界。Oracle 图灵机让我们能"假装"获得不可计算的信息，看看下一步能算什么；图灵归约让我们衡量问题之间的相对难度；图灵度把所有不可计算性组织成有结构的格。

下一章我们会看到，这套结构最让人惊叹的应用——自我指涉。停机问题的对角线、Rice 定理的归约、Gödel 不完备的自我引用、Y 组合子的不动点——它们都是同一个深层结构的不同显现。计算理论的真正秘密，藏在"程序能否谈论自己"这个问题里。

Oracle 没有让我们逃出"可计算"的牢笼——但它让我们看清牢笼的立体形状，看清牢笼之外那座无尽的金字塔。这就是数学最美的姿态：当你以为撞上终极障碍时，它告诉你障碍背后还有结构，而结构里还有故事，而故事尚未结束。