Question

证明以下函数是递归的

Answer 1

问：证明以下函数是递归的

答：亲~我正在编辑这道题的答案，还请您耐心等待一下。

答：若为部分递归函数，则存在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的最小不动点。第一和第二不动点定理之名称纯粹是由克林的经典著作《元数学导论》中表述的先后次序而定的，别无他意。此外，在许多文献中，上述的(第二)不动点定理也称为递归定理而不加区分。