3,094
个编辑
更改
跳到导航
跳到搜索
第747行：
第747行： − # '''简单性与普适性的反差'''。SRT 的全部证明只有一行对角线，应用却横跨逻辑学几乎所有分支。Moschovakis 指出：其广泛适用性恰恰'''源于'''这种简单——它极易被翻译到自然数以外的语境（实数空间、任意 Polish 空间、高类型对象、模态逻辑），在每个语境中重新化身<ref name="moschovakis2010" />。+ − # '''两个递归定理的分工'''。第一递归定理保证'''递归定义有最小解'''（函数层面、序理论的不动点）；第二递归定理保证'''自指定义合法'''（代码层面的不动点）。前者回答"这个函数方程有解吗"，后者回答"我能在定义中引用被定义者自己的代码吗"。强定理蕴含弱定理，反之不然（见 4.4）。+ − # '''自指的数学化'''。从 Gödel 的替换函数、Turing 的通用机、von Neumann 的自复制自动机，到 quine、计算机病毒、编译器自举，乃至人工智能中"系统改进自身"的设想，"系统谈论自身"的可行性边界都由同一种对角线结构划定。Kleene 递归定理是这一结构最干净、最一般的陈述。+ − # '''历史反讽'''。Kleene 1938 年发明 SRT 是为了构造序数记号，而 1944 年他恰恰因为"拿到一个不动点却误以为拿到最小不动点"而犯下著名错误，直到 1955 年才纠正（见 3.3）——这个故事最恰当地说明了理解两个递归定理'''区别'''的重要性。+ − # '''Rogers 的总评'''：递归定理是"一个基本的研究工具、一个深刻的结果"（a basic research tool <math>\ldots</math> a deep result），它的深刻在于"以优雅和智识上的经济性，处理那些否则需要繁复构造的问题"<ref name="rogers1967" />；虽然它的直接效果常是产生各种"病态"结构（自我枚举的集合、自我打印的程序），但它在 Myhill 定理等结果中起到了"在此前独立定义的概念之间建立正则联系"的作用<ref name="rogers1967" />。+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
撤销Jake（讨论）的版本51018
== 评注与影响 ==
== 评注与影响 ==
1. '''简单性与普适性的反差'''。SRT 的全部证明只有一行对角线，应用却横跨逻辑学几乎所有分支。Moschovakis 指出：其广泛适用性恰恰'''源于'''这种简单——它极易被翻译到自然数以外的语境（实数空间、任意 Polish 空间、高类型对象、模态逻辑），在每个语境中重新化身<ref name="moschovakis2010" />。
2. '''两个递归定理的分工'''。第一递归定理保证'''递归定义有最小解'''（函数层面、序理论的不动点）；第二递归定理保证'''自指定义合法'''（代码层面的不动点）。前者回答"这个函数方程有解吗"，后者回答"我能在定义中引用被定义者自己的代码吗"。强定理蕴含弱定理，反之不然（见 4.4）。
3. '''自指的数学化'''。从 Gödel 的替换函数、Turing 的通用机、von Neumann 的自复制自动机，到 quine、计算机病毒、编译器自举，乃至人工智能中"系统改进自身"的设想，"系统谈论自身"的可行性边界都由同一种对角线结构划定。Kleene 递归定理是这一结构最干净、最一般的陈述。
4. '''历史反讽'''。Kleene 1938 年发明 SRT 是为了构造序数记号，而 1944 年他恰恰因为"拿到一个不动点却误以为拿到最小不动点"而犯下著名错误，直到 1955 年才纠正（见 3.3）——这个故事最恰当地说明了理解两个递归定理'''区别'''的重要性。
5. '''Rogers 的总评'''：递归定理是"一个基本的研究工具、一个深刻的结果"（a basic research tool <math>\ldots</math> a deep result），它的深刻在于"以优雅和智识上的经济性，处理那些否则需要繁复构造的问题"<ref name="rogers1967" />；虽然它的直接效果常是产生各种"病态"结构（自我枚举的集合、自我打印的程序），但它在 Myhill 定理等结果中起到了"在此前独立定义的概念之间建立正则联系"的作用<ref name="rogers1967" />。
---
'''一手文献'''
:<ref name="cantor1891">'''Cantor, G. (1891).''' Über eine elementare Frage der Mannigfaltigkeitslehre. ''Jahresbericht der Deutschen Mathematiker-Vereinigung'', 1, 75–78.【对角线论证的源头】</ref>
:<ref name="russell1908">'''Russell, B. (1908).''' Mathematical logic as based on the theory of types. ''American Journal of Mathematics'', 30, 222–262.【罗素悖论的现代陈述】</ref>
:<ref name="godel1931">'''Gödel, K. (1931).''' Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. ''Monatshefte für Mathematik und Physik'', 38, 173–198.【Gödel 不完备定理（Gödel 不动点引理是其核心证明工具，见 §5.6.1）】【§5.7.4】</ref>
:<ref name="kleene1938">'''Kleene, S. C. (1938).''' On notation for ordinal numbers. ''The Journal of Symbolic Logic'', 3(4), 150–155.【第二递归定理的原始出处，定理与证明见 p.153】</ref>
:<ref name="turing1936">'''Turing, A. M. (1936).''' On computable numbers, with an application to the Entscheidungsproblem. ''Proceedings of the London Mathematical Society'', 42, 230–265.【停机问题不可判定】</ref>
:<ref name="kleene1952">Kleene, S. C. (1952). ''Introduction to Metamathematics''. D. Van Nostrand.【第一递归定理的明确表述】</ref>
:<ref name="vonneumann1966">'''von Neumann, J. (1966).''' ''Theory of Self-Reproducing Automata'' (A. W. Burks 编). University of Illinois Press.【自复制自动机的奠基性设计（原稿始于 1948）】【§5.7.5】</ref>
:<ref name="lee1963">'''Lee, C. Y. (1963).''' A Turing machine which prints its own tape. ''Mathematical Tables and Other Aids to Computation'', 17, 403–406.【Rogers 1967 §11.4 第三图示的直接启发】</ref>
:<ref name="bratley1972">'''Bratley, P., & Millo, J. (1972).''' Computer recreations: Self-reproducing programs. ''Software: Practice and Experience'', 2, 397–400.【自打印程序的早期系统研究】</ref>
:<ref name="church1936">Church, A., & Kleene, S. C. (1936). Formal definitions in the theory of ordinal numbers. ''Fundamenta Mathematicae'', 28, 11–21.【序数记号问题的源头】</ref>
:<ref name="hofstadter1979">'''Hofstadter, D. R. (1979).''' ''Gödel, Escher, Bach: An Eternal Golden Braid''. Basic Books.【"quine" 一词的普及来源】</ref>
:<ref name="wikipedia_quine_computing">'''Wikipedia.''' ''Quine (computing)''. <https://en.wikipedia.org/wiki/Quine_(computing).【quine> 的准确定义：不接受输入、只输出自身源码、且不得读取自身源码】【§5.7.6】</ref>
:<ref name="cutland1980">'''Cutland, N. J. (1980).''' ''Computability: An Introduction to Recursive Function Theory''. Cambridge University Press.【§1.9 定理 1.9 给出 totally <math>\psi</math>-introspective 程序的原始定义与存在性证明——"自省程序"概念的最早明确出处（§5.7.7）；§2.3 定理 2.3 给出 SRT 的"列表法"证明（§5.3.1）】</ref>
:<ref name="zhang2026">'''Zhang, J., Yuan, B., & Zhang, Q. (2026).''' Self-Referential Introspection in Large Language Models: The Critical Threshold for Recursive Self-Improvement. ''Entropy'', 28(9), 951.【自省程序（f=<math>f_T</math> 有界自模拟）与自省式自改进程序的定义；SRT 在 LLM 递归自我改进中的应用】【§5.7.7】</ref>
:<ref name="myhill1955">Myhill, J. (1955). Creative sets. ''Zeitschrift für mathematische Logik und Grundlagen der Mathematik'', 1, 97–108.</ref>
:<ref name="myhill1955">Myhill, J., & Shepherdson, J. C. (1955). Effective operations on partial recursive functions. ''Zeitschrift für mathematische Logik und Grundlagen der Mathematik'', 1, 310–317.</ref>
:<ref name="smullyan1961">'''Smullyan, R. M. (1961).''' ''Theory of Formal Systems''. Princeton University Press.【双递归定理的提出者；§5.2.1】</ref>
:<ref name="spector1955">Spector, C. (1955). Recursive wellorderings. ''The Journal of Symbolic Logic'', 20, 151–163.</ref>
:<ref name="solovay1976">Solovay, R. M. (1976). Provability interpretations of modal logic. ''Israel Journal of Mathematics'', 25, 287–304.</ref>
:<ref name="rice1953">'''Rice, H. G. (1953).''' Classes of recursively enumerable sets and their decision problems. ''Transactions of the AMS'', 74, 358–366.【Rice 定理原始论文】【§6.5.1】</ref>
:<ref name="arslanov1981">'''Arslanov, R. R. (1981).''' On a class of recursively enumerable sets. ''Algebra and Logic'', 20, 324–328.【Arslanov 完全性判据】【§5.2.3】</ref>
:<ref name="lawvere1969">'''Lawvere, F. W. (1969).''' Diagonal arguments and cartesian closed categories. In ''Category Theory, Homology Theory and their Applications III'', Lecture Notes in Mathematics, vol. 92, Springer.【Lawvere 不动点定理，把 SRT、Gödel 不完备、Turing 停机统一为范畴论特例】【§5.6.2】</ref>
'''综述与教材（本文主要依据）'''
:<ref name="moschovakis2010">'''Moschovakis, Y. N. (2010).''' Kleene's amazing second recursion theorem. ''The Bulletin of Symbolic Logic'', 16(2), 189–239.【18 个应用的权威综述；本文应用部分的章节编号均指此文】</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>
<references />
<references />