当前位置：新励学网 > 秒知问答 > 递归定理的证明

递归定理的证明

发表时间：2024-07-28 03:19:55 来源：网友投稿

递归定理的原始形式（特称为第二递归定理）为：若为部分递归函数，则存在e，使得与第二递归定理等价的是下列不动点定理：对任何递归函数f，存在自然数n(称为f的不动点)，使φn=φf(n)。不动点定理有一些推广的形式：带参数的递归定理。若f为n+1元递归函数，则存在一一的n元递归函数h，使2.二重递归定理.对递归函数f，g，存在自然数a，b，使得：φa=φf(a，b) φb=φg(a，b).

对一个递归函数f，其不动点不仅存在，而且一定有无穷多个，它们所组成的集合可能是递归集，也可能是非递归的.值得指出的是，对部分递归函数，其不动点定理与第二递归定理是等价的，但两者的证明所需要的基础并不一样.前者依赖于Sm定理和枚举定理，而后者则仅依赖于Sm定理.所以若一个函数类具有Sm性质但不具有枚举性(如原始递归函数类)，则第二递归定理对它也成立，而不动点定理则不然.与第二递归定理相对应的是关于部分递归泛函的第一不动点定理(美国逻辑学家、数学家克林(Kleene，S.C.)，于1952年证明的)：设F(α，x)为部分递归泛函，则存在一个部分递归函数α，使得：

1.ᗄx(α(x)=F(α，x));

2.ᗄx(β(x)=F(β，x))→α⊆β;

此时α称为F的最小不动点。第一和第二不动点定理之名称纯粹是由克林的经典著作《元数学导论》中表述的先后次序而定的，别无他意。

另外在许多文献中，上述的(第二)不动点定理也称为递归定理而不加区分。

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！