更改

跳到导航 跳到搜索
大小无更改 、 2026年9月10日 (星期四)
第11行: 第11行:  
'''第二递归定理(日常语言版)''':''对任何可计算的全函数 <math>f</math>(一个对任何输入都停机的"程序变换"),总存在一个源程序 <math>c</math>,使得执行 <math>c</math> 的效果,等同于执行 <math>f(c)</math>——即 <math>f</math> 拿着 <math>c</math> 自己的源代码算出来的那个程序。'' 用符号写就是:<math>\phi_c = \phi_{f(c)}</math><ref name="rogers1967">'''Rogers, H., Jr. (1967).''' ''Theory of Recursive Functions and Effective Computability''. McGraw-Hill. 第 11 章 The Recursion Theorem, pp. 179–222.【教科书标准表述;第一/第二递归定理的命名来源】</ref>.
 
'''第二递归定理(日常语言版)''':''对任何可计算的全函数 <math>f</math>(一个对任何输入都停机的"程序变换"),总存在一个源程序 <math>c</math>,使得执行 <math>c</math> 的效果,等同于执行 <math>f(c)</math>——即 <math>f</math> 拿着 <math>c</math> 自己的源代码算出来的那个程序。'' 用符号写就是:<math>\phi_c = \phi_{f(c)}</math><ref name="rogers1967">'''Rogers, H., Jr. (1967).''' ''Theory of Recursive Functions and Effective Computability''. McGraw-Hill. 第 11 章 The Recursion Theorem, pp. 179–222.【教科书标准表述;第一/第二递归定理的命名来源】</ref>.
   −
'''第一递归定理(日常语言版)''':''任何递归定义——即把一个函数在某处的值,写成它自己在其他输入上的值(比如阶乘 <math>fac(n) = n\cdot fac(n−1)</math>)——都必然有解'' ,而且其中"最小"的那个解一定能被机器算出。换句话说,'''机械式的递归定义永远合法、永远有解'''。<ref name="rogers1967" />
+
'''第一递归定理(日常语言版)''':''任何递归定义——即把一个函数在某处的值,写成它自己在其他输入上的值(比如阶乘 <math>fac(n) = n\cdot fac(n−1)</math>)——都必然有解'' ,而且其中"最小"的那个解一定能被机器算出。换句话说,'''机械式的递归定义永远合法、永远有解'''<ref name="rogers1967" />。
    
两个定理的对照表(其中涉及的符号会在第二节逐一解释,此处可先跳过细节):
 
两个定理的对照表(其中涉及的符号会在第二节逐一解释,此处可先跳过细节):

导航菜单