原始递归函数

相关概念介绍(合成 原始递归)

原始递归函数 定义

常用原始递归函数

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

相关概念介绍

合成

设 f 是 k 元部分函数，g1、g2、...、gk是 k 个n 元部分函数，令

h(x1,...,xn)=f(g1(x1,...,xn),...,gk(x1,...,xn))

称函数h是由 f 和g1,...,gk 合成得到的。

原始递归

1. 设 g 是2元全函数，k 是一个常数，函数 h 由下述等式给出

h(0)=k,

h(t+1)=g(t,h(t))

称 h 是由 g 经过原始递归运算得到的。

2. 设 f 和 g 分别是 n 元和 n+2 元全函数， n+1 元函数 h 由下述等式给出

h(x1,...,xn,0)=f(x1,...,xn),

h(x1,...,xn,t+1)=g(t,h(x1,...,xn),x1,...,xn)

称 h 是由 f 和 g 经过原始递归运算得到的。

原始递归函数 定义

初始函数

包括：

后继函数： s(x)=x+1

零函数： n(x)=0

投影函数： Ui n (x1,...,xn)=xi, 1≦i≦n

定义：

由 初始函数 经过 有限次 合成和原始递归得到的函数称作 原始递归函数

常用原始递归函数

1. 常数K

2. x

3. x+y

4. xy

5. x!

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

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

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