The primitive recursive functions form the smallest class of
functions that
- includes
- the zero function: \( z(x) = 0 \)
- the successor function: \( s(x) = x+1 \)
- the projection functions: \( p_i(x_1,\ldots,x_i,\ldots,x_m) = x_i \)
- is closed under
- composition: \( h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n) ) \)
- primitive recursion: \( h(x,0)=f(x);\, h(x,y+1)=g(x,y,h(x,y))\)
Examples:
- sum: \( x+0=x; \, x+(y+1) = 1+(x+y) \)
- product: \( x\times 0=0; \, x\times(y+1) = x+(x\times y) \)
- exponentiation: \( x^0=1; \, x^{y+1} = x\times x^y \)
- super-exponentiation: \( se(x,0)=1; \, se(x,y+1)= x^{se(x,y)} \)
where \( se(x,y) = x^{\ldots^x} (y \mbox{ terms})\)
- factorial: \( 0!=1; \, (y+1)! = (y+1) \times y! \)
- All primitive recursive functions are Turing computable.
- Not all computable functions are primitive recursive;
Ackermann's function is a
counter-example.