primitive recursive (thing)

The primitive recursive functions (from the nonnegative integers to themselves) are the functions of the following class C:

• C contains all projections P_i(x_1,...,x_n)=x_i
• C contains the constant (function) z=z()=0
• C contains the increment function I(x)=x+1
• if C contains the n-ary function f(y_1,...,y_n) and the k-ary functions g_1(x_1,...,x_k),...,g_n(x_1,...,x_k), then C also contains the composition function h(x_1,...,x_k) = f(g_1(x_1,...,x_k), ..., g_n(x_1,...,x_k)).
• (primitive recursion) if C contains the functions c(x_1,...,x_n), g_1(x_1,...,x_n),...,g_n(x_1,...,x_n) then C also contains the iterated function

  h(0,x_1,...,x_n) = c(x_1,...,x_n)
  h(m+1,x_1,...,x_n) = h(m, g_1(x_1,...,x_n), ..., g_n(x_1,...,x_n))

• C contains just these functions.

Implementation-wise, the above rules would of course be terribly inefficient; here we're just concerned with defining the class.

Less formally, C contains the exactly those functions a BASIC program can compute, if we constrain all GOTOs to be forwards, and allow just FOR loops.

Addition, multiplication, exponentiation, integer logarithm, and most other "simple" functions are primitive recursive. Ackermann's function is not.

Note that primitive recursive functions are defined for all arguments. Since we know Turing machines (and real computer programs) can enter infinite loops, it should be clear that primitive recursive functions are less powerful than computable functions.