3,094
个编辑
更改
跳到导航
跳到搜索
第826行：
第826行： + + + + + + + + + + +
→SRT 与计算复杂性理论
更微妙的是，我们能否把 SRT本身复杂性化？如果把编号限制到多项式时间的程序族上，SRT 还成立吗？困难出在证明的两个枢纽操作上：通用模拟在 P-时间世界里没有多项式时间版本（万能解释器本身要超线性时间），s-m-n 实例化（把参数写死）也会放大运行时间。因此对一般的多项式时间编号，'''带时间界的 SRT 不成立'''；不过 Kleene 1938 年的直接证明不经过通用程序，所以某些没有通用程序的子递归系统仍保有递归定理。
更微妙的是，我们能否把 SRT本身复杂性化？如果把编号限制到多项式时间的程序族上，SRT 还成立吗？困难出在证明的两个枢纽操作上：通用模拟在 P-时间世界里没有多项式时间版本（万能解释器本身要超线性时间），s-m-n 实例化（把参数写死）也会放大运行时间。因此对一般的多项式时间编号，'''带时间界的 SRT 不成立'''；不过 Kleene 1938 年的直接证明不经过通用程序，所以某些没有通用程序的子递归系统仍保有递归定理。
==== 存在性与可构造性的分野====
经典表述下，第二递归定理的"存在性"部分——不动点存在且可计算——对一切可接受编号成立，且这一保证不附带任何资源代价。然而上一小节的"自指免费，高效自指昂贵"提示了一个更深的问题：'''一旦要求不动点在资源有界的系统（如多项式时间编号）中可构造，定理的哪些部分存活、哪些失效？'''答案是一个干净的分野：'''存在性原封不动地活着；可构造性一旦要求资源有界，就会在子递归系统中部分失效。'''而有意思的是，这片"失效地带"并非荒芜之地——为了刻画它，递归论与复杂性理论交叉出三种新工具。
'''工具一：Kolmogorov 复杂性与 DNR 度。'''相对化之后 SRT 何时失效，上一节已给出精确刻画：<math>A</math> 能算 DNR 函数当且仅当 <math>A</math> 是 autocomplex 的<ref name="kjos2011" />。换个角度看，这条定理把"自指是否可用"从一个全有全无的定性事实，变成了一个可以'''测量、分级、缺失'''的复杂性量——DNR 度的层级就是"自指损坏程度"的标尺。
'''工具二：延迟对角化（delayed diagonalization）。'''复杂性类分离证明中有一个内禀的时序难题：对角化机器要躲开的对象可能就是它自己（或自己的更早版本），而它必须在对方"提交行为"之后才能可靠地反着做。Breidbart 的分裂递归集构造把递归定理的延迟技术引入这类证明<ref name="breidbart1978" />，其思想被 Schmidt 统一为"复杂性类的递归论结构"定理<ref name="schmidt1985" />。延迟对角化由此成为分离复杂性类的标准武器——本质上，它是"带时钟的对角线"对自引用时序的形式化处理。
'''工具三（工程终点）：哥德尔机。'''Schmidhuber 把"资源有界的自引用"推到了最雄心勃勃的形式<ref name="schmidhuber2003">'''Schmidhuber, J. (2003).''' ''Gödel machines: self-referential universal problem solvers making provably optimal self-improvements''. arXiv:cs/0309048【正式版本见 LNCS 3394 (2005), 1–23 及 Springer《Artificial General Intelligence》(2006)；IDSIA 技术报告 IDSIA-19-03】</ref>：机器的初始代码包含自身硬件、环境、效用函数乃至整个初始软件的公理化描述，一个基于 Levin 通用搜索的偏置最优证明搜索器（BIOPS）持续寻找证明——'''一旦证明某个对自身代码的改写能提升未来效用，就立即改写（包括改写证明搜索器本身）'''。由于改写前必须证明"继续搜索其他改写不值当"，每次自改进都是全局最优的，没有局部极值。它的边界同样是哥德尔式的：只能改写"在形式系统内可证明有用"的部分，超出可证明范围的好处再大也拿不到。这条工程谱系与上文的[[#自省程序与自省式自改进程序|自省程序]]一脉相承：自省程序"知道自己的有界执行轨迹"，哥德尔机则"能证明地改写自己的任何部分"——自指从存在性工具，最终长成了资源有界的自改进机制<ref name="zhang2026" />。
==== 自指的可用性依赖于编号系统：KRT 可以被分级 ====
==== 自指的可用性依赖于编号系统：KRT 可以被分级 ====