'''递归定理(recursion theorem)'''是递归函数论——即可计算性理论(computability theory,研究"什么问题原则上可以被机械地计算"的学科)——中的一组基本定理,由 Stephen Cole Kleene 提出,合称 '''Kleene 递归定理''',包括两条:'''第一递归定理'''说,任何用递归方式定义的函数方程都有可计算的(最小)解——机械式的递归定义永远合法、永远有解;'''第二递归定理'''说,对任何可计算的全函数 f,总存在源程序 c,使得执行 c 与执行 f(c) 效果完全相同(<math>\phi_c = \phi_{f(c)}</math>)——程序可以合法地引用自己的代码。 | '''递归定理(recursion theorem)'''是递归函数论——即可计算性理论(computability theory,研究"什么问题原则上可以被机械地计算"的学科)——中的一组基本定理,由 Stephen Cole Kleene 提出,合称 '''Kleene 递归定理''',包括两条:'''第一递归定理'''说,任何用递归方式定义的函数方程都有可计算的(最小)解——机械式的递归定义永远合法、永远有解;'''第二递归定理'''说,对任何可计算的全函数 f,总存在源程序 c,使得执行 c 与执行 f(c) 效果完全相同(<math>\phi_c = \phi_{f(c)}</math>)——程序可以合法地引用自己的代码。 |