原始递归函数

原始递归函数是可计算性理论中的一类自然数函数，英文为primitive recursive function。定义首先给出零函数、把n送到n＋1的后继函数，以及从多个输入中选取某一项的投影函数，再允许有限次使用复合和原始递归。这里的“原始”限定的是生成规则，不表示功能原始或计算速度快。

复合把若干已知函数的输出交给另一个已知函数。原始递归则规定初值f(0,x)＝g(x)，以及后继步骤f(n＋1,x)＝h(n,f(n,x),x)，其中g和h已构造完成，x可代表一组参数。计算第n步只依赖此前一步的结果和已有函数，而不是无限制地寻找某个尚不知是否存在的结果。

参考：[1] [2]

加法可以定义为add(0,y)＝y，add(n＋1,y)＝S(add(n,y))。计算add(3,2)时，从2出发连续应用三次后继函数，依次得到3、4、5。它展示了递归参数控制步骤数，而另一个参数提供初始值的方式。

乘法再以加法为工具：mul(0,y)＝0，mul(n＋1,y)＝add(mul(n,y),y)。例如mul(3,2)沿着0、2、4、6计算。指数等运算还可继续逐层建立。某个程序写成循环还是函数自调用，不决定其所计算的函数属于哪一类；重要的是有没有等价的原始递归构造。

参考：[1]

基本函数在所有自然数输入上都有定义，复合保持这一性质；原始递归对给定n只进行有限层后继步骤。因此每个原始递归函数都是全函数，也都是可计算函数。不过，这个结论没有给出实际可接受的时间界：嵌套构造能产生极快增长的函数。

反方向不成立。可以有效列出全部原始递归函数的描述，并对每个给定描述与输入计算结果。利用这种求值过程构造对角函数，让它在第i个输入上比列表中第i个函数大1，就得到一个全可计算但不在该列表中的函数。这个论证区分了“能够逐一求值”和“存在覆盖全部成员的同类通用函数”。

参考：[2]

阿克曼函数给出更具体的边界例子。一个常用版本令A(0,y)＝y＋1，A(x＋1,0)＝A(x,1)，A(x＋1,y＋1)＝A(x,A(x＋1,y))。对任意固定的第一参数x，所得单变量函数属于原始递归类；但把两个参数都作为输入的完整函数虽然总能计算，却不是原始递归函数。

因此不能仅凭递归式的外观判定类别，也不能把“非原始递归”读成“不可计算”。若在基本构造上允许无界最小化，即从0开始搜索使条件成立的最小数，就能进入更广的部分递归函数框架；搜索条件未必能满足，计算也可能不终止。这正是与原始递归所保障的全定义性不同的地方。

参考：[2] [3]