Shoenfield 极限定理

$0^{\prime }$ 能回答“某个搜索以后还会不会成功”这一类存在性问题。给定近似的当前值，询问未来是否还会变化，就是一个可识别事件：可以逐阶段寻找首个反例。停机预言机可以判定这个搜索最终有无结果，于是能够找到真正的最后版本。

反方向中，$0^{\prime }$ 的有限计算只查看有限多个 oracle 位。把 $0^{\prime }$ 用“目前已经发现的停机程序”逐阶段逼近，某次计算可能因尚未发现的正例而暂时走错；但对固定输入，真实停机计算只涉及有限查询，这些位最终全部稳定。此后足够长的有界模拟便重复同一条正确轨迹。无限 oracle 被压缩成了每个输入上的有限、但事先不知道何时可靠的信息。

两边的关键都不是把 $0^{\prime }$ 当作一个瞬间可见的无限表。正向证明用它逐次决定未来变化，反向证明只依赖实际计算的有限 use。若省略有限 use，就无法从 oracle 的逐位收敛推出整段计算稳定；若假设可计算地知道最后变化阶段，又会把结论错误加强成普通可计算性。

先从近似推出 $0^{\prime }$-算法。给定总可计算 $g(x,s)$，固定 $x,s$ 后考察谓词

$E$ 是 c.e.：逐个计算 $t>s$ 的值即可寻找一次变化。用参数化定理理路s-m-n 定理s-m-n theorem · Parameter theorem把程序的部分输入有效固化为新程序索引的参数化定理。把 $x,s$ 写入这段搜索程序，得到一个停机实例，所以 $0^{\prime }$ 能判定它。依次试 $s=0,1,2,\dots$，首个满足 $\mathrm{\neg }E(x,s)$ 的阶段一定存在，输出 $g(x,s)$ 即为极限。这个算法不靠猜测一个全局收敛速率。

反过来设 $f(x)={\mathrm{\Phi }}_e^{0^{\prime }}(x)$ 且对每个 $x$ 停机。令 $K_s=\{e\le s:{\mathrm{\Phi }}_e^{\varnothing }(e)\text{ 在至多 }s\text{ 步内停机}\}$，并定义 $g(x,s)$：用 $K_s$ 作临时 oracle，模拟 ${\mathrm{\Phi }}_e(x)$ 至多 $s$ 步；若停机则取其输出，否则输出 $0$。真实计算对固定 $x$ 只询问有限多个数。所有真实“是”答案最终进入 $K_s$，真实“否”答案永不进入；当这些位和运行时间都被阶段覆盖后，$g(x,s)$ 永远等于 $f(x)$。

总性假设不可省略。若 ${\mathrm{\Phi }}_e^{0^{\prime }}(x)$ 在某些输入发散，上述默认输出 $0$ 的近似仍可能收敛，却会把“无定义”误写成函数值；部分函数版本必须用带发散语义的另外表述。近似也无需单调，甚至可有限次往返；Shoenfield 定理保证最终稳定，不保证每项只改一次。最后，${\mathrm{\Delta }}_2^0$ 结论针对集合的特征函数，不能把任意 ${\mathrm{\Sigma }}_2^0$ 集自动称为 limit computable。

定理把 ${\mathrm{\Delta }}_2^0$ 的三种常用定义接在一起：双重算术定义、$0^{\prime }$-可计算性与可计算稳定逼近。因此在有效阶段构造里，若阶段特征函数 $a(x,s)\in \{0,1\}$ 是总可计算的，并且对每个 $x$ 最终稳定到 ${\chi }_A(x)$，就立刻得到上界 $A{\le }_T{0}^{\prime }$；反过来，任何低于 $0^{\prime }$ 的集合都有这样的统一可计算近似。仅证明某列猜测逐点稳定而不证明 $(x,s)\mapsto a(x,s)$ 可计算，并不足以应用本定理。

相对版本是有限伤害优先法的基础。以 $D$ 为背景信息构造对象时，允许 $D$-可计算的阶段策略；最终对象恰落在 $D^{\prime }$ 以下。多次相对化得到 $A{\le }_T{0}^{(n)}$ 与 $0^{(n-1)}$-可计算近似之间的对应，并和 Post 定理的 ${\mathrm{\Delta }}_{n+1}^0$ 刻画吻合。

极限定理也提供错误检查：若有人声称一个 $0^{\prime }$-可计算函数只有“越来越接近”却不最终恒定的整数近似，他尚未给出本定理要求的见证；若给出了可计算稳定模，则函数其实无需 $0^{\prime }$。在算法学习与 trial-and-error computation 中，可以借用这种修订直觉，但只有输入、阶段、总性和逐点稳定量词完全一致时，结论才真的是 Shoenfield 极限定理。