原始递归函数

来自计算思维百科
跳转至: 导航搜索

自变量值和函数值都是自然数的函数,称为数论函数。原始递归函数是数论函数的一部分。首先规定少量直观可计算的函数为原始递归函数,它们是:函数值恒等于0的零函数C0,函数值等于自变量值加1的后继函数S,函数值等于第i个自变量值的n元投影函数Pi(n)。然后规定,原始递归函数的合成仍是原始递归函数,可以由已知原始递归函数简单递归地计算出函数值的函数仍是原始递归函数。例如,和函数f(x','y)=x+y可由原始递归函数Pi(1)S递归地计算出函数值。

f (x,0)=P1(1)(x)

f(x,S(y))=S(f(x,y))

比如,f (4, 2) 可这样计算,首先算出f (4,0)=P1(1)(4)=4,然后计算f (4,1)=S(f(4,0))=S(4)=5,最后f (4,2)=S (f(4,1))=S (5)=6。因此,和函数是原始递归函数。显然,一切原始递归函数都是直观可计算的,但并非一切直观可计算的函数都是原始递归函数。