3,094
个编辑
更改
跳到导航
跳到搜索
第40行：
第40行： − + − − '''图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 对此有详细辨析。
→总览：两个定理各说了什么
| Kleene (1938) §2 末尾，当时甚至没有名字，证明只有两行<ref name="kleene1938" />
| Kleene (1938) §2 末尾，当时甚至没有名字，证明只有两行<ref name="kleene1938" />
|}
|}
[[文件:两种“不动点”.png|替代=两种“不动点”|缩略图|图2：两个定理的"不动点"含义截然不同——左：函数 <nowiki><math>\phi</math></nowiki> 经变换 <nowiki><math>\Psi</math></nowiki> 后变回 <nowiki><math>\phi</math></nowiki>（函数层面）；右：程序 <nowiki><math>n</math></nowiki> 经变换 <nowiki><math>f</math></nowiki> 后变成另一个程序 <nowiki><math>f(n)</math></nowiki>（通常<nowiki><math> f(n) \neq n</math></nowiki>），但 <nowiki><math>\phi_n = \phi_{f(n)}</math></nowiki>（'''代码变了，行为不变'''）。§2.5 对此有详细辨析。]]
[[文件:两种“不动点”.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" />, §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<ref name="kiselyov" />, §1〕。它的一行证明看似只是个小技巧，却支撑了从 [[哥德尔|Gödel]] 不完备定理到[[序数]]理论、从程序自复制到有效[[描述集合论]]的庞大理论大厦（详见第五、六节）。