更改

大小无更改 、 2026年9月13日 (星期日)
第393行: 第393行:  
'''算子递归定理''':设 <math>\Theta</math> 是一个可计算算子(即由图灵机实现的、把(部分)函数映为(部分)函数的映射:算子通过函数图像的有限片段与被作用函数交互,因此也能作用于不可计算的函数),则存在一个全可计算、严格单调递增的函数 <math>e(p)</math>,使得对所有 <math>p</math>:
 
'''算子递归定理''':设 <math>\Theta</math> 是一个可计算算子(即由图灵机实现的、把(部分)函数映为(部分)函数的映射:算子通过函数图像的有限片段与被作用函数交互,因此也能作用于不可计算的函数),则存在一个全可计算、严格单调递增的函数 <math>e(p)</math>,使得对所有 <math>p</math>:
   −
: <math>\phi_{e(p)} \simeq \Theta(e)(p, \cdot)</math>
+
: <math>\phi_{e(p)}(x) = \Theta(e)(p, x),\quad\forall x</math>
    
与第二递归定理({{EquationNote|表述A}})对比,有两处关键升级:
 
与第二递归定理({{EquationNote|表述A}})对比,有两处关键升级:
第400行: 第400行:  
# 直接工作在函数层而非源代码层。{{EquationNote|表述B}} 的对象是"程序变换"(对源代码的机械改写),而 ORT 的对象是'''可计算算子'''——它可以利用被作用函数的'''任何'''可计算信息,即便这个函数本身不可计算。这使 ORT 能表达"程序知道一个不可计算对象的可计算近似"这类构造。
 
# 直接工作在函数层而非源代码层。{{EquationNote|表述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" />。
+
ORT 可以由第二递归定理推出,因此二者在经典可计算性理论中等价;但 ORT 的表达形式在[[归纳推断]](algorithmic learning theory,Gold 风格的可学习性理论)中远为顺手——从 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" />。
    
=== 推论:SRT 衍生出的若干重要结果 ===
 
=== 推论:SRT 衍生出的若干重要结果 ===