3,094
个编辑
更改
跳到导航
跳到搜索
第2行：
第2行： + −  − − '''图1'''：六个经典自指现象——Cantor 对角线（1891）、Russell 悖论（1901）、Gödel 不完备定理（1931）、Turing 停机问题（1936）、von Neumann 自复制（1948）、Quine（自打印程序，1960s）——都源于同一种对角线/自指原理；Kleene 第二递归定理是这一原理最一般的陈述。 第820行：
第818行： +
无编辑摘要
两条之中，第二递归定理尤为重要，它是数学中对"自指"（self-reference）现象最简洁、最有力的统一陈述：它只有一步对角线证明 `c = S(e, e)`（S 是"把程序的部分输入写死、生成新程序"的柯里化操作，详见 §2.3），却统一了从罗素悖论（1901）、Gödel 不完备定理（1931）、Turing 停机问题（1936）、von Neumann 自复制自动机（1948）到今天的 quine 程序（1960s）等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身（详 §5.7）。
两条之中，第二递归定理尤为重要，它是数学中对"自指"（self-reference）现象最简洁、最有力的统一陈述：它只有一步对角线证明 `c = S(e, e)`（S 是"把程序的部分输入写死、生成新程序"的柯里化操作，详见 §2.3），却统一了从罗素悖论（1901）、Gödel 不完备定理（1931）、Turing 停机问题（1936）、von Neumann 自复制自动机（1948）到今天的 quine 程序（1960s）等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身（详 §5.7）。
[[文件:自指家族.png|替代=自指家族|缩略图|自指家族]]
== 总览：两个定理各说了什么 ==
== 总览：两个定理各说了什么 ==
:<ref name="rogers1967">'''Rogers, H., Jr. (1967).''' ''Theory of Recursive Functions and Effective Computability''. McGraw-Hill. 第 11 章 The Recursion Theorem, pp. 179–222.【教科书标准表述；第一/第二递归定理的命名来源】</ref>
:<ref name="rogers1967">'''Rogers, H., Jr. (1967).''' ''Theory of Recursive Functions and Effective Computability''. McGraw-Hill. 第 11 章 The Recursion Theorem, pp. 179–222.【教科书标准表述；第一/第二递归定理的命名来源】</ref>
:<ref name="kiselyov">'''Kiselyov, O.''' ''Kleene Second Recursion Theorem: A Functional Pearl''.【<math>\lambda</math> 演算/函数式编程视角；quine、twine、性能分析；Unix `cat` 例子出处】</ref>
:<ref name="kiselyov">'''Kiselyov, O.''' ''Kleene Second Recursion Theorem: A Functional Pearl''.【<math>\lambda</math> 演算/函数式编程视角；quine、twine、性能分析；Unix `cat` 例子出处】</ref>
<references />