3,094
个编辑
更改
跳到导航
跳到搜索
第341行：
第341行： + + + + + + + +
→Uniform 形式
* 该定理的证明如何构造？把 §[[#证明|5.2]] 展开版证明逐步查一遍——第 0 步用 s-m-n 造 <math>\theta</math> 的编号（原始递归操作），第 2 步 <math>f = S(e,e)</math>（S 原始递归）——每一步都是编号上的原始递归运算。所以复合出来的 <math>e \Longrightarrow f</math> 就是那个 <math>r</math>，原始递归。这也是为什么说 Kleene 1938/1952 的原始证明“实际上已经是 uniform 的”：证明即算法。
* 该定理的证明如何构造？把 §[[#证明|5.2]] 展开版证明逐步查一遍——第 0 步用 s-m-n 造 <math>\theta</math> 的编号（原始递归操作），第 2 步 <math>f = S(e,e)</math>（S 原始递归）——每一步都是编号上的原始递归运算。所以复合出来的 <math>e \Longrightarrow f</math> 就是那个 <math>r</math>，原始递归。这也是为什么说 Kleene 1938/1952 的原始证明“实际上已经是 uniform 的”：证明即算法。
不难理解，{{EquationNote|表述B}}也可以改写为Uniform的形式：
* 存在全可计算函数<math>r</math>，使得对任意的自然数<math>n</math>，如果<math>\phi_n</math>全可计算，则：
:<math>
\phi_{r(n)}\simeq \phi_{\phi_n(r(n))}
</math>
不难看出，这里的<math>n</math>就是{{EquationNote|表述B}}中的<math>f</math>的编号。这样{{EquationNote|表述B}}就可以自然变成上式的形式。
====Smullyan双递归定理====
====Smullyan双递归定理====