3,094
个编辑
更改
→Smullyan双递归定理
另外，值得一提的是，这个双递归定理以及对应的n递归定理的推广形式，实际上可以看成是多个部分互相指涉，互相依赖的形式，因此也就构成了[[自创生理论]]（Autopoesis）的数学基础。
另外，值得一提的是，这个双递归定理以及对应的n递归定理的推广形式，实际上可以看成是多个部分互相指涉，互相依赖的形式，因此也就构成了[[自创生理论]]（Autopoesis）的数学基础。
==== 算子递归定理（ORT）：无穷互引的程序族 ====
'''算子递归定理'''（operator recursion theorem，简称 ORT）是第二递归定理的"无穷化"推广，由[[约翰·凯斯|Case]]在研究自复制自动机时提出<ref name="case1974">'''Case, J. (1974).''' ''Periodicity in generations of automata''. Mathematical Systems Theory 8: 15–32. doi:10.1007/BF01761704.【算子递归定理（ORT）的原始出处；Kleene 第二递归定理的无穷化推广，由自复制自动机的世代周期性问题引出】</ref>。它把自指的对象从一个程序升级为'''一整个可计算的程序族'''。
'''陈述'''：设 <math>\Theta</math> 是一个可计算算子（即由图灵机实现的、把（部分）函数映为（部分）函数的映射：算子通过函数图像的有限片段与被作用函数交互，因此也能作用于不可计算的函数），则存在一个全可计算、严格单调递增的函数 <math>e(p)</math>，使得对所有 <math>p, x</math>：
: <math>\phi_{e(p)}(x) \simeq \Theta(e)(p, x)</math>
与第二递归定理（表述 A）对比，有两处关键升级：
# '''从一个不动点到一个互引家族'''。<math>e(p)</math> 的每个成员 <math>e(0), e(1), e(2), \ldots</math> 都在"照镜子"——但镜子里不仅有它自己，还有整个家族。直观地说：每个成员'''不但知道自己，还知道全家'''。单调递增性进一步保证这些编号两两不同。
# '''直接工作在函数层而非源代码层'''。表述 B 的对象是"程序变换"（对源代码的机械改写），而 ORT 的对象是'''可计算算子'''——它可以利用被作用函数的'''任何'''可计算信息，即便这个函数本身不可计算。这使 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>。
=== 推论：SRT 衍生出的若干重要结果 ===
=== 推论：SRT 衍生出的若干重要结果 ===