递归函数

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

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

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

定义

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

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

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

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

• （1）常数函数：对于每个自然数n和所有的k:

${\displaystyle f(x_{1},\ldots ,x_{k})=n}$。

有时这个常数通过重复使用后继函数和叫做"初始对象0（零）"的对象来生成（Kleene (1952) p.?)

• （2）后继函数S: "从已经生成的对象到另一个对象n+1或n'（n的后继者）"（ibid）。

S(x) ≡_def f(x) = x' = x +1

• （3）投影函数P_i^k（也叫做恒等函数I_i^k）:对于所有自然数i使得${\displaystyle 1\leq i\leq k}$:

P_i^k${\displaystyle (x_{1},\ldots ,x_{k})}$ =_def ${\displaystyle f(x_{1},\ldots ,x_{k})=x_{i}}$.

• （4）复合算子：复合也叫做代换，接受一个函数${\displaystyle h(x_{1},\ldots ,x_{m})}$和函数${\displaystyle g_{i}(x_{1},\ldots ,x_{k})}$对每个i有${\displaystyle 1\leq i\leq m}$，并返回映射x₁, ... x_k到

${\displaystyle f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}$的一个函数。

• （5）原始递归算子：接受函数${\displaystyle g(x_{1},\ldots ,x_{k})}$和${\displaystyle h(y,z,x_{1},\ldots ,x_{k})}$并返回唯一的函数${\displaystyle f}$使得

${\displaystyle f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,x_{k})}$,

${\displaystyle f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}$。

• （6）μ算子：μ算子接受一个函数${\displaystyle f(y,x_{1},\ldots ,x_{k})}$并返回函数${\displaystyle \mu yf(y,x_{1},\ldots ,x_{k})}$，它的参数是x₁ , . . ., x_k。这个函数${\displaystyle f}$要么是从自然数{ 0, 1, ... n }到自然数{ 0, 1, ... n }的数论函数，要么是运算于谓词(输出{ t, f })上生成{ 0, 1 }的表示函数。

在任何一个情况下：这个函数μy f返回最小的自然数${\displaystyle y}$使得，如果这样的y存在，则f(0,x₁,x₂,...,x_k), f(1,x₁,x₂,...,x_k), ..., f(y,x₁,x₂,...,x_k)都是有定义的，并且f(y,x₁,x₂,...,x_k) = 0；如果这样的y不存在，则μy f是对特定参数x₁,...,x_k是未定义的。

强等于算子${\displaystyle \simeq }$被用来比较偏μ-递归函数。这是对所有偏函数f和g定义的所以

${\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}$

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

同其他模型的等价性

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

范式定理

范式定理源于Kleene声称对于每个k有原始递归函数${\displaystyle U(y)\!}$和${\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}$使得对于任何k个自由变量的μ-递归函数${\displaystyle f(x_{1},\ldots ,x_{k})\!}$有一个e使得

${\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))}$。

数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）。

例子

• 斐波那契数列
• McCarthy 91函数

参见

• 递归
• 递归 (计算机科学)
• 库尔特·哥德尔

外部链接

• Stanford Encyclopedia of Philosophy entry （页面存档备份，存于互联网档案馆）

引用

• Stephen Kleene（1952）Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression 1991, ISBN 0-7204-2103-9.
• Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.
• Marvin L. Minsky（1967）, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.

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.

• George Boolos、John Burgess、Richard Jeffrey（2002）, Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70-71.