更改

'''递归定理（recursion theorem）'''[[递归函数论]]——即[[可计算性理论]]（computability theory，研究"什么问题原则上可以被机械地计算"的学科）——中的一组基本定理，由[[Stephen Cole Kleene]]提出，合称 '''Kleene 递归定理'''，包括两条：'''第一递归定理''': 任何用递归方式定义的[[函数方程]]都有可计算的（最小）解——机械式的递归定义永远合法、永远有解；'''第二递归定理''': 对任何可计算的全函数 <math>f</math>，总存在源程序<math>c</math>，使得执行<math>c</math>与执行<math>f(c)</math> 效果完全相同（<math>\phi_c = \phi_{f(c)}</math>）——程序可以合法地引用自己的代码。

'''递归定理（recursion theorem）'''是[[递归函数论]]，即[[可计算性理论]]（computability theory）中的一组基本定理，由[[Stephen Cole Kleene]]提出，合称 '''Kleene 递归定理'''，包括两条：'''第一递归定理''': 任何用递归方式定义的[[函数方程]]都有可计算的（最小）解——机械式的递归定义永远合法、永远有解；'''第二递归定理''': 对任何可计算的全函数 <math>f</math>，总存在一个程序编号（即源代码）<math>c</math>，使得执行<math>c</math>与执行编号（源代码）为<math>f(c)</math>的计算效果完全相同，因此程序可以合法地引用自己的代码。两条之中，第二递归定理尤为重要，它是数学中对[[自指]]（self-reference）现象最简洁、最有力的统一陈述：它只有一步对角线证明 `<math>c = S(e, e)</math>`（<math>S</math> 是"把程序的部分输入写死、生成新程序"的[[柯里化操作]]（Currying），详见[[#s-m-n 定理（柯里化 / 参数特化）|2.3]]小节），却统一了从[[罗素悖论]]（1901）、[[哥德尔不完备定理]]（1931）、[[图灵停机问题]]（1936）、[[冯诺伊曼自复制自动机]]（1948）到今天的[[Quine程序]]（1960s）等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身（详见[[#SRT与自指|5.7]]小节）。

 

 

:<math>

\phi_c \simeq \phi_{f(c)}

</math>

两条之中，第二递归定理尤为重要，它是数学中对[[自指]]（self-reference）现象最简洁、最有力的统一陈述：它只有一步对角线证明 `<math>c = S(e, e)</math>`（<math>S</math> 是"把程序的部分输入写死、生成新程序"的[[柯里化操作]]（Currying），详见[[#s-m-n 定理（柯里化 / 参数特化）|2.3]]小节），却统一了从[[罗素悖论]]（1901）、[[哥德尔不完备定理]]（1931）、[[图灵停机问题]]（1936）、[[冯诺伊曼自复制自动机]]（1948）到今天的[[Quine程序]]（1960s）等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身（详见[[#SRT与自指|5.7]]小节）。

这里的<math>\phi</math>代表通用函数，<math>\phi_c</math>代表通用函数在模拟代码为<math>c</math>的程序计算，<math>\simeq</math>代表左右两个函数功能等价，即它们在所有的输入数据上要么计算结果相等，要么无定义。