原始递归函数

原始递归函数属于数论函数，这些函数是从自然数(非负整数){0，1，2，...}到自然数的函数。这些函数取n个参数代表某个自然数 n，被称为n元。

基本的原始递归函由以下公理给出:

1. 常值函数：0元常量函数0是原始递归的。
2. 后继函数：1元后继函数S,返回其参数的后继函数(参见Peano假定)是原始递归的。即，S（k）= k + 1
3. 映射函数：对于每个n≥1和每个i,1≤i≤n，返回其第i个参数的n元映射函数Pin是原始递归的。

通过这些公理给出的运算，可以得到一些更为复杂的原始递归函数。

1. 组合函数：假设f是一个k元函数，k个m元函数g1,...,gk，给出f和g1,...,gk的组合，即m元函数h(x1,...,xn)=f(g1(x1,...,xn),...,gk(x1,...,xn))是一个原始递归。

举例，我们取 f（x)作为上述定义的S（x),这个f是一元原始递归函数,且g（x)= S（x)也是。因此 h（x)定义为 f（g（x)= S（S（x))也是一个原始一元递归函数。通俗地说， h（x)是将x 变成 x+2的函数。

1. 原始递归：设 f 和 g 分别是k 元和 k+2 元原始递归函数， k+1 元函数 h被定义为f和g的原始递归,即函数h是原始递归的,当:

         和

        

举例，假设 f（x)= P₁¹（x)= x 和 g（x,y,z)= S（P₂³（x,y,z)= S（y),并且 h(0，x)= x 和 h（S（y)，x)= g（y,h（y,x)，x)= S（h（y,x)),则有 h(0，1) = 1， h(1，1) = S（h(0，1)) = 2， h(2，1) = S（h(1，1)) = 3。这个h是一个二元原始递归函数,我们可以称二元递归函数h为“加法”。

对上述理论的说明:函数 h 充当从0到第一个参数值的 for 循环的角色。至于函数 h 中的其余参数 ，这里用 x_i (i = 1，..., k)表示，是for循环的一组初始条件，它可以在整个计算过程中使用，但不可被随意改变。函数 f 和 g 在定义函数 h 等式的右边，表示执行计算的循环体。函数 f 仅用于执行一次初始计算,循环的后续步骤的计算由函数 g 执行 。g 的第一个参数是For循环的“当前值”,g的第二个参数是由For循环的前一步的结果提供,g 的其余参数是前面提到的for循环的不可变初始条件。它们可被g 用于执行计算，但它们本身不会被 g 改变。

原始递归函数是基本函数,它们是基本函数通过有限次的运算获得的。

1.1 映射函数的作用

映射函数可用于避免上述函数的元数中明显的刚性问题；通过使用具有各种映射函数的组合，可以将一个函数的参数子集传递给另一个函数。例如，如果函数 g 和 h 是二元原始递归函数，那么有：

也是原始递归的。则使用映射函数的一个典型的形式定义是

1.2 将谓词转换为数值函数

在某些设置中，考虑原始递归函数是很自然的，这些函数将数字和真值(即t表示真、f 表示假)混合作为输入元组，或者将真值作为输出。^[2] 这可以通过以任何固定方式用数字识别真实值来实现。 例如，我们通常将真值 t标识为1，真值 f 标识为0。一旦进行了这种识别，则集合A的特征函数，总是返回到1或0，它就可以被看作是一个谓词，指示数字是否在集合A中。本文的中余下部分将假定使用数字函数对谓词进行标识。

1.3 计算机语言定义

原始递归编程语言的一个例子是一个包含基本算术运算符(例如+和-、条件和比较关系(IF-THEN）、等于（EQUALS）、小于（LESS-THAN）)以及诸如基本的for loop的有界循环的语言，其中，对于所有循环(FOR i从1到n，I和n都不能被循环体修改)都有一个已知的或可计算的上限。在原始递归语言中不允许使用更具通用性的控制结构，比如 while循环或IF-THEN plus GOTO。道格拉斯·霍夫斯塔德在哥德尔、埃舍尔、巴赫 中的Bloop就是如此。添加无界循环(WHILE，GOTO)会使语言部分递归，或者全图灵，Floop就是这样，几乎所有现实世界的计算机语言都是这样。

一般来说，纵使所有原始递归函数都停止了，但对于任意计算机程序或图灵机，仍不能分析判断它们也是否停止（停机问题）。这并不是矛盾的，因为原始递归程序是所有可能程序的非任意子集，是专门为可分析而构建的。

大多数在单个变量上使用递归的数论函数都是原始递归的。基本示例包括加法函数和截断减法函数。

2.1 加法

直观地说，加法可以用规则进行递归定义:

  ,

要将它放入严格的原始递归定义中，则可以定义为:

其中，是S(n)是“n的后继函数 ”(即， n+1)， P₁¹ 是识别函数， P₂³ 是映射函数它可以接受3个参数并返回第二个参数。上面定义的原始递归运算所需要的函数 f 和 g 分别由 P₁¹ 和S 和 P₂³的组合来实现。

2.2 减法

因为原始递归函数使用自然数而不是整数，并且自然数在减法下不闭合，因此本文研究了截断减法函数(也称为“适当减法”)。这个有限减法函数子(a, b)或[ b ∸ a]，如果这是非负的，则返回 b - a ，否则返回0。

前趋函数 与后继函数的作用相反，并根据规则进行递归定义:

pred(0) = 0，

pred(n +1)= 1 n。

这些规则可以通过原始递归转换为更正式的定义:

pred(0) = 0，

pred(S(n)= P ₁ ²（n，pred(n))。

有限减法函数可由前趋函数定义，其定义方式类似于由后继函数定义加法的方式:

sub(0， x)= P ₁ ¹（x)，

sub(S(n)， x)= pred(P ₂ ³（n，sub(n, x)， x))。

此处sub(a, b)对应于 b ∸ a；为了简单起见，参数的顺序已经从“标准”定义转换为符合原始递归的要求。这可以很容易地用具有合适映射组合来校正。

2.3 自然数的其他运算

指数运算和素性测试是原始递归的。给定原始递归函数 e, f, g，和 h，当 e≤f时，该函数返回 g 的函数值，否则返回 h 的函数值，这样的操作也是原始递归的。

2.4 整数和有理数的运算

通过使用哥德尔(Gödel)编码，原始递归函数可以扩展到对其他对象(如整数和 有理数）进行运算操作。 如果整数以标准方式被哥德尔数编码，则包括加法、减法和乘法在内的算术运算都是原始递归的。同样，如果有理数用哥德尔数表示，那么该领域所有运算也是原始递归的。

在一阶Peano算法中，有无限个变量(0元符号),除了S、+、*、和≤之外，没有k>0的非逻辑k元符号。因此，为了定义原始递归函数，必须使用哥德尔的以下技巧。

通过使用 序列的哥德尔编码系列，例如 哥德尔β函数，任何数字序列都可以用一个数字编码。因此，这样一个数可以表示原始递归函数，直到给定的n为止。

假设 h 是一元原始递归函数，则有如下定义:

其中C是常数，并且 g 是一个已经定义的函数。

使用哥德尔β函数，对于任何自然数序列(k₀，k₁，…，k_n)，存在自然数b和c，使得对于每个i ≤ n，有β(b，c，i) = k_i。因此，我们可以使用以下公式来定义 h；更准确地说， m=h（n)是以下内容的简写:   等同于已经定义的函数 g，实际上是一些其他已经定义的公式的简写(如β函数，这里给出了它的公式)。

采用这种算法，对任何k元原始递归函数的扩展都是比较容易的。

通过引入无界搜索算子可以定义更广泛的部分递归函数。使用该运算符可能会导致一个偏函数，即每个参数至多只有一个对应值的关系，但对于任何参数则不一定有一个任何值相对应（请参阅有关域的介绍）。一个等价的定义表明，一个部分递归函数可以由图灵机进行运算，一个完全递归函数是为每个输入定义的部分递归函数。

每个原始递归函数都是完全递归的，但不是所有的完全递归函数都是原始递归的。阿克曼函数 A（m,n)是一个众所周知的完全递归函数(实际上是可证明的完全递归函数)的例子，它不是原始递归函数。使用阿克曼函数将原始递归函数描述为完全递归函数的子集。这个特征表明一个函数是原始递归的，当且仅当存在一个自然数m，使得该函数可以由图灵机计算，该图灵机总是在A(m,n)或更少的步骤内就停止运算，其中 n 就是原始递归函数参数的总和。^[3]

原始递归函数的一个重要特性是它们是所有完全递归函数集合的递归可枚举子集(它本身不是递归可枚举的)。这意味着有一个单独的可计算的函数 f（m,n)可以枚举原始递归函数，即:

• 对于每个原始递归函数 g，存在一个 m ，使得对于所有 n 有g（n)= f（m,n)；
• 对于每一个 m，函数 h（n)= f（m,n)都是原始递归的。

f 可以通过迭代重复创建原始递归函数的所有可能的方法来显式构造。因此，它是完全可以证明的。人们可以使用对角线化参数证明这一点的论据，f本身不是递归原语:如果是这样的话，h（n)= f（n,n)+1也是如此。但是如果这等同于一些原始递归函数，那么就存在一个 m ，使得对于所有 n 有h（n)= f（m,n)，因此有 h（m)= f（m,m)，从而导致矛盾。

然而，原始递归函数集不是所有完全递归函数集合的最大递归可枚举子集。例如，可证明的全函数集(在Peano算法中)也是递归可枚举的，因为可以枚举该理论的所有证明。虽然所有的原始递归函数都可证明是完全递归的，但反过来却不是这样。

原始递归函数往往与我们对可计算函数的直觉非常接近。当然，初始函数是可以直观计算的(非常简单)，并且创建新的原始递归函数的两个操作也非常简单。然而，原始递归函数集并不包括所有可能的完全可计算函数—这可以从康托对角参数的变体中看出。这个参数提供了一个非原始递归的完全可计算函数，证据如下:

一个参数的原始递归函数(即一元函数)是可计算枚举的。该枚举使用原始递归函数的定义(本质上只是一个表达式，该表达式带有合成体和原始递归运算，如运算器以及基本的原始递归函数，如原子)，并且可以假设每个定义包含一次，即使是相同的函数将在列表中出现多次(因为许多定义定义了相同的函数；事实上，只需通过简单的恒等函数组合就可以生成无限多个原始递归函数的定义)。这意味着从 n就可以有效地确定此枚举中原始递归函数的第 n 个定义。事实上，如果使用一些哥德尔编码要将定义编码设置为数字，那么这个列表中的第 n 个定义将由 n 的原始递归函数计算。设 f_n 表示由该定义给出的一元原始递归函数，

现在通过 ev(i,j) = f_i(j)定义含有两个参数的“评价函数” ev，显然地， ev是完全可计算的，因为人们可以有效地确定 f_i 是一个原始递归函数， f_i 本身是完全可计算的，所以 f_i(j) 总是被定义为可有效计算的。然而对角线参数将表明含有两个参数的函数 ev 不是一个原始递归函数。

假设 ev 是原始递归的，那么由 g( i) = S( ev( i, i) 定义的 一元函数 g 也是原始递归的，因为它是由后继函数和 ev 的组合定义的 。然而 g 出现在枚举中，所以存在 n ，使得 g = f_n。但是现在有 g( n) = S( ev( n, n)) = S( f_n( n)) = S( g( n)，从而产生矛盾。

正如本文所述图灵机总是骤停一样，这个参数可以应用于通过这种方式枚举的任何一类可计算(全)函数。但是请意：部分可计算函数(那些不需要为所有参数定义的函数)可以显式枚举，例如通过枚举图灵机进行编码。

全递归但非原始递归函数的其他例子:

• 从 m 到 Ackermann（m,m)是一个一元完全递归函数，它不是原始递归函数。
• Paris–Harrington 定理 涉及了一个非原始递归的完全递归函数。 因为这个函数是基于Ramsey 理论的，所以它有时被认为比Ackermann函数更“自然”。
• 苏丹函数（Sudan function）
• 古德斯坦函数（ Goodstein function）

下面的例子和定义来自克莱尼（Kleene）(1952)223–231页，许多例子都有证明。在布洛斯-伯吉斯-杰弗里（Boolos-Burgess-Jeffrey）(2002)63–70页中，大多数也以相似的名字出现，或者作为证据，或者作为例子；根据精确的推导，他们加上#22号对数lo(x，y)或lg(x，y)。

在下文中，我们观察到原始递归函数可以有四种类型:

1. 函数简称：数论函数，{ 0，1，2，...}到{ 0，1，2，...}。
2. 谓词:从{ 0，1，2，...}到真实值{ t = 真，f = 假}。
3. 命题连接词:从真值{ t，f }到真值{ t，f }。
4. 表示函数:从真值{ t，f }到{ 0，1，2，...}。很多时候，谓词需要一个表示函数来将谓词的输出{ t，f }转换为{ 0，1 }(注意顺序“t”为“0”和“f”为“1”与下面定义的~sg()相匹配)。通过定义函数φ(x)是谓词P(x)的“表示函数”，当p是“真实”时，如果φ仅取值0和1，则产生为“0”。

在下文的标记“‘ ”中，例如a’，是表示原始标记“的后继”，通常被认为是“+1”，例如a +1 =_def ' a '。函数16-20和#G对于将原始递归谓词表示为哥德尔数的“算术”形式并从中提取对它们有意义的部分。

1. 加法:a+b
2. 乘法:a×b
3. 幂运算:a^b
4. 阶乘a！:0！= 1，a！= a！×a '
5. 预解码(a):(前趋或递减):如果大于0，则为a-1，否则为0
6. 适当的减法a ∸ b:如果a ≥ b，则a-b为0
7. 最小值(a₁,...a_n)
8. 最大值(a₁,...a_n)
9. 绝对差:| a-b | =_def (a ∸ b) + (b ∸ a)
10. ~sg(a):NOT[符号函数(a)]:如果a=0，则为1，否则为0
11. sg(a):符号函数(a):如果a=0，则为0，否则为1
12. a | b: (a除b):如果b=k×a代表某些k，则为0，否则为1
13. 余数(a，b):如果b不整除a而余下的数，也称为MOD(a，b)
14. a = b: sg | a - b | (Kleene的约定：由0代表真实的和由1代表假的；目前，特别是在计算机中，最常见的约定与之是相反的，即1表示真实的和0表示错误的，这相当于在此处和下一项中将sg更改为~sg)
15. a < b: sg( a' ∸ b)
16. Pr(a): a是素数Pr(a)= 1_def a>1 & NOT(存在c)_1<c<a [ c|a ]
17. p_i:第i+1个素数
18. (a)_i:pi的指数a:唯一的x，使得p_i^x|a & NOT(p_i^x'|a)
19. lh(a):a“长度”或a 中非消失指数的数量
20. lo(a，b):以b为底的a的对数

在下文中，缩写 x = _def x ₁,...x _n；如果需要，可以使用下标。

• #A: 在ψ中，可由函数ψ和常数q₁, ... q_n明确定义的函数φ是原始递归的。
• #B: 在ψ中，有限和σ_y<z ψ(x，y)和产物π_y<zψ(x，y)是原始递归的。
• #C: 在χ1，...，χm，Q中，通过将函数χ1，...，χm代入谓词Q的各个变量而获得的谓词P是原始递归的。
• #D: 下列谓词在Q和R中是原始递归的:

• • NOT_Q(x) .
  • Q或R: Q(x) V R(x),
  • Q和R: Q(x) & R(x),
  • Q包含R: Q(x) → R(x)
  • Q等同于R: Q(x) ≡ R(x)

• #E: 下列谓词在R中是递归的:

• (Ey)_y<z r(x，y)，其中(Ey)_y<z 表示“存在至少一个小于z的y，使得..”
• (y)_y<z r(x，y)，其中(y)_y<z 表示“对于所有小于z的y，是真实的”
• μy_y<z r(x，y)，运算符μy_y<z r(x，y)是一个有界限的最小化的形式 mu-运算符:定义为“y小于z的最小值，因此R(x，y)是真的；否则取 z。"

• #F: 案例定义:据此定义的函数，其中φ₁,...，Q_m 是互斥谓词 (或“ψ(x)应具有同样适用的第一个子句给出的值)，该函数在φ₁,...，Q₁,...Q_{m中是原始递归的}:

φ( x)=

• φ₁（x)如果Q₁（x)是真的，
• ..........................................
• φ_m（x)如果Q_m（x)是真的
• 否则就是φ_m+1（x)

• #G:如果φ满足方程式:

φ(y， x)= χ(y，NOT-φ(y；x ₂,...x _n )，x ₂,...x _n 那么φ在χ中是原始递归的。所以，从某种意义上说，人们对数值过程函数NOT-φ(y； x _{2 to n} )的值的认知等同于对初始函数φ(0， x _{2 to n})，...，φ(y-1， x _{2 to n})的值序列的认知。"

一些其他形式的递归也定义了实际上是原始递归的函数。这些形式定义可能更容易找到，或者更适合阅读或书写。数值过程递归定义原始递归函数，某些形式的互递归也定义原始递归函数。

在循环编程语言中可以编程的函数也正是原始递归函数，这对这些函数的能力给出了不同的特征描述。与图灵完全语言相比，在LOOP语言中，每个循环运行的次数是在循环开始运行之前就已经被指定。

原始递归函数与数学意义上的有限论密切相关，在数学逻辑中，当需要一个特别的构造系统时，它们可以在多个上下文中值序列用。 原始递归算法 (PRA)是自然数及其原始递归函数的形式公理系统，经常被用于此目的。

PRA算法远没有Peano算法那么强大，这不是一个有限的系统。然而，数论和证明论中的许多结论都可以在PRA中得到证明。例如，哥德尔不完备性定理可以形式化为PRA，给出如下定理:

如果T是一个满足一定假设的算术理论，用哥德尔命题GT，则PRA证明了蕴涵Con(T)→G_T。

同样，证明理论中的许多句法都可以在PRA中得到证明，这意味着存在执行相应证明句法转换的原始递归函数。

在证明理论和集合论中，人们对有限一致性证明感兴趣。也就是说，一致性证明本身是有限可接受的。这就证明了T理论的一致性，通过产生原始递归函数来暗示理论S的一致性，该原始递归函数可以将来自S的任何不一致证明转换为来自T的不一致证明。 一致性证明有限的一个充分条件是能够在PRA中将其形式化。例如，通过强制得到的集合论中的许多一致性结果可以从新转化为句法证明，并在PRA中形式化。

递归定义之前或多或少在数学中被正式使用过，但是原始递归的构造可以追溯到 Richard Dedekind的定理126-his Was sind und was sollen die Zahlen？ (1888年)。这项工作首次证明了某个递归结构是如何定义一个独特函数的。^[4][5][6]

原始递归算法 最初是由 Thoralf Skolem^[7] 1923年提出的。

当前的术语是在由 Ackermann在1928年证明了今天以他的名字命名的函数不是原始递归的之后，由 Rózsa Péter (1934年)创造的。这一事件促使我们需要重新命名在那之前被简单称之为递归函数的函数。^[5][6]

1. Brainerd and Landweber, 1974
2. Kleene [1952 pp. 226–227]
3. This follows from the facts that the functions of this form are the most quickly growing primitive recursive functions, and that a function is primitive recursive if and only if its time complexity is bounded by a primitive recursive function. For the former, see Linz, Peter (2011), An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, p. 332, ISBN 9781449615529. For the latter, see Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, p. 287, ISBN 9780191620805
4. Peter Smith (2013). An Introduction to Gödel's Theorems (2nd ed.). Cambridge University Press. pp. 98–99. ISBN 978-1-107-02284-3.
5. George Tourlakis (2003). Lectures in Logic and Set Theory: Volume 1, Mathematical Logic. Cambridge University Press. p. 129. ISBN 978-1-139-43942-8.
6. Rod Downey, ed. (2014). Turing's Legacy: Developments from Turing's Ideas in Logic. Cambridge University Press. p. 474. ISBN 978-1-107-04348-0.
7. Thoralf Skolem (1923) "The foundations of elementary arithmetic" in Jean van Heijenoort, translator and ed. (1967) From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 302-33.