极限可计算函数 | Codeboy's Blog

形式陈述

总函数 $f:\mathbb N^k\to\mathbb N$ 称为极限可计算，若存在总可计算函数

g:\mathbb N^k\times\mathbb N\to\mathbb N

使对每个输入 $\vec x$ ，存在阶段 $s_0$ 满足

\forall s\ge s_0\qquad g(\vec x,s)=f(\vec x).

写作 $f(\vec x)=\lim_s g(\vec x,s)$ 。因为值域是离散的自然数，“极限存在”在这里就是最终恒定；每个输入允许自己的稳定阶段，定义不要求存在统一 $s_0$ ，也不要求从 $\vec x$ 可计算出稳定阶段。 $g$ 称为 $f$ 的可计算近似，值发生改变称一次 mind change。

集合 $A\subseteq\mathbb N$ 极限可计算，是指特征函数 $\chi_A$ 有取值于 $\{0,1\}$ 的这种近似。相对于预言机 $D$ 的版本把 $g$ 改为 $D$ -可计算；其余量词不变。若只给部分近似、只保证某个子序列收敛，或允许输出在极限处无定义，就得到别的函数类，本页不采用这些变体。

直觉

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

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

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

例子与边界

固定可接受编号，令 $K=\{e:\varphi_e(e)\downarrow\}$ 。定义

g(e,s)= \begin{cases} 1,&\varphi_e(e)\text{ 在至多 }s\text{ 步内停机},\\ 0,&\text{否则}. \end{cases}

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

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

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

h(e,s)= \begin{cases} s\bmod 2,&\varphi_e(e)\text{ 在 }s\text{ 步内尚未停机},\\ 0,&\varphi_e(e)\text{ 已在 }s\text{ 步内停机}. \end{cases}

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

推论与应用

Shoenfield 极限定理证明：总函数极限可计算当且仅当它可由 $0'$ 计算；对集合而言，这正是 $\Delta^0_2$ 。该定理说明无限修订没有随意突破可计算层级，而是精确对应一次停机预言机。相对版本把 $0'$ 换成 $D'$ ，使阶段逼近可以在任意 oracle 基准上迭代。

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

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

参考资料

Joseph R. Shoenfield, “On Degrees of Unsolvability,” Annals of Mathematics 69(3), 1959, pp. 644–653，Limit Lemma 及其一致化形式。
Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer, 1987，Chapter III，computable approximations and the Limit Lemma。
S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, 2004，章节 “Computable Approximations and the Limit Lemma”。

形式陈述 ​

反向链接

形式陈述