可计算性理论 V.pdf

V ．原始递归函数和部分递归函数 5.1 原始递归函数 定义 5.1 包含基本函数并且在代入和原始递归运算下封闭的最小类称为原始递归函数类 （Primitive Recursive ）。其中函数称为原始递归函数。特征函数是原始递归函数的谓词称为 原始递归谓词。 定义5.2 有穷函数序列f 1 ,f 2 ,,f k 满足下列条件：每一个f i (1i k) （1）或者是基本函数之一； （2 ）或者由该序列中它前面的一些函数经代入或原始递归得到， 并且f k f ，则称该序列为f 的一个原始递归描述，k 称为描述长度。 定理5.1 函数f 是原始递归的iff 存在f 的原始递归描述。 推论：函数f 是原始递归的ifff 能从基本函数出发经有穷次代入，原始递归而得到。 推论：原始递归函数类是可数的。 证明：每一个原始递归描述确定一个原始递归函数，所以，只要证明所有原始递归描述的数 目可数。基本函数的总数是可数的，长度为n 的原始递归描述是总数是可数的。考虑所有n 时，可得多个可数个原始递归描述，它也是可数的。故原始递归函数是可数的。 定理5.2 下列函数是原始递归的 （1）常函数c(x) c （2 ）和函数x y （3 ）积函数x y y （4 ）幂函数x 0 x 0  （5）先行元函数x 1   x 1 x 0  0 x y  （6 ）算术差x y   x y x y  0 x 0  （7 ）符号函数 sg (x)  1 x 0  1 x 0  （8）反符号函数sg (x)  0 x 0  （9 ）差绝对值 | x y | （10）阶乘 x! （11）min(x,y) （12）max(x,y) （13）（y 被x 除时）余数rm(x,y) （补： ） rm(0,y) y （14）商函数qt(x,y) (or: [y/x ]) （15）算术平方根[ x ] f(0) 0  证明：（1） f(x 1) s(x)  c(x) f(c) x 0 x  (2)  x (y 1) (x y ) 1  x 0 0  （3 ） x (y 1) (xy ) x   0