原始递归函数

·原始递归与合成
设f，g分别是n，n+2元全函数，h遵从如下定义：
\(h(x_1,...,x_n,0) = f(x_1,...,x_n) ;\)
\(h(x_1,...,x_n,t+1) = g(t,h(x_1,...,x_n,t),x_1,...,x_n)\).
则称h是由f，g原始递归运算得的。
h的定义说明，在原始递归运算中，原自变量、递归次数、上一次递归的结果都可以作为自变量使用。如果f，g都可计算，则h亦可计算。
合成：\(h = f(g_1,g_2,...,g_n)\).

·原始递归函数
由初始函数（后继、零、投影）经过有限次递归和合成得到的函数。
例：前驱函数\(p(x):\ p(0)=0,p(x+1)=x\)
\(x \frac{.}{}y : x \frac{.}{}0=x,x \frac{.}{}(y+1)=p( x\frac{.}{} y) \)
\(\alpha(x) = (x=0) = 1\frac{.}{}x\)

·原始递归谓词
如果一个谓词作为0，1的全函数是原始递归的，则称为原始递归谓词。
定理：若P，Q是原始递归谓词，则\(P \land Q,P \lor Q, \neg P \)亦然。

·迭代运算
若\(f(x_1,...,x_n,x_{n+1})\)是原始递归（可计算）函数，则\[g(x_1,...,x_n,y)=\sum_{t=0}^{y} f(x_1,...,x_n,t),\]\[ h(x_1,...,x_n,y)=\prod_{t=0}^{y} f(x_1,...,x_n,t)\]亦然.

有界量词
设\(P(x_1,...x_n,y)\)是原始递归（可计算）谓词，则\((\forall t)_{≤y}P(x_1,...x_n,t),(\exists t)_{≤y}P(x_1,...x_n,t)\)都是原始递归（可计算）谓词。

有界极小化与极小化
定义\(min_{t≤y}P(x_1,...,x_n,t)\)为使得谓词为真的最小t，可以由初始函数有限次合成、原始递归得到。故部分极小化也是原始递归（可计算）函数。
用原始递归也可以实现（无界）极小化。由初始函数经有限次合成、原始递归和极小化运算得到的函数称为部分递归函数，部分递归的全函数称作递归函数。如果一个谓词作为0，1的全函数是递归的，则称为递归谓词。

    所属分类：TCS     发表于2021-09-19