更改

'''表述 C（带参数的强化形式）'''：A、B 只断言不动点"存在"，表述 C 进一步保证：不动点'''能被程序机械地找出来，并且能随参数连续变化'''。设想变换规则额外带一个参数 <math>y</math>——用一个三元函数 <math>\psi(e, y, x)</math> 表示"编号为 <math>e</math> 的程序在参数 <math>y</math> 下的行为"。那么存在一个可计算的全函数 <math>z</math>：你输入 <math>y</math>，它就输出针对这个参数的不动点编号 <math>z(y)</math>，使得:

'''表述 C（带参数的强化形式）'''：A、B 只断言不动点"存在"，{{EquationNote|表述C}} 进一步保证：不动点'''能被程序机械地找出来，并且能随参数连续变化'''。设想变换规则额外带一个参数 <math>y</math>——用一个三元函数 <math>\psi(e, y, x)</math> 表示"编号为 <math>e</math> 的程序在参数 <math>y</math> 下的行为"。那么存在一个可计算的全函数 <math>z</math>：你输入 <math>y</math>，它就输出针对这个参数的不动点编号 <math>z(y)</math>，使得:

{{NumBlk|:|

{{NumBlk|:|

====一行对角线====

====一行对角线====

以表述 A 为例，全部证明如下：

以{{EquationNote|表述A}} 为例，全部证明如下：

首先，根据[[s-m-n定理]]，对于任意的编号为<math>a</math>的二元输入可计算函数，以及任意的自然数<math>y</math>，这个二元函数都等价于一个一元可计算函数：

首先，根据[[s-m-n定理]]，对于任意的编号为<math>a</math>的二元输入可计算函数，以及任意的自然数<math>y</math>，这个二元函数都等价于一个一元可计算函数：

也就是说，'''SRT 证明与 quine 不是"互逆"，而是同构'''——两者都是"先有一个具体的全可计算函数 <math>f</math>、再造一个不动点程序 <math>c</math> 满足 <math>\phi_c = \phi_{f(c)}</math>"。SRT 真正比 quine 强的地方只有一点：'''它证明了"先有 <math>f</math>、再造 <math>c</math>"这种构造对所有全可计算 <math>f</math> 都成立'''，而 quine 只演示了 <math>f =</math> Print 一个特例；SRT 给的不是"一个程序"，而是"对每个 <math>f</math> 都有一个程序（<math>f</math> 的不动点 <math>c</math>）"这样的普遍性陈述。这也解释了为何 SRT 在可计算性文献中被称为"second recursion theorem"——它把"quine 这种特例的构造手法"摆到了"自指可计算函数的普遍刻画"这一位置，把 quine 从"程序员的奇技"升格为"任何合理程序系统都封不住自指"的元定理。

也就是说，'''SRT 证明与 quine 不是"互逆"，而是同构'''——两者都是"先有一个具体的全可计算函数 <math>f</math>、再造一个不动点程序 <math>c</math> 满足 <math>\phi_c = \phi_{f(c)}</math>"。SRT 真正比 quine 强的地方只有一点：'''它证明了"先有 <math>f</math>、再造 <math>c</math>"这种构造对所有全可计算 <math>f</math> 都成立'''，而 quine 只演示了 <math>f =</math> Print 一个特例；SRT 给的不是"一个程序"，而是"对每个 <math>f</math> 都有一个程序（<math>f</math> 的不动点 <math>c</math>）"这样的普遍性陈述。这也解释了为何 SRT 在可计算性文献中被称为"second recursion theorem"——它把"quine 这种特例的构造手法"摆到了"自指可计算函数的普遍刻画"这一位置，把 quine 从"程序员的奇技"升格为"任何合理程序系统都封不住自指"的元定理。

'''例 2（自我命名的集合）'''<ref name="rogers1967" />：是否存在程序 <math>n</math>，它所列出的集合恰好是单点集 <math>\{n\}</math>——'''一个枚举出自己编号的程序'''？直觉上这像是编号系统的"巧合"，但取变换规则 <math>f</math> 使得"程序 <math>f(x)</math> 恰好输出单点集 <math>\{x\}</math>"（这样的 <math>f</math> 显然可构造），应用表述 B 即得 <math>\phi_n = \phi_{f(n)}</math>，即 <math>W_n = \{n\}</math>。而且这个结论对'''任何合理的程序编号系统都成立'''——它不是编号的巧合，而是编号的必然。

'''例 2（自我命名的集合）'''<ref name="rogers1967" />：是否存在程序 <math>n</math>，它所列出的集合恰好是单点集 <math>\{n\}</math>——'''一个枚举出自己编号的程序'''？直觉上这像是编号系统的"巧合"，但取变换规则 <math>f</math> 使得"程序 <math>f(x)</math> 恰好输出单点集 <math>\{x\}</math>"（这样的 <math>f</math> 显然可构造），应用{{EquationNote|表述B}} 即得 <math>\phi_n = \phi_{f(n)}</math>，即 <math>W_n = \{n\}</math>。而且这个结论对'''任何合理的程序编号系统都成立'''——它不是编号的巧合，而是编号的必然。

'''自指的机制'''（Rogers 的精辟分析）<ref name="rogers1967" />：不动点程序 <math>n</math> 作为一段指令，'''并不包含它自身的全文'''（这不可能，句子不能比自身还长），而是包含'''一份"如何重建自身"的配方'''——"先算出我的代码，再执行它"。这与 Gödel 在证明不完备定理时发明的"替换函数"（substitution function，把一个公式的编号代入公式自身）是同一种机制。自然语言中的对应物是这个短语：

'''自指的机制'''（Rogers 的精辟分析）<ref name="rogers1967" />：不动点程序 <math>n</math> 作为一段指令，'''并不包含它自身的全文'''（这不可能，句子不能比自身还长），而是包含'''一份"如何重建自身"的配方'''——"先算出我的代码，再执行它"。这与 Gödel 在证明不完备定理时发明的"替换函数"（substitution function，把一个公式的编号代入公式自身）是同一种机制。自然语言中的对应物是这个短语：

: <math>\phi_{e(p)} \simeq \Theta(e)(p, \cdot)</math>

: <math>\phi_{e(p)} \simeq \Theta(e)(p, \cdot)</math>

# 从一个不动点到一个互引家族。<math>e(p)</math> 的每个成员 <math>e(0), e(1), e(2), \ldots</math> 都在"照镜子"——但镜子里不仅有它自己，还有整个家族。单调递增性进一步保证这些编号两两不同。

# 从一个不动点到一个互引家族。<math>e(p)</math> 的每个成员 <math>e(0), e(1), e(2), \ldots</math> 都在"照镜子"——但镜子里不仅有它自己，还有整个家族。单调递增性进一步保证这些编号两两不同。

# 直接工作在函数层而非源代码层。表述 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 与 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 默认在一个'''[[可接受编号]]'''（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 不动点形式（{{EquationNote|表述B}}）对一切可接受编号成立；但在'''一般的可计算编号'''（同样是全部一元偏可计算函数的一致枚举、却不满足可接受性的编号）中，'''Kleene 形式（{{EquationNote|表述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>。

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

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

== 评注与影响 ==

== 评注与影响 ==