3,094
个编辑
更改
跳到导航
跳到搜索
第748行：
第748行： − − ===其它扩展研究=== − − ====SRT与计算复杂性==== − − − ==== 自指的可用性依赖于编号系统：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 中最脆弱也最值钱的部分。 第830行：
第817行： + + + + + + + + + + + + + + + + +
→其它扩展研究
'''证明中 SRT 的关键一步'''：想把任意 r.e. 集 B 归约到创造集 A，需要构造一个程序 <math>z</math>，使得"若 <math>x\in B</math>，则 <math>z</math> 枚举出<math>\{u(z)\}</math>；否则 <math>z</math> 枚举空集"——'''<math>z</math> 的定义里用到了 <math>z</math> 自己的编号'''（<math>u(z)</math> 是生产反例的程序作用于 <math>z</math>）。这正是 SRT 合法化的自指；没有这个自指，证明无法闭合。由此 Rogers 还得到推论：'''所有创造集在"可计算的重新命名"意义下完全相同（两两递归同构）'''——从可计算性角度看它们"长得一模一样"<ref name="rogers1967" />。
'''证明中 SRT 的关键一步'''：想把任意 r.e. 集 B 归约到创造集 A，需要构造一个程序 <math>z</math>，使得"若 <math>x\in B</math>，则 <math>z</math> 枚举出<math>\{u(z)\}</math>；否则 <math>z</math> 枚举空集"——'''<math>z</math> 的定义里用到了 <math>z</math> 自己的编号'''（<math>u(z)</math> 是生产反例的程序作用于 <math>z</math>）。这正是 SRT 合法化的自指；没有这个自指，证明无法闭合。由此 Rogers 还得到推论：'''所有创造集在"可计算的重新命名"意义下完全相同（两两递归同构）'''——从可计算性角度看它们"长得一模一样"<ref name="rogers1967" />。
==== 有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理 ====
==== 有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理 ====
（表中"§"编号均指 Moschovakis 2010<ref name="moschovakis2010" /> 的章节。）
（表中"§"编号均指 Moschovakis 2010<ref name="moschovakis2010" /> 的章节。）
===其它扩展研究===
=== 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>。
在[[曼纽尔·布卢姆|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 年的直接证明不经过通用程序，所以某些没有通用程序的子递归系统仍保有递归定理。一句话主旋律：'''自指免费，高效自指昂贵'''——不动点的"存在"有保证，"存在得节省"没有。
==== 自指的可用性依赖于编号系统：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 中最脆弱也最值钱的部分。
== 评注与影响 ==
== 评注与影响 ==