3,094
个编辑
更改
跳到导航
跳到搜索
第160行：
第160行： − + −
→与第二递归定理的关系
=== 与第二递归定理的关系 ===
=== 与第二递归定理的关系 ===
Rogers 证明了：'''第二递归定理（强）蕴含第一递归定理（弱）'''——存在统一的机械方法，把"函数层面的不动点问题"翻译成"代码层面的不动点问题"，并且翻译后得到的不动点恰好是'''最小'''的<ref name="rogers1967" />。反过来不成立：第五、六节中第二递归定理的应用几乎都无法由第一递归定理得到。因此两者中'''第二递归定理更基本、更强大'''<ref name="rogers1967" />。
Rogers 证明了：'''第二递归定理（强）蕴含第一递归定理（弱）'''——存在统一的机械方法，把"函数层面的不动点问题"翻译成"代码层面的不动点问题"，并且翻译后得到的不动点恰好是'''最小'''的<ref name="rogers1967" />。反过来不成立：第[[第二递归定理（SRT）|五]]节中第二递归定理的应用几乎都无法由第一递归定理得到。因此两者中'''第二递归定理更基本、更强大'''<ref name="rogers1967" />。
Moschovakis 还给出了一个'''统一形式'''：把"变换规则"同时允许依赖于"函数的编号"和"函数的值"，所得不动点定理在两种极端情形下分别退化为第二递归定理（不依赖函数值）和第一递归定理（不依赖编号）<ref name="moschovakis2010" />。
Moschovakis 还给出了一个'''统一形式'''：把"变换规则"同时允许依赖于"函数的编号"和"函数的值"，所得不动点定理在两种极端情形下分别退化为第二递归定理（不依赖函数值）和第一递归定理（不依赖编号）<ref name="moschovakis2010" />。
== 第二递归定理（SRT） ==
== 第二递归定理（SRT） ==