原始递归函数

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

在可计算性理论中，原始递归函数对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。

通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的(Brainerd and Landweber, 1974)。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如阿克曼函数)。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。

原始递归函数可以用总是停机的图灵机计算，而递归函数需要图灵完全系统。

原始递归函数的集合在计算复杂性理论中叫做PR。

目录 1 定义 2 例子 2.1 加法 2.2 减法 3 限制 4 参考 5 参见

[编辑] 定义

原始递归函数接受自然数或自然数的元组作为参数并生成自然数。接受 n 个参数的函数叫做 n-元函数。基本原始递归函数用如下公理给出:

1. 常函数 0 是原始递归的。
2. 后继函数 S，它接受一个参数并返回皮亚诺公理给出的后继数，是原始递归的。
3. 投影函数 P_iⁿ，它接受 n 个参数并返回它们中的第 i 个参数，是原始递归的。

更加复杂的递归函数可以通过应用下列公理给出的运算来获得:

1. 复合: 给定 k-元原始递归函数 f，和 k 个 l-元原始递归函数g₀,...,g_k−1， f 与 g₀,...,g_k-1 的复合，就是说，函数 h(x₀,...,x_l-1) = f(g₀(x₀,...,x_l−1),...,g_k−1(x₀,...,x_l-1)) 是原始递归的。
2. 原始递归: 给定 k-元原始递归函数 f，和 (k+2)元原始递归函数 g，被定义为 f 和 g 的原始递归的 (k+1)-元函数，就是说，函数 h 这里的 h(0,x₀,...,x_k−1) = f(x₀,...,x_k−1) 并且 h(S(n),x₀,...,x_k−1) = g(h(n,x₀,...,x_k−1),n,x₀,...,x_k−1)，是原始递归的。

投影函数允许我们按上述函数的元数来得到严格的外在形式，因为通过复合我们可以传递参数的任何子集。

服从这些公理的函数是原始递归的，如果它是上述基本函数之一，或者它可以通过应用有限次数的运算获得自基本函数。

[编辑] 例子

[编辑] 加法

直觉上我们会把加法递归的定义为:

add(0,x)=x

add(n+1,x)=add(n,x)+1

为了使它适合于严格的原始递归定义,我们定义:

add(0,x)=P₁¹(x)

add(S(n),x)=S(P₁³(add(n,x),n,x))

(注意: 这里的 P₁³ 是一个函数，它接受 3 个参数并返回第一个。)

P₁¹ 是简单的恒等函数；包含它是上述原始递归运算定义的要求；它扮演了 f 的角色。S 和 P₁³ 的复合，它是原始递归的，它扮演了 g 的角色。

[编辑] 减法

我们可以定义有限减法，就是说，截止到 0 的减法(因为我们还没有负数的概念呢)。首先我们必须定义"前驱" 函数，它担任后继函数的对立物。

直觉上我们会把前驱定义为:

pred(0)=0

pred(n+1)=n

为了使它适合正式的原始递归定义，我们写:

pred(0)=0

pred(S(n))=P₂²(pred(n),n)

现在我们以类似加法的方式定义减法。

sub(0,x)=P₁¹(x)

sub(S(n),x)=pred(P₁³(sub(n,x),n,x))

出于简单的缘故，切换了"标准"定义的参数次序来适合原始递归的要求，就是说， sub(a,b) 对应于 b-a。这可以轻易的使用适当的投影来矫正。

很多类似的函数可以被证明是原始递归的；一些例子包括条件、指数、素数检验和数学归纳法，并且原始递归函数可以被扩展来运算在其他对象上比如整数和有理数。

[编辑] 限制

原始递归函数意图紧密对应于我们直觉上可计算函数应该的样子。当然函数的初始集合在直觉上是可计算的(因为它们非常简单)，而你能用来建立新原始递归函数的两个运算也是非常直接的。但是原始递归函数的集合不包含所有可能的可计算函数 — 这可以看作康拖尔对角论证法的变体。这个论证提供了一个不是原始递归的可计算函数。证明的梗概如下:

原始递归函数集合可以被计算枚举。这个编号方案在函数定义上是唯一的，尽管在实际函数自身上不是唯一的(因为所有的函数都可以有无限数目的定义 — 考虑简单的由恒等函数构成)。这个编码在可计算性的形式模型，比如递归函数或图灵机下定义的意义上是可计算的，邱奇-图灵论题涉及的任何机器都可以。

现在考虑一个矩阵，这里的行是在这个编号方案下的有一个参数的原始递归函数，而列是自然数。则每个元素 (i, j) 对应于计算于数 j 之上的第 i 个一元原始递归函数。我们可以写为 f_i(j)。

现在我们考虑函数 g(x) = S(f_x(x))。g 位于这个矩阵的对角线上，并简单的对它找到的值加一。这个函数是可计算的(按上述定义)，但是明显的没有计算它的原始递归函数存在，因为它与每个可能的原始递归函数都有至少一个值不同。所以，必然存在不是原始递归的可计算函数。

这个论证可以应用于能用这种方式枚举的任何一类的可计算(全)函数上。所以，任何这种可计算(全)函数的明确列表都不可能是完全的，比如那些可以用总是停机的机器计算的函数。但是要注意，偏可计算函数集合(那些不需要对所有参数有定义的函数)可以被明确的枚举，例如通过枚举图灵机编码。

可以明确展示的一个简单的 1-元可计算函数阿克曼函數，它是对任何自然数递归定义的，但不是原始递归的。

[编辑] 参考

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0471095850

[编辑] 参见

• 判定器