|
|
| 第12行： |
第12行： |
| | | | |
| | '''第一递归定理（日常语言版）'''：''任何递归定义——即把一个函数在某处的值，写成它自己在其他输入上的值（比如阶乘 <math>fac(n) = n\cdot fac(n−1)</math>）——都必然有解'' ，而且其中"最小"的那个解一定能被机器算出。换句话说，'''机械式的递归定义永远合法、永远有解'''。<ref name="rogers1967" /> | | '''第一递归定理（日常语言版）'''：''任何递归定义——即把一个函数在某处的值，写成它自己在其他输入上的值（比如阶乘 <math>fac(n) = n\cdot fac(n−1)</math>）——都必然有解'' ，而且其中"最小"的那个解一定能被机器算出。换句话说，'''机械式的递归定义永远合法、永远有解'''。<ref name="rogers1967" /> |
| − |
| |
| − | 两个定理的对照表（其中涉及的符号会在第二节逐一解释，此处可先跳过细节）：
| |
| − |
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | !
| |
| − | ! '''第一递归定理'''（First Recursion Theorem, FRT）
| |
| − | ! '''第二递归定理'''（Second Recursion Theorem, SRT）
| |
| − | |-
| |
| − | | '''作用对象'''
| |
| − | | 函数本身（"把函数变成函数"的规则）
| |
| − | | 程序的编号（代码）
| |
| − | |-
| |
| − | | '''结论'''
| |
| − | | 任何可计算的函数变换规则 <math>\Psi</math> 都有最小[[不动点]] <math>\phi</math>，且 <math>\phi</math> 是可计算的：<math>\Psi(\phi) = \phi</math>
| |
| − | | 任何可计算的程序变换规则 <math>f</math> 都有不动点 <math>n</math>：程序 <math>n</math> 与程序 <math>f(n)</math> 计算同一个函数，记作 <math>\phi_n = \phi_{f(n)}</math>
| |
| − | |-
| |
| − | | '''数学血统'''
| |
| − | | [[序理论]]中 [[Knaster–Tarski 不动点定理]]的"可计算版本"<ref name="rogers1967" />
| |
| − | | [[对角线方法]]（diagonalization，[[Cantor]]、[[Gödel]]、[[Turing]] 用过的同一种论证技术）的集大成者<ref name="rogers1967" />
| |
| − | |-
| |
| − | | '''别称'''
| |
| − | | 弱递归定理
| |
| − | | 强递归定理、Kleene 不动点定理
| |
| − | |-
| |
| − | | '''首次出现'''
| |
| − | | Kleene (1952)《元数学导论》中明确表述<ref name="kleene1952">Kleene, S. C. (1952). ''Introduction to Metamathematics''. D. Van Nostrand.【第一递归定理的明确表述】</ref><ref name="moschovakis2010" />
| |
| − | | Kleene (1938) §2 末尾，当时甚至没有名字，证明只有两行<ref name="kleene1938" />
| |
| − | |}
| |
| − | [[文件:两种“不动点”.png|替代=两种“不动点”|缩略图|图2：两个定理的"不动点"含义截然不同——左：函数 <math>\phi</math>经变换<math>\Psi</math> 后变回 <math>\phi</math>（函数层面）；右：程序 <math>n</math> 经变换 <math>f</math> 后变成另一个程序 <math>f(n)</math>（通常<math> f(n) \neq n</math>），但<math>\phi_n = \phi_{f(n)}</math>（'''代码变了，行为不变'''）。§2.5 对此有详细辨析。]]
| |
| − |
| |
| − | 第二递归定理被 [[Yiannis N. Moschovakis|Moschovakis]] 称为 '''"令人惊叹的"（amazing）'''——他的综述标题就叫 ''Kleene's Amazing Second Recursion Theorem''<ref name="moschovakis2010" />；计算机科学家 Neil Jones 称之'''"可计算性的瑞士军刀"（A Swiss Pocket Knife for Computability）'''〔转引自 Kiselyov<ref name="kiselyov">'''Kiselyov, O.''' ''Kleene Second Recursion Theorem: A Functional Pearl''.【<math>\lambda</math> 演算/函数式编程视角；quine、twine、性能分析；Unix `cat` 例子出处】</ref>, §1〕。它的一行证明看似只是个小技巧，却支撑了从 [[哥德尔|Gödel]] 不完备定理到[[序数]]理论、从程序自复制到有效[[描述集合论]]的庞大理论大厦（详见第五、六节）。
| |
2026年9月10日 (四) 06:06的版本
递归定理（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）。
总览：两个定理各说了什么
Kleene 递归定理是关于自指（self-reference，即一个系统"谈论"自身）不动点（fixed point，即变换后保持不变的点）两个基本定理的合称。先用日常语言各说一遍，再给出精确表述。
第二递归定理（日常语言版）：对任何可计算的全函数 [math]\displaystyle{ f }[/math]（一个对任何输入都停机的"程序变换"），总存在一个源程序 [math]\displaystyle{ c }[/math]，使得执行 [math]\displaystyle{ c }[/math] 的效果，等同于执行 [math]\displaystyle{ f(c) }[/math]——即 [math]\displaystyle{ f }[/math] 拿着 [math]\displaystyle{ c }[/math] 自己的源代码算出来的那个程序。 用符号写就是：[math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math][1].
第一递归定理（日常语言版）：任何递归定义——即把一个函数在某处的值，写成它自己在其他输入上的值（比如阶乘 [math]\displaystyle{ fac(n) = n\cdot fac(n−1) }[/math]）——都必然有解 ，而且其中"最小"的那个解一定能被机器算出。换句话说，机械式的递归定义永远合法、永远有解。[1]
- ↑ 1.0 1.1 Rogers, H., Jr. (1967). Theory of Recursive Functions and Effective Computability. McGraw-Hill. 第 11 章 The Recursion Theorem, pp. 179–222.【教科书标准表述；第一/第二递归定理的命名来源】
