3,094
个编辑
更改
跳到导航
跳到搜索
第389行：
第389行： + + + + + + + +
→算子递归定理（ORT）：无穷互引的程序族
ORT 可以由第二递归定理推出，因此二者在经典可计算性理论中等价；但 ORT 的表达形式在[[归纳推断]]（algorithmic learning theory，Gold 风格的可学习性理论）中远为顺手——从 Blum 与 Blum 1975 年的奠基工作起，学习理论中需要自指构造的证明几乎都以 ORT 为标准引用形式<ref name="case1974" /><ref name="case1994">'''Case, J. (1994).''' ''Infinitary self-reference in learning theory''. Journal of Experimental and Theoretical Artificial Intelligence 6(1): 3–16.【ORT 在学习理论中用法的教学性综述】</ref>。Case 本人后来写了一篇教学性综述，用"程序先制造自身的静默副本再运行给定的使用方案"的意象讲解无穷自指的用法<ref name="case1994" /><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>。
ORT 可以由第二递归定理推出，因此二者在经典可计算性理论中等价；但 ORT 的表达形式在[[归纳推断]]（algorithmic learning theory，Gold 风格的可学习性理论）中远为顺手——从 Blum 与 Blum 1975 年的奠基工作起，学习理论中需要自指构造的证明几乎都以 ORT 为标准引用形式<ref name="case1974" /><ref name="case1994">'''Case, J. (1994).''' ''Infinitary self-reference in learning theory''. Journal of Experimental and Theoretical Artificial Intelligence 6(1): 3–16.【ORT 在学习理论中用法的教学性综述】</ref>。Case 本人后来写了一篇教学性综述，用"程序先制造自身的静默副本再运行给定的使用方案"的意象讲解无穷自指的用法<ref name="case1994" /><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>。
==== 自指的可用性依赖于编号系统：KRT 可以被分级 ====
该词条表述的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" />。
这带来一个概念上的反转：自指不再是"图灵等价世界"里的免费午餐，而是'''编号系统的一种资源'''，可以测量、可以分级、可以缺失。该文还证明了两个结构性事实：①一个编号"找不动点的能力"与它"作为学习最优假设空间的能力"相互独立；②若编号既对解释性学习最优、又在 Ex 意义下满足 KRT，则它还能在 Ex 意义下翻译其他编号的指标。这与正文 §5.1 的"表述 C"形成呼应——uniform 性与可构造性本身，就是递归定理 content 中最脆弱也最值钱的部分。
=== 推论：SRT 衍生出的若干重要结果 ===
=== 推论：SRT 衍生出的若干重要结果 ===