递归定理

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

两条之中，第二递归定理尤为重要，它是数学中对自指（self-reference）现象最简洁、最有力的统一陈述：它只有一步对角线证明 `[math]\displaystyle{ c = S(e, e) }[/math]`（[math]\displaystyle{ S }[/math] 是"把程序的部分输入写死、生成新程序"的柯里化操作，详见 §2.3），却统一了从罗素悖论（1901）、Gödel不完备定理（1931）、Turing停机问题（1936）、von Neumann 自复制自动机（1948）到今天的Quine程序（1960s）等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身（详 §5.7）。

图1：六个经典自指现象——Cantor对角线（1891）、Russell悖论（1901）、Gödel不完备定理（1931）、Turing停机问题（1936）、von Neumann自复制（1948）、Quine（自打印程序，1960s）——都源于同一种对角线/自指原理；Kleene 第二递归定理是这一原理最一般的陈述。