递归函数

维基百科，自由的百科全书

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的" 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最著名的这种函数是阿克曼函数。

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

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

[编辑] 定义

接受原始递归函数的公理作为公理，但是为允许偏函数而扩展了定义。进一步增加了无界查找运算，定义如下:

如果 f(x,z₁,z₂,...,z_n) 是带有 n+1 个参数的 x, z₁,...,z_n 的在自然数上的偏函数，则函数 μx f 是带有参数 z₁,...,z_n 的偏函数，返回最小的 x 使得f(0,z₁,z₂,...,z_n), f(1,z₁,z₂,...,z_n), ..., f(x,z₁,z₂,...,z_n) 全部是已定义的，并且 f(x,z₁,z₂,...,z_n) = 0，如果有这样一个 x 存在的话；如果没有这样的 x 存在，则 μx f 对于特定参数 z₁,...,z_n 是未定义的。

很容易看出这个最小查找公理(与简单原始递归公理一起)蕴涵了原始递归的有界查找公理。

偏递归函数的集合被定义为从自然数到自然数的任何元数的偏函数的最小集合，它包含零、后续、和投影函数，并且它闭合在复合、原始递归和无界查找下。

全递归函数的集合是是全函数的偏递归函数的子集。

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

注意到如果上述定义的无界查找运算的应用被严格的限制于正规函数(在无界查找运算作用于它们的时候保证是全函数的函数)，则结果集合(历史上叫做一般递归函数)同于递归函数的集合 -- 换句话说，对偏函数的要求可以部分的排除。