递归函数

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）创建在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。

其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。

所有递归函数的集合叫做R。

μ-递归函数（或偏μ-递归函数）是接受自然数的有限元组并并返回一个单一自然数的偏函数。它们是包括初始函数并闭合在复合、原始递归和μ算子下的最小的偏函数类。

包括初始函数并闭合在复合和原始递归下的（就是说使用前五个函数定义的）最小的函数类是原始递归函数类。所有原始递归函数都是全函数。需要第六个或"μ算子"是因为不是所有全函数都可以只用五个原始递归函数来计算（比如阿克曼函数）。在这些实例中μ算子终止运算。它充当无界查找算子，无界但仍然（通过全函数定义）被某种方式（比如归纳证明）证明为最终生成一个数并终止运算。

但是，如果无界μ算子自身是偏函数 -- 就是说存在某个数它不能为其返回一个数 -- 使用它的函数将也是偏函数 -- 对某些数没有定义。在这些实例中，因为它是无界的，μ算子将永远查找，永不通过生成一个数而终止运算。（某些算法可以采用可以生成指示“不可判定”的符号"u"并以此终止运算的u-算子（cf Kleene（1952）pp. 328ff））。换句话说：使用偏μ算子的偏μ-递归函数可能不是全函数。全μ-递归函数的集合是全函数的偏μ-递归函数的子集。

前三个函数叫做"初始"或"基本"函数：（Kleene (1952) p. 219）：

强等于算子${\displaystyle \simeq <!--\; \simeq \; -->}$和定义的所以

成立，当且仅当对于参数的任何选择要么两个函数都有定义并且它们的值相等要么两个函数都是未定义的。

在可计算性模型的等价中在对特定输入不终止的图灵机和对这个输入得到未定义结果的相应偏递归函数之间是平行/并列的。无界查找运算是不能通过原始递归的规则定义的，因为它们不提供"无限循环"（未定义值）的机制。

范式定理源于Kleene声称对于每个有原始递归函数${\displaystyle U(y)}$个自由变量的μ-递归函数${\displaystyle f(x_1,\dots <!--\; \dots \; -->,x_k)}$使得

数被叫做函数的索引或哥德尔数。这个结果的一个结论是任何μ-递归函数都可以使用把μ算子应用于（全）原始递归函数的一个单一实例来定义。

Minsky (1967)(同样Boolos-Burgess-Jeffrey (2002) pp. 94-95)观察到上面定义的U在本质上是通用图灵机的μ-递归等价物：