更改

跳到导航 跳到搜索
添加32字节 、 2026年9月12日 (星期六)
第47行: 第47行:  
| Kleene (1938) §2 末尾,当时甚至没有名字,证明只有两行<ref name="kleene1938">'''Kleene, S. C. (1938).''' On notation for ordinal numbers. ''The Journal of Symbolic Logic'', 3(4), 150–155.【第二递归定理的原始出处,定理与证明见 p.153】</ref>
 
| Kleene (1938) §2 末尾,当时甚至没有名字,证明只有两行<ref name="kleene1938">'''Kleene, S. C. (1938).''' On notation for ordinal numbers. ''The Journal of Symbolic Logic'', 3(4), 150–155.【第二递归定理的原始出处,定理与证明见 p.153】</ref>
 
|}
 
|}
−
[[文件:两种“不动点”.png|替代=两种“不动点”|缩略图|图2:两个定理的"不动点"含义截然不同——左:函数 <math>\varphi</math>经变换<math>\Psi</math> 后变回 <math>\varphi</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 对此有详细辨析。]]
+
[[文件:两种“不动点”.png|替代=两种“不动点”|缩略图|图2:两个定理的"不动点"含义截然不同——左:函数 <math>\varphi</math>经变换<math>\Psi</math> 后变回 <math>\varphi</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〕。它的一行证明看似只是个小技巧,却支撑了从 [[哥德尔不完备定理]]到[[序数]]理论、从程序自复制到有效[[描述集合论]]的庞大理论大厦(详见第[[#第二递归定理(SRT)|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〕。它的一行证明看似只是个小技巧,却支撑了从 [[哥德尔不完备定理]]到[[序数]]理论、从程序自复制到有效[[描述集合论]]的庞大理论大厦(详见第[[#第二递归定理(SRT)|5]])。

导航菜单