# Primitive recursive functions

The primitive recursive functions form the smallest class of functions that

1. 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$
2. 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.