更改

== 总览：两个定理各说了什么 ==

== 总览：两个定理各说了什么 ==

'''Kleene 递归定理'''是关于'''自指（self-reference，即一个系统"谈论"自身）'''[[不动点]]（fixed point，即变换后保持不变的点）两个基本定理的合称。先用日常语言各说一遍，再给出精确表述。

'''Kleene 递归定理'''是关于'''[[自指]]（self-reference，即一个系统"谈论"自身）'''[[不动点]]（fixed point，即变换后保持不变的点）两个基本定理的合称。先用日常语言各说一遍，再给出精确表述。

'''第二递归定理（日常语言版）'''：''对任何可计算的全函数 <math>f</math>（一个对任何输入都停机的"程序变换"），总存在一个源程序 <math>c</math>，使得执行 <math>c</math> 的效果，等同于执行 <math>f(c)</math>——即 <math>f</math> 拿着 <math>c</math> 自己的源代码算出来的那个程序。'' 用符号写就是：<math>\phi_c = \phi_{f(c)}</math>。<ref name="rogers1967" />

'''第二递归定理（日常语言版）'''：''对任何可计算的全函数 <math>f</math>（一个对任何输入都停机的"程序变换"），总存在一个源程序 <math>c</math>，使得执行 <math>c</math> 的效果，等同于执行 <math>f(c)</math>——即 <math>f</math> 拿着 <math>c</math> 自己的源代码算出来的那个程序。'' 用符号写就是：<math>\phi_c = \phi_{f(c)}</math>。<ref name="rogers1967" />

|-

|-

| '''结论'''

| '''结论'''

| 任何可计算的函数变换规则 <math>\Psi</math> 都有最小不动点 <math>\phi</math>，且 <math>\phi</math> 是可计算的：<math>\Psi(\phi) = \phi</math>

| 任何可计算的函数变换规则 <math>\Psi</math> 都有最小[[不动点]] <math>\phi</math>，且 <math>\phi</math> 是可计算的：<math>\Psi(\phi) = \phi</math>

| 任何可计算的程序变换规则 f 都有不动点 n：程序 n 与程序 f(n) 计算同一个函数，记作 <math>\phi_n = \phi_{f(n)}</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" />

| [[序理论]]中 [[Knaster–Tarski 不动点定理]]的"可计算版本"<ref name="rogers1967" />

| 对角线方法（diagonalization，Cantor、Gödel、Turing 用过的同一种论证技术）的集大成者<ref name="rogers1967" />

| [[对角线方法]]（diagonalization，[[Cantor]]、[[Gödel]]、[[Turing]] 用过的同一种论证技术）的集大成者<ref name="rogers1967" />

|-

|-

| '''别称'''

| '''别称'''

![两种[[不动点]]](figures/fig3_two_fixedpoints.png)

![两种[[不动点]]](figures/fig3_two_fixedpoints.png)

'''图2'''：两个定理的"不动点"含义截然不同——左：函数 <math>\phi</math> 经变换 <math>\Psi</math> 后变回 <math>\phi</math>（函数层面）；右：程序 n 经变换 f 后变成另一个程序 f(n)（通常 f(n) <math>\neq n</math>），但 <math>\phi_n = \phi_{f(n)}</math>（'''代码变了，行为不变'''）。§2.5 对此有详细辨析。

'''图2'''：两个定理的"不动点"含义截然不同——左：函数 <math>\phi</math> 经变换 <math>\Psi</math> 后变回 <math>\phi</math>（函数层面）；右：程序 <math>n</math> 经变换 <math>f</math> 后变成另一个程序 <math>f(n)</math>（通常 <math>f(n)</math> <math>\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 称之&#x4E3A;'''"可计算性的瑞士军刀"（A Swiss Pocket Knife for Computability）'''〔转引自 Kiselyov, §1〕。它的一行证明看似只是个小技巧，却支撑了从 [[哥德尔|Gödel]] 不完备定理到[[序数]]理论、从程序自复制到有效[[描述集合论]]的庞大理论大厦（详见第五、六节）。

第二递归定理被 [[Yiannis N. Moschovakis|Moschovakis]] 称为 '''"令人惊叹的"（amazing）'''——他的综述标题就叫 ''Kleene's Amazing Second Recursion Theorem''<ref name="moschovakis2010" />；计算机科学家 Neil Jones 称之'''"可计算性的瑞士军刀"（A Swiss Pocket Knife for Computability）'''〔转引自 Kiselyov, §1〕。它的一行证明看似只是个小技巧，却支撑了从 [[哥德尔|Gödel]] 不完备定理到[[序数]]理论、从程序自复制到有效[[描述集合论]]的庞大理论大厦（详见第五、六节）。

---

---