递归函数

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

递归函数

点击查看词条快照

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。所有递归函数的集合叫做R。定义. μ-递归函数（或偏μ-递归函数）是接受自然数的有限元组并并返回一个单一自然数的偏函数。它们是包括初始函数并闭合在复合、原始递归和μ算子下的最小的偏函数类。包括初始函数并闭合在复合和原始递归下的（就是说使用前五个函数定义的）最小的函数类是原始递归函数类。所有原始递归函数都是全函数。需要第六个或"μ算子"是因为不是所有全函数都可以只用五个原始递归函数来计算（比如阿克曼函数）。在这些实例中μ算子终止运算。它充当无界查找算子，无界但仍然（通过全函数定义）被某种方式（比如归纳证明）证明为最终生成一个数并终止运算。但是，如果无界μ算子自身是偏函数 -- 就是说存在某个数它不能为其返回一个数 -- 使用它的函数将也是偏函数 -- 对某些数没有定义。在这些实例中，因为它是无界的，μ算子将永远查找，永不通过生成一个数而终止运算。（某些算法可以采用可以生成指示“不可判定”的符号"u"并以此终止运算的u-算子（cf Kleene（1952）pp. 328ff））。换句话说：使用偏μ算子的偏μ-递归函数可能不是全函数。全μ-递归函数的集合是全函数的偏μ-递归函数的子集。前三个函数叫做"初始"或"基本"函数：（Kleene (1952) p. 219）： *（1）常数函数：对于每个自然数"n"和所有的"k": formula_1。有时这个常数通过重复使用后继函数和叫做"初始对象0（零）"的对象来生成（Kleene (1952) p.?) *（2）后继函数S: "从已经生成的对象到另一个对象n+1或n'（"n"的"后继者"）"（ibid）。 S(x) ≡def f(x) = x' = x +1 *（3）投影函数Pik（也叫做恒等函数Iik）:对于所有自然数"i"使得formula_2: Pikformula_3 =def formula_4. formula_8的一个函数。 formula_12, formula_13。在任何一个情况下：这个函数μ"y" "f"返回最小的自然数formula_17使得，如果这样的"y"存在，则"f"(0,"x"1,"x"2...,"x""k"), "f"(1,"x"1,"x"2...,"x""k"), ..., "f"("y","x"1,"x"2...,"x""k")都是有定义的，并且"f"("y","x"1,"x"2...,"x""k") = 0；如果这样的"y"不存在，则μ"y" "f"是对特定参数"x"1...,"x""k"是未定义的。强等于算子formula_18被用来比较偏μ-递归函数。这是对所有偏函数"f"和"g"定义的所以 formula_19 成立，当且仅当对于参数的任何选择要么两个函数都有定义并且它们的值相等要么两个函数都是未定义的。同其他模型的等价性. 在可计算性模型的等价中在对特定输入不终止的图灵机和对这个输入得到未定义结果的相应偏递归函数之间是平行/并列的。无界查找运算是不能通过原始递归的规则定义的，因为它们不提供"无限循环"（未定义值）的机制。范式定理. 范式定理源于Kleene声称对于每个"k"有原始递归函数formula_20和formula_21使得对于任何"k"个自由变量的μ-递归函数formula_22有一个"e"使得 formula_23。数"e"被叫做函数"f"的索引或哥德尔数。这个结果的一个结论是任何μ-递归函数都可以使用把μ算子应用于（全）原始递归函数的一个单一实例来定义。 Minsky (1967)(同样Boolos-Burgess-Jeffrey (2002) pp. 94-95)观察到上面定义的U在本质上是通用图灵机的μ-递归等价物： “要构造U就是写下通用递归函数U(n, x)的定义，它正确的解释数n并计算x的适当的函数。要直接构造U涉及与我们在构造通用图灵机的研究中本质上同量的努力，"和本质上同样的想法"”（italics in original, Minsky (1967) p. 189）。 On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

采花节

浦项市

撒都该人

八水绕长安

小德意志

黄麻地

林锦公路

威利·梅斯

冯两努

回旋镖 (电视频道)

黑沙水库郊野公园

大德意志