递归函数

在数理逻辑和计算机科学中，一般递归函数、部分递归函数或 μ 递归函数是从自然数到自然数的部分函数，在直觉和形式上都是可计算的。 如果函数是全函数，则也称为全递归函数（有时简称为递归函数）。 在可计算性理论中，表明μ-递归函数正是图灵机可以计算的函数（这是支持丘奇-图灵论题的定理之一）。 μ-递归函数与原始递归函数密切相关，它们的归纳定义（如下）建立在原始递归函数的基础上。 然而，并非每个全递归函数都是原始递归函数——最著名的例子是阿克曼函数。

其他等效的函数类是 lambda 演算的函数和可以通过马尔可夫算法计算的函数。

具有 {0,1} 值的所有总递归函数的子集在计算复杂性理论中被称为复杂性类 R。

μ-递归函数（或一般递归函数）是部分函数，它采用自然数的有限元组并返回单个自然数。 它们是最小的部分函数类，包括初始函数并且在组合、原始递归和 μ 运算符下是封闭的。

最小的函数类包括初始函数和封闭组合和原始递归（即没有最小化）是原始递归函数类。 虽然所有原始递归函数都是全递归函数，但部分递归函数并非如此； 例如，后继函数的最小化是未定义的。 原始递归函数是总递归函数的子集，总递归函数是部分递归函数的子集。 例如，阿克曼函数可以被证明是完全递归的，并且是非原始的。

原始或基本功能：

• 常数函数 Ck_{n: 对于每个自然数 n 和每个 kC n k ( x 1 , … , x k ) = d e f n {\displaystyle C_{n}{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n }替代定义使用零函数作为始终返回零的原始函数，并从零函数、后继函数和组合运算符构建常量函数。}
• 后继函数 S:S ( x ) = d e f x + 1 {\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,
• 投影函数 P i k {\displaystyle P_{i}{k}}（也称为恒等函数）

运算符（由运算符定义的函数的域是参数值的集合，以便在计算期间必须完成的每个函数应用程序都提供明确定义的结果）

原始递归运算符 ρ：给定 k 元函数 g ( x 1 , … , x k ) {\displaystyle g(x_{1},\ldots ,x_{k})\,} 和 k+ 二元函数