更改

删除834字节 、 2026年9月7日 (星期一)
第1行: 第1行: −
= Kleene 递归定理(Kleene's Recursion Theorems) =
  −
  −
> '''词条性质''':可计算性理论(computability theory,研究"什么问题原则上可以被机械地计算"的学科)的核心定理 
  −
> '''提出者''':Stephen Cole Kleene(斯蒂芬·科尔·克林,1909–1994,美国逻辑学家,Church 的学生,可计算性理论奠基人之一) 
  −
> '''首次发表''':Kleene (1938), ''On Notation for Ordinal Numbers'', The Journal of Symbolic Logic 3(4): 150–155 
  −
> '''面向读者''':具有物理、人工智能等理工科背景、但未系统学习过递归函数论的读者。文中所有术语和符号在第一次出现时均给出解释。 
  −
> '''引用体例''':文中以〔作者 年份,页码/章节〕标注出处,完整文献信息见文末"参考文献"。
  −
  −
---
  −
  −
== 导言 ==
  −
   
'''递归定理(recursion theorem)'''&#x662F;递归函数论——即可计算性理论(computability theory,研究"什么问题原则上可以被机械地计算"的学科)——中的一组基本定理,由 Stephen Cole Kleene 提出,合称 '''Kleene 递归定理''',包括两条:'''第一递归定理'''说,任何用递归方式定义的函数方程都有可计算的(最小)解——机械式的递归定义永远合法、永远有解;'''第二递归定理'''说,对任何可计算的全函数 f,总存在源程序 c,使得执行 c 与执行 f(c) 效果完全相同(<math>\phi_c = \phi_{f(c)}</math>)——程序可以合法地引用自己的代码。
 
'''递归定理(recursion theorem)'''&#x662F;递归函数论——即可计算性理论(computability theory,研究"什么问题原则上可以被机械地计算"的学科)——中的一组基本定理,由 Stephen Cole Kleene 提出,合称 '''Kleene 递归定理''',包括两条:'''第一递归定理'''说,任何用递归方式定义的函数方程都有可计算的(最小)解——机械式的递归定义永远合法、永远有解;'''第二递归定理'''说,对任何可计算的全函数 f,总存在源程序 c,使得执行 c 与执行 f(c) 效果完全相同(<math>\phi_c = \phi_{f(c)}</math>)——程序可以合法地引用自己的代码。
   第18行: 第6行:     
'''图1''':六个经典自指现象——Cantor 对角线(1891)、Russell 悖论(1901)、Gödel 不完备定理(1931)、Turing 停机问题(1936)、von Neumann 自复制(1948)、Quine(自打印程序,1960s)——都源于同一种对角线/自指原理;Kleene 第二递归定理是这一原理最一般的陈述。
 
'''图1''':六个经典自指现象——Cantor 对角线(1891)、Russell 悖论(1901)、Gödel 不完备定理(1931)、Turing 停机问题(1936)、von Neumann 自复制(1948)、Quine(自打印程序,1960s)——都源于同一种对角线/自指原理;Kleene 第二递归定理是这一原理最一般的陈述。
−
  −
---
      
== 总览:两个定理各说了什么 ==
 
== 总览:两个定理各说了什么 ==