home > factoids > primitive recursive functions

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 pi(x1,...,xi,...,xm)=xi
  2. is closed under
    • composition h(x1,...,xn)=f(g1(x1,...,xn),...,gm(x1,...,xn))
    • 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*0=x; x*(y+1)=x+(x*y)
  • exponentiation
x^0^=1; x^(y+1)^=x*(x^y^)
  • super-exponentiation, where
    se(x,y)=x^(...^x^)^ (y terms)
se(x,0)=1; se(x,(y+1))=x^se(x,y)^
  • factorial
0!=1; (y+1)!=(y+1)*y!