极限可计算函数

普通算法必须在某个可观察时刻交付最终答案；极限算法可以不断发布修订稿，只承诺每一项最终不再变化。使用者无法仅凭当前值知道这是最后一版，因为稳定时刻本身可能编码不可计算信息。因而“每项终会猜对”不等于“有办法等到确定猜对”。

阶段参数 $s$ 可理解为目前允许的计算时间与已发现证据量。若新证据只会加入而不会撤销，某些近似是单调的；一般极限近似却可来回改口任意有限次，而且不同输入的改口次数可以没有统一可计算上界。关键约束是逐点有限，而不是整个无限表在某一共同阶段全部冻结。

若另有总可计算函数 $m(\overrightarrow{x})$ 保证 $s\ge m(\overrightarrow{x})$ 时已经稳定，那么直接计算 $g(\overrightarrow{x},m(\overrightarrow{x}))$ 就得到 $f$；这会把极限可计算退化为普通可计算。极限模型增加的能力恰好藏在“稳定但无有效收敛模”这一处，而不是藏在每个阶段的计算里——每个 $g(\cdot ,s)$ 都完全有效。

固定可接受编号理路程序编号与可接受编号Program indexing · Acceptable numbering · Gödel numbering对部分可计算函数进行有效枚举，并要求编号支持通用解释与有效参数编译。，令 $K=\{e:{\phi }_e(e)\downarrow \}$。定义

有限步模拟使 $g$ 总可计算。若程序永不停机，序列恒为 $0$；若它在第 $t$ 步停机，序列从阶段 $t$ 起恒为 $1$。所以 $\underset{s}{lim}g(e,s)={\chi }_K(e)$，每项至多改口一次。$K$ 不可计算，因此这是“极限可计算严格强于可计算”的实际见证。

补集 $\bar{K}$ 也有近似 $1-g(e,s)$：先猜“不停机”，发现停机证据后改成 $0$。注意这个过程不会在真不停止的程序上收到确认；它仍靠极限语义得到正确特征值，并没有成为余停机问题的普通判定器。

边界在稳定性。定义总可计算函数

若 ${\phi }_e(e)$ 永不停机，$h(e,s)$ 就无限振荡，因而不存在自然数值极限；若程序停机，序列才会在有限次变化后稳定为 $0$。若只要求实数意义上的数值收敛，$1/s$ 可以不断变化仍趋于 $0$；自然数离散值域下则不允许这种现象。概率算法“错误概率趋零”也不等于这里的逐输入最终恒定，除非先指定一条确定随机序列并证明实际输出最终不变。

与普通总可计算函数理路可计算函数Computable function · Recursive function有图灵机对每个合法输入都停机并输出其值的全函数。相比，极限可计算函数允许不能有效识别的最后一次改口。每个普通可计算 $f$ 都可取恒定近似 $g(x,s)=f(x)$；上面的 ${\chi }_K$ 则证明反向不成立。两类对象都是总函数理路函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。，差别在取得值的有效方式，不能把极限过程当作一台最终输出并停机的普通判定器。

Shoenfield 极限定理证明：总函数极限可计算当且仅当它可由 $0^{\prime }$ 计算；对集合而言，这正是 ${\mathrm{\Delta }}_2^0$。因此，逐点最终稳定的计算能力精确对应一次停机预言机。相对版本把 $0^{\prime }$ 换成 $D^{\prime }$，使阶段逼近可以在任意 oracle 基准上迭代。

极限近似是优先构造的日常语言。构造 c.e. degree 或 low 集时，研究者在阶段 $s$ 维护有限近似，允许高优先级要求使低优先级策略改口，再证明每个给定要求只受有限次伤害。这里的“有限伤害”给出逐项稳定，不一定给出可计算的最后伤害时刻；这正吻合定义。

限制 mind change 次数会得到差分层级中的 $n$-c.e. 集：从 $0$ 开始、每个输入最多改变 $n$ 次。所有这类集合都极限可计算，但一般 ${\mathrm{\Delta }}_2^0$ 集未必有任何固定有限的全局改口上界。另一方面，迭代极限运算可刻画更高 ${\mathrm{\Delta }}_n^0$ 层；每次迭代都必须保留“所有内层极限存在”的条件，不能把多个未收敛猜测机械嵌套。