Turing 跳跃

把 $A$ 想成已经装进机器的可靠问答器。机器虽然能免费询问 $A$，仍无法普遍预言所有“使用 $A$ 的程序”会不会停机；$A^{\prime }$ 正好收集这些新停机问题。跳跃于是把“手上已有的信息”变成“关于使用这些信息的全部程序行为”的下一层问题。每向上跳一次，观察者的语言不变，能够作为原子答案使用的停机事实却多一层。

严格性来自相对化的对角论证，而不是 $A$ 本身有多复杂。即使 $A$ 已经不可计算，假定某台 $A$-预言机能判定 $A^{\prime }$，仍可制造一台在判定器说“会停机”时循环、说“不会停机”时立即停机的 $A$-程序，再把自己的索引代入，得到同一个矛盾。因此不存在“足够难便对自身跳跃封闭”的集合。

另一方面，$A{\le }_T{A}^{\prime }$ 不是因为 $A$ 被字面包含在 $A^{\prime }$ 中。对每个 $x$，可以有效生成程序 $P_x^A$：它只询问 $x\in A$，答案为真便停机，否则循环。$s$-$m$-$n$ 定理公理库s-m-n 定理s-m-n theorem · Parameter theorem把程序的部分输入有效固化为新程序索引的参数化定理。把 $x$ 固化进程序并给出索引 $e_x$；查询 $e_x\in A^{\prime }$ 就恢复 $x\in A$。这里用的是统一索引变换，而非集合包含。

取 $A=\varnothing$。因为预言机永远回答“否”，${\mathrm{\Phi }}_e^{\varnothing }$ 可由普通程序模拟，故 $0^{\prime }$ 与对角停机集 $K=\{e:{\mathrm{\Phi }}_e(e)\downarrow \}$ 同 degree。给定输入 $x$，构造“模拟第 $x$ 个程序在 $x$ 上运行”的机器，其索引可计算地产生；询问这个索引是否属于 $0^{\prime }$，便判定对应停机实例。反过来若普通机器能判定 $0^{\prime }$，令

并考察 $D$ 自身索引，就得到 $D(d)\downarrow ⟺D(d)\uparrow$。同一机制在任意 $A$ 上原样成立，证明 $A^{\prime }{\nleqq }_{T}A$。

第一跳的量词可直接从执行轨迹读出：$e\in 0^{\prime }$ 当且仅当存在步数 $s$，使程序 $e$ 在输入 $e$ 上于 $s$ 步内停机。固定 $e,s$ 后，有限模拟能判定这个条件，所以它是 ${\mathrm{\Sigma }}_1^0$ 公式；补集则要求每个 $s$ 都没有停机。无界的“存在某一步”和“所有步都没有”正是两种不同的终止义务。

字面上的 $A^{\prime }$ 依赖编号：换一套可接受编号会改变哪些自然数充当程序代码，但不会改变其 Turing degree。若编号不支持通用解释和有效参数化，对角集合仍可写下，却未必具有上述统一性；这正是可接受编号假设不可删除的原因。

跳跃也不是补集运算。$A$ 与 $\bar{A}$ 总是 Turing 等价，因而 $A^{\prime }{\equiv }_T(\bar{A}{)}^{\prime }$；但 $A^{\prime }$ 记录相对停机，通常既非 $A$ 的补集，也非把 $A$ 添入某个固定停机集的普通并集。本页只讨论有限迭代；到极限序数时必须另外给出有效序数记号与 join 约定，不能把 $A^{(\omega )}$ 当作有限递推式的一个普通下一项。

跳跃给不可计算性提供一把可反复校准的尺。Turing degree公理库Turing degreeTuring degree · Degree of unsolvability · 图灵度按双向 Turing 可归约把集合分成等价类，并用归约偏序比较它们携带的不可计算信息。上的 jump 把 $\mathbf{a}=[A]$ 送到 ${\mathbf{a}}^{\prime }=[A^{\prime }]$；其良定义性来自 $A{\equiv }_{T}B\Rightarrow A^{\prime }{\equiv }_T{B}^{\prime }$，严格性则给出 $\mathbf{a}<{\mathbf{a}}^{\prime }$。low 与 high 性质比较的不是 $A$ 自身是否容易枚举，而是 $A^{\prime }$ 相对于 $0^{\prime }$、$0^{″}$ 落在哪里。

有限跳跃还把机器模型接到可定义性。对 $n\ge 1$，$0^{(n)}$ 是 ${\mathrm{\Sigma }}_n^0$ 的 many-one 完全集。Post 定理准确写成

${\mathrm{\Sigma }}_n^0$ 指可由以存在量词块开头、至多 $n$ 个交替量词块及可计算矩阵定义的集合；${\mathrm{\Pi }}_n^0$ 从全称量词开头，${\mathrm{\Delta }}_n^0={\mathrm{\Sigma }}_n^0\cap {\mathrm{\Pi }}_n^0$。不能把“第 $n$ 层完备”理解成同时在 $\mathrm{\Sigma }$、$\mathrm{\Pi }$ 两侧完备，也不能把相对可枚举误写成相对可判定。

Shoenfield 极限定理在第一跳处给出另一种表示：一个集合可由 $0^{\prime }$ 计算，当且仅当其特征函数有逐点最终稳定的可计算近似。每个输入最终稳定，不要求存在可计算的时刻告诉我们何时不再变化。

在相对化证明中，跳跃也是检查结论强度的试纸。若某论证声称只把 $A$ 当黑盒，却能由 $A$ 决定 $A^{\prime }$，相对对角化立即指出它遗漏了非一致步骤、额外参数或不合法的无限信息。这个用途不要求真的实现不可计算预言机；模型的价值正是隔离“允许哪些答案”之后仍不可跨越的界限。