原始递归函数

计算 $f(\mathbf{x},n)$ 可以先求 $g(\mathbf{x})$，再把状态依次更新恰好 $n$ 次。每一轮调用的 $h$ 已经有自己的有限构造，因此不会在更新时凭空引入未知是否终止的搜索。这类似循环次数在进入该循环时已经确定的程序；嵌套循环的次数可以依赖外层状态，并不要求整个程序所有次数都预先是某个固定常数。

这一限制约束的是构造能力，不是增长速度的简单阈值。指数、阶乘以及固定层数的迭代指数都能原始递归地构造；所以“增长很快”不足以证明非原始递归，“源码用了递归”也不足以证明属于原始递归类。

从算术公式到可核验的构造证书 ​

自然数条目已经用递归建立了加法和乘法。这里要检查的是：它们的初值、更新是否确实由允许的函数拼成，而不是重新证明算术公理。

记原始递归构造为 $R(g,h)$。加法的初值是 $P_1^1$，更新函数是 $S\circ P_3^3$，因此

乘法使用这个已经构造出的加法：初值为 $Z_1$，更新函数为

于是 $\mathrm{mul}=R(Z_1,h)$。输入 $(3,4)$ 时，状态从 $0$ 开始，每一步调用已有的 $\mathrm{add}$，依次得到 $3,6,9,12$；计数参数 $n$ 虽然传给 $h$，却被投影忽略。这里的有限证书清楚区分了“使用已构造函数”与“假设待定义的乘法可用”。

再令 $q(0)=1$、$q(n+1)=\mathrm{mul}(n+1,q(n))$，就得到阶乘。常量 $1$ 是 $S(Z_0())$，更新也是后继、投影和乘法的复合，所以这一步无需增加基本运算。

Ackermann–Péter 函数：总性仍不够 ​

定义二元函数

它对所有自然数输入终止。证明先对 $m$ 归纳：第零行显然全定义；假设第 $m$ 行对所有输入都已全定义，则第 $m+1$ 行在零处可算，对 $n$ 再归纳，每个新值先调用已算出的同一行前值，再调用全定义的上一行。嵌套调用虽然复杂，却没有留下无限下降之外的循环依赖。

逐行展开可得 $A(1,n)=n+2$、$A(2,n)=2n+3$，以及

第三行在 $n=0,1,2,3,4$ 上依次为 $5,13,29,61,125$：初值是 $A(2,1)=5$，之后每步把前值 $z$ 更新为 $2z+3$。对每个固定的 $m$，一元切片 $n\mapsto A(m,n)$ 都是原始递归的，因为下一行只是对已固定的上一行做原始递归。但允许 $m$ 本身作为输入的统一二元函数 $A$ 不是原始递归函数。

后一结论不能由“递推式不像定义模板”证明：同一个函数可能另有符合模板的写法。标准证明建立支配定理，按原始递归构造树归纳，说明每个原始递归函数都受到某个固定 Ackermann 层的适当增长界控制；沿对角线增加层号则最终超过每个这样的固定层界。若统一的 $A$ 也原始递归，其对角函数也会因复合而原始递归，便与该支配结论冲突。这里给出证明机制；各层的单调性及支配不等式仍是完整证明需要建立的内容。

有界搜索与无界搜索 ​

若谓词 $R(\mathbf{x},y)$ 的 $0/1$ 特征函数是原始递归的，界 $b(\mathbf{x})$ 也是原始递归的，则在 $0\le y\le b(\mathbf{x})$ 中寻找最小见证、找不到时返回 $b(\mathbf{x})+1$，仍是原始递归函数。可以逐候选维护“尚未找到”或“第一个见证”的状态；有限次数的更新与原始递归条件分支实现这个搜索。返回值约定让没有见证时也有确定结果。

去掉上界，改成“不断找直到成功”，就失去了这一保证：例如依次找满足 $y^2=2$ 的自然数永远不会停机。这是部分可计算函数公理库部分可计算函数Partial computable function允许机器在函数未定义的输入上不停机的部分函数。中无界最小化可能发散的原因。但即使另行证明某个无界搜索总会成功，也只能先得到全可计算性，不能自动提升为原始递归性。

总性和可计算性如何随构造传递 ​

原始递归函数都是可计算全函数公理库可计算函数Computable function · Recursive function有图灵机对每个合法输入都停机并输出其值的全函数。。证明对有限构造树做结构归纳：基本函数有直接终止的算法；复合只串接有限个已知会终止的计算；递归节点则运行下面的过程：

z := g(x)
for i = 0, ..., n-1:
    z := h(x, i, z)
return z

当 $n=0$ 时循环为空。对子程序的总性使用结构归纳假设，对循环次数使用数学归纳法公理库数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。：执行 $i$ 轮后，$z=f(\mathbf{x},i)$；下一轮由递归等式保持这个性质。到第 $n$ 轮既得到正确值，也完成有限计算。这同时说明关系“原始递归函数是全可计算函数的特例”，而 Ackermann–Péter 例子说明包含是严格的。

原始递归常用于编码有限语法、有限计算轨迹与带显式界的检查过程；它提供一种能机械组合的终止保证。更一般的自然数递归可以让状态是函数等高阶对象，或者把任意已给的更新映射代入递归定理。那不是本页仅在自然数有限元函数上、由基本函数有限生成的一阶闭包，不能因为都叫“自然数递归”就断言表达能力相同。

自测。 构造截断前驱 $p(0)=0$、$p(n+1)=n$，并判断能否据此构造截断减法 $d(x,n)=max(x-n,0)$。检查标准：$p=R(Z_0,P_1^2)$；随后用 $d(x,0)=x$、$d(x,n+1)=p(d(x,n))$，初值为投影，更新为 $p\circ P_3^3$。注意自然数上的“减一”在零处必须给出值，不能默默改成部分函数。

语法的哥德尔编码公理库语法的哥德尔编码Gödel coding of syntax · Arithmetization of syntax把有限项、公式和自由变量替换编码为自然数运算，为算术内部表达语法提供接口。给出一个具体应用：配对解码是有界搜索，闭数码生成是原始递归，处理量词遮蔽的替换则可由较小子树的结果表逐步重建。有界搜索与结果表更新给出了所需的原始递归构造。算术可表示性公理库算术可表示性Arithmetical representability用算术公式逐个输入证明函数值及其唯一性，连接外部计算和理论内推导。随后将这些外部数函数接到 PA 中的公式及证明。