更改

'''递归定理（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]]小节）。

'''递归定理（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]]小节）。

[[文件:自指家族.png|替代=自指家族|缩略图|图1：六个经典自指现象——[[康托尔对角线]]（1891）、[[罗素悖论]]（1901）、[[哥德尔不完备定理]]（1931）、[[图灵停机问题]]（1936）、[[冯诺伊曼自复制]]（1948）、[[Quine]]（[[自打印程序]]，1960s）——都源于同一种对角线/自指原理；Kleene 第二递归定理是这一原理最一般的陈述。]]

[[文件:自指家族.png|替代=自指家族|缩略图|图1：六个经典自指现象——[[康托尔对角线]]（1891）、[[罗素悖论]]（1901）、[[哥德尔不完备定理]]（1931）、[[图灵停机问题]]（1936）、[[冯诺伊曼自复制]]（1948）、[[Quine]]（[[自打印程序]]，1960s）和[[自省程序]](以及自省式自修改程序，2026）——都源于同一种对角线/自指原理；Kleene 第二递归定理是这一原理最一般的陈述。]]

第二递归定理可以用公式表达为：

第二递归定理可以用公式表达为：