更改

==== SRT 与计算复杂性理论 ====

==== SRT 与计算复杂性理论 ====

在[[复杂性理论]]中，递归定理主要扮演'''证明工具'''的角色。[[复杂性类]]的许多分离与结构定理采用"带时钟的对角化"：让机器检查并躲开自己（或更早的机器）的行为；当这种自躲藏需要程序援引自己的代码时，严格化的抓手正是 SRT。Breidbart 的"[[分裂递归集]]"构造显式调用递归定理，是这一路数的源头<ref name="breidbart1978">'''Breidbart, S. (1978).''' ''On splitting recursive sets''. Journal of Computer and System Sciences 17: 56–64.【复杂性类对角化中显式使用递归定理的"延迟构造"源头】</ref>；Schmidt 进一步把这类论证统一为"[[复杂性类的递归论结构]]"定理，其推论包括：除非 [[NP = P]]，[[NP]] 不等于 [[P]] 与 NP 完全类之并这类"[[可递归呈现类]]"的非平凡并<ref name="schmidt1985">'''Schmidt, D. (1985).''' ''The recursion-theoretic structure of complexity classes''. Theoretical Computer Science 38: 143–156. doi:10.1016/0304-3975(85)90217-8.【复杂性类对角化定理的递归论统一；推论：除非 NP=P，NP ≠ P ∪ {[[NP完全类]]}】</ref>。

在[[复杂性理论]]中，递归定理主要扮演'''证明工具'''的角色。[[复杂性类]]的许多分离与结构定理采用"带时钟的对角化"：让机器检查并躲开自己（或更早的机器）的行为；当这种自躲藏需要程序援引自己的代码时，严格化的抓手正是 SRT。这类证明有一个内禀的时序难题：对角化机器要躲开的对象可能就是它自己（或自己的更早版本），而它必须在对方"提交行为"之后才能可靠地反着做——处理这一难题的技术称为'''延迟对角化'''（delayed diagonalization），其源头是 Breidbart 的"[[分裂递归集]]"构造显式调用递归定理<ref name="breidbart1978">'''Breidbart, S. (1978).''' ''On splitting recursive sets''. Journal of Computer and System Sciences 17: 56–64.【复杂性类对角化中显式使用递归定理的"延迟构造"源头】</ref>；其思想后来被 Schmidt 统一为"[[复杂性类的递归论结构]]"定理，推论包括：除非 [[NP = P]]，[[NP]] 不等于 [[P]] 与 NP 完全类之并这类"[[可递归呈现类]]"的非平凡并<ref name="schmidt1985">'''Schmidt, D. (1985).''' ''The recursion-theoretic structure of complexity classes''. Theoretical Computer Science 38: 143–156. doi:10.1016/0304-3975(85)90217-8.【复杂性类对角化定理的递归论统一；推论：除非 NP=P，NP ≠ P ∪ {NP完全类}】</ref>。延迟对角化由此成为分离复杂性类的标准武器——本质上，它是"带时钟的对角线"对自引用时序的形式化处理。

在[[曼纽尔·布卢姆|Blum]]的机器无关复杂性理论中，SRT 与对角化结合产生了一批"存在性"结果。代表性的一例：Helm 与 Young 回答了 Blum 的一个问题——存在这样的可计算函数，任何为它"换上更快的程序"的尝试都要付出程序尺寸爆炸的代价，且刻画这一代价的增长函数快于任何递归函数<ref name="helmyoung1971">'''Helm, J.; Young, P. (1971).''' ''On size vs. efficiency for programs admitting speed-ups''. Journal of Symbolic Logic 36.【回答 Blum 的问题：加速必然伴随尺寸爆炸，代价函数增长快于任何递归函数】</ref>。"加速与简洁不可兼得"由此成为定理而非格言。

在[[曼纽尔·布卢姆|Blum]]的机器无关复杂性理论中，SRT 与对角化结合产生了一批"存在性"结果。代表性的一例：Helm 与 Young 回答了 Blum 的一个问题——存在这样的可计算函数，任何为它"换上更快的程序"的尝试都要付出程序尺寸爆炸的代价，且刻画这一代价的增长函数快于任何递归函数<ref name="helmyoung1971">'''Helm, J.; Young, P. (1971).''' ''On size vs. efficiency for programs admitting speed-ups''. Journal of Symbolic Logic 36.【回答 Blum 的问题：加速必然伴随尺寸爆炸，代价函数增长快于任何递归函数】</ref>。"加速与简洁不可兼得"由此成为定理而非格言。

更微妙的是，我们能否把 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">'''Kjos-Hanssen, B.; Merkle, W.; Stephan, F. (2011).''' ''Kolmogorov complexity and the recursion theorem''. Transactions of the American Mathematical Society 363(10): 5465–5480. doi:10.1090/S0002-9947-2011-05306-7.【SRT 相对化失效的刻画：A 能计算 DNR 函数 ⟺ A autocomplex；会议版为 STACS 2006, LNCS 3884, 149–161】</ref>

'''工具一：[[Kolmogorov复杂性]]与[[DNR度]]。'''相对化之后 SRT 何时失效，有一个精确刻画：<math>A</math> 能算 DNR 函数当且仅当 <math>A</math> 是 [[autocomplex]] 的<ref name="kjos2011">'''Kjos-Hanssen, B.; Merkle, W.; Stephan, F. (2011).''' ''Kolmogorov complexity and the recursion theorem''. Transactions of the American Mathematical Society 363(10): 5465–5480. doi:10.1090/S0002-9947-2011-05306-7.【SRT 相对化失效的刻画：A 能计算 DNR 函数 ⟺ A autocomplex；会议版为 STACS 2006, LNCS 3884, 149–161】</ref>。换个角度看，这条定理把"自指是否可用"从一个全有全无的定性事实，变成了一个由环境（oracle）标定的'''可测量、可分级、可缺失'''的复杂性量——DNR 度的层级就是"自指损坏程度"的标尺。

。换个角度看，这条定理把"自指是否可用"从一个全有全无的定性事实，变成了一个可以'''测量、分级、缺失'''的复杂性量——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" />。

 

'''工具三（工程终点）：哥德尔机。'''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 可以被分级 ====

该词条表述的SRT默认在一个'''[[可接受编号]]'''（acceptable numbering，即同时满足通用性与[[s-m-n定理]]的编号系统）中工作；在此类编号之间，[[#Rogers 同构定理（1958）|Rogers同构]]保证了彼此可计算互译。一个自然的追问是：'''换掉编号，递归定理还剩多少？'''

该词条表述的 SRT 默认在一个'''[[可接受编号]]'''（acceptable numbering，即同时满足通用性与[[s-m-n定理]]的编号系统）中工作；在此类编号之间，[[#Rogers 同构定理（1958）|Rogers同构]]保证了彼此可计算互译。一个自然的追问是：'''换掉编号，递归定理还剩多少？'''

答案分两层。其一，Rogers 不动点形式（表述 B）对一切可接受编号成立；但在'''一般的可计算编号'''（同样是全部一元偏可计算函数的一致枚举、却不满足可接受性的编号）中，'''Kleene 形式（表述 A，文献中称 KRT）可以失效'''。其二，失效与否不是全有全无的：Case、Jain 与 Stephan 借用归纳推断的收敛标准，把"在编号 <math>\psi</math> 中找到不动点"分成了由强到弱的四档——'''FinKrt'''（有限步内机械给出不动点）、'''ExKrt'''（极限收敛地找到）、'''VacKrt'''（摇摆式收敛）、'''BcKrt'''（行为正确地收敛），并系统研究了哪些编号落在哪一档<ref name="case2018">'''Case, J.; Jain, S.; Stephan, F. (2018).''' ''Effectivity questions for Kleene's recursion theorem''. Theoretical Computer Science 733: 55–70. doi:10.1016/j.tcs.2018.04.036.【KRT 对编号系统的依赖性：FinKrt/ExKrt/VacKrt/BcKrt 分级；KRT 找不动点能力与学习最优性独立】</ref>。

答案分两层。其一，Rogers 不动点形式（表述 B）对一切可接受编号成立；但在'''一般的可计算编号'''（同样是全部一元偏可计算函数的一致枚举、却不满足可接受性的编号）中，'''Kleene 形式（表述 A，文献中称 KRT）可以失效'''。其二，失效与否不是全有全无的：Case、Jain 与 Stephan 借用归纳推断的收敛标准，把"在编号 <math>\psi</math> 中找到不动点"分成了由强到弱的四档——'''FinKrt'''（有限步内机械给出不动点）、'''ExKrt'''（极限收敛地找到）、'''VacKrt'''（摇摆式收敛）、'''BcKrt'''（行为正确地收敛），并系统研究了哪些编号落在哪一档<ref name="case2018">'''Case, J.; Jain, S.; Stephan, F. (2018).''' ''Effectivity questions for Kleene's recursion theorem''. Theoretical Computer Science 733: 55–70. doi:10.1016/j.tcs.2018.04.036.【KRT 对编号系统的依赖性：FinKrt/ExKrt/VacKrt/BcKrt 分级；KRT 找不动点能力与学习最优性独立】</ref>。

这带来一个概念上的反转：自指不再是"图灵等价世界"里的免费午餐，而是'''编号系统的一种资源'''，可以测量、可以分级、可以缺失。该文还证明了两个结构性事实：①一个编号"找不动点的能力"与它"作为学习最优假设空间的能力"相互独立；②若编号既对解释性学习最优、又在 Ex 意义下满足 KRT，则它还能在 Ex 意义下翻译其他编号的指标。这与正文 §5.1 的"表述 C"形成呼应——uniform 性与可构造性本身，就是递归定理 content 中最脆弱也最值钱的部分。

这带来一个概念上的反转：自指不再是"图灵等价世界"里的免费午餐，而是'''编号系统的一种资源'''。与上一小节的 DNR 刻画合观，结论是对称的：环境（oracle）与编码（编号）两个维度中任何一个被放宽，自指都可能失效，而失效的程度都可以被测量与分级。该文还证明了两个结构性事实：①一个编号"找不动点的能力"与它"作为学习最优假设空间的能力"相互独立；②若编号既对解释性学习最优、又在 Ex 意义下满足 KRT，则它还能在 Ex 意义下翻译其他编号的指标。这与正文 §5.1 的"表述 C"形成呼应——uniform 性与可构造性本身，就是递归定理中最脆弱也最值钱的部分。

== 评注与影响 ==

== 评注与影响 ==