查看“︁递归函数”︁的源代码

{{noteTA
|G1=IT
}}

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

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

所有递归函数的集合叫做[[R (复杂性)|R]]。

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

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

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

前三个函数叫做"初始"或"基本"函数：（Kleene (1952) p. 219）：
:*（1）'''常数函数：'''对于每个自然数''n''和所有的''k'':
::<math>f(x_1,\ldots,x_k) = n</math>。
::::有时这个常数通过重复使用后继函数和叫做"初始对象0（零）"的对象来生成（Kleene (1952) p.?)<!--
<math>\lambda x_1,\ldots,x_k[n]</math> is initial.-->
:*（2）'''后继函数S:''' "从已经生成的对象到另一个对象n+1或n'（''n''的''后继者''）"（ibid）。
:: S(x) ≡<sub>def</sub>  f(x) = x' = x +1
:*（3）'''投影函数P<sub>i</sub><sup>k</sup>'''（也叫做'''恒等函数I<sub>i</sub><sup>k</sup>'''）:对于所有自然数''i''使得<math>1 \le i \le k</math>:
:: P<sub>i</sub><sup>k</sup><math>(x_1,\ldots,x_k)</math> =<sub>def</sub>    <math>f(x_1,\ldots,x_k) = x_i</math>.<!--
<math>\lambda x_1,\ldots,x_k [x_i]</math> is an initial function,-->
*（4）'''复合算子：'''复合也叫做'''代换'''，接受一个函数<math>h(x_1,\ldots,x_m)</math>和函数<math>g_i(x_1,\ldots,x_k)</math>对每个''i''有<math>1 \le i \leq m</math>，并返回映射''x''<sub>1</sub>, ... ''x''<sub>k</sub>到
:<math>f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))</math>的一个函数。
*（5）'''原始递归算子：'''接受函数<math>g(x_1,\ldots,x_k)</math>和<math>h(y,z,x_1,\ldots,x_k)</math>并返回唯一的函数<math>f</math>使得
: <math>f(0,x_1,\ldots,x_k) = g(x_1,\ldots,x_k)</math>,
: <math>f(y+1,x_1,\ldots,x_k) = h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)</math>。
*（6）'''μ算子'''：μ算子接受一个函数<math>f(y,x_1,\ldots, x_k)</math>并返回函数<math>\mu y f(y,x_1,\ldots,x_k)</math>，它的参数是x<sub>1</sub> , . . ., x<sub>k</sub>。这个函数<math>f</math>要么是从自然数{ 0, 1, ... n }到自然数{ 0, 1, ... n }的数论函数，要么是运算于[[关系 (数学)|谓词]](输出{ t, f })上生成{ 0, 1 }的[[表示函数]]。

:在任何一个情况下：这个函数μ''y'' ''f''返回最小的自然数<math>y</math>使得，如果这样的''y''存在，则''f''(0,''x''<sub>1</sub>,''x''<sub>2</sub>,...,''x''<sub>''k''</sub>), ''f''(1,''x''<sub>1</sub>,''x''<sub>2</sub>,...,''x''<sub>''k''</sub>), ..., ''f''(''y'',''x''<sub>1</sub>,''x''<sub>2</sub>,...,''x''<sub>''k''</sub>)都是有定义的，并且''f''(''y'',''x''<sub>1</sub>,''x''<sub>2</sub>,...,''x''<sub>''k''</sub>) = 0；如果这样的''y''不存在，则μ''y'' ''f''是对特定参数''x''<sub>1</sub>,...,''x''<sub>''k''</sub>是未定义的。

'''强等于'''算子<math>\simeq</math>被用来比较偏μ-递归函数。这是对所有偏函数''f''和''g''定义的所以
:<math>f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)</math>
成立，当且仅当对于参数的任何选择要么两个函数都有定义并且它们的值相等要么两个函数都是未定义的。

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

== 范式定理 ==
'''范式定理'''源于Kleene声称对于每个''k''有原始递归函数<math>U(y)\!</math>和<math>T(y,e,x_1,\ldots,x_k)\!</math>使得对于任何''k''个自由变量的μ-递归函数<math>f(x_1,\ldots,x_k)\!</math>有一个''e''使得
:<math>f(x_1,\ldots,x_k) \simeq U(\mu y\, T(y,e,x_1,\ldots,x_k))</math>。
数''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函数]]

==参见==
* [[递归]]
* [[递归 (计算机科学)]]
* [[库尔特·哥德尔]]

==外部链接==
*[http://plato.stanford.edu/entries/recursive-functions/ Stanford Encyclopedia of Philosophy entry] {{Wayback|url=http://plato.stanford.edu/entries/recursive-functions/ |date=20210128153137 }}

== 引用 ==
*[[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.

{{CPU technologies}}

[[Category:递归论]]
[[Category:函数]]