原始递归函数

在可计算性理论中，原始递归函数粗略地说就是一个可以被计算机程序计算的函数，其循环都是for循环（即在进入循环之前可以确定每个循环的迭代次数的上限） . 原始递归函数构成那些也是全函数的一般递归函数的严格子集。

原始递归函数的重要性在于这样一个事实，即在数论（以及更普遍的数学）中研究的大多数可计算函数都是原始递归函数。 例如，加法和除法、阶乘和指数函数以及返回第 n 个素数的函数都是原始递归的。 事实上，为了证明一个可计算函数是原始递归的，只要证明它的时间复杂度受输入大小的原始递归函数的限制就足够了。 因此，设计一个非原始递归的可计算函数并不容易； 下面的§ 限制部分显示了一些示例。

这组原始递归函数在计算复杂性理论中被称为 PR。

原始递归函数采用固定数量的参数，每个参数都是自然数（非负整数：{0, 1, 2, ...}），并返回一个自然数。 如果它有 n 个参数，它被称为 n-ary。

这些公理给出了基本的原始递归函数：

• 常数函数ck_{n: 对于每个自然数n和每个k，定义的k元常数函数 通过 C n k ( x 1 , … , x k ) = d e f n {\displaystyle C_{n}{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n} ，是原始递归。}
• 后继函数：一元后继函数 S，它返回其参数的后继（见 Peano 假设），即 S ( x ) = d e f x + 1 {\displaystyle S(x)\ { \stackrel {\mathrm {def} }{=}}\ x+1} ，是原始递归。
• 投影函数 P i k {\displaystyle P_{i}{k}} ：对于所有自然数 i , k {\displaystyle i,k} 使得 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} ，由 P i k ( x 1 , … , x k ) = d e f x i {\displaystyle P_{i}{k}(x_{1},\ldots ,x_{ k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}} 是原始递归。

通过应用这些公理给出的操作可以获得更复杂的原始递归函数：

• 复合运算符 ∘ {\displaystyle \circ \,}（也称为替换运算符）：给定一个多元函数 h ( x 1 , … , x m ) {\displaystyle h(x_{1} ,\ldots ,x_{m})\,} 和 m 个 k 元函数 g 1 ( x 1 , … , x k ) , … , g m ( x 1 , … , x k ) {\displaystyle g_{1} (x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})} : h ∘ ( g 1 , … , g m ) = d e f f，其中 f ( x 1 , … , x k ) = h ( g 1 ( x 1 , … , x k ) , … , g m (x 1 , … , x k )) 。 {\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad { text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ ldots ,g_{m}(x_{1},\ldots ,x_{k})).}

• 原始递归运算符 ρ：给定 k 元函数 g ( x 1 , … , x k ) {\displaystyle g(x_{1},\ldots ,x_{k})\,} 和 ( k + 2)-ary 函数 h ( y , z , x 1 , … , x k ) {\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,} : ρ ( g , h ) = d e f f ，其中 ( k + 1 ) 元函数 f 由 f ( 0 , x 1 , … , x k ) = g ( x 1 , … , x k ) f ( S ( y ) , x 1 , … , x k ) = h ( y , f ( y , x 1 , … , x k ) , x 1 , … , x k ) 。 {\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text {其中 }}(k+1){\text{-ary 函数 }}f{\text{ 由}}\\f(0,x_{1},\ldots ,x_{ k})&=g(x_{1},\ldots,x_{k})\\f(S(y),x_{1},\ldots,x_{k})&= h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}解释：函数 f 充当从 0 到xxx个参数值的 for 循环。 f 的其余参数（此处用 x1、...、xk 表示）是 for 循环的一组初始条件，可在计算期间使用但不可更改。 定义 f 的方程式右侧的函数 g 和 h 代表执行计算的循环体。 函数 g 仅用于执行初始计算一次。 循环的后续步骤的计算由 h 执行。 h 的xxx个参数是 for 循环索引的当前值。 h 的第二个参数是来自前面步骤的 for 循环先前计算的结果。 h 的其余参数是前面提到的 for 循环的不可变初始条件。 它们可能会被 h 用来执行计算，但它们本身不会被 h 更改。