Editing Primitive recursive function (section)

== Definition ==

A primitive recursive function takes a fixed number of arguments, each a [[natural number]] (nonnegative integer: {0, 1, 2, ...}), and returns a natural number. If it takes ''n'' arguments it is called ''n''-[[arity|ary]].

The basic primitive recursive functions are given by these [[axiom]]s:

{{ordered list|start=1
|1=''Constant functions <math>C_n^k</math>'': For each natural number <math>n</math> and every <math>k</math>, the ''k''-ary constant function, defined by <math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  n</math>, is primitive recursive.

| 2=''Successor function'': The 1-ary successor function ''S'', which returns the successor of its argument (see [[Peano postulates]]), that is, <math>S(x) \ \stackrel{\mathrm{def}}{=}\  x + 1</math>, is primitive recursive.

| 3=''Projection functions'' <math>P_i^k</math>: For all natural numbers <math>i, k</math> such that <math>1\le i\le k</math>, the ''k''-ary function defined by <math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  x_i</math> is primitive recursive.
}}

More complex primitive recursive functions can be obtained by applying the [[operation (mathematics)|operation]]s given by these axioms:

{{ordered list|start=4
| 4=''Composition operator'' <math>\circ\,</math> (also called the ''substitution operator''): Given an ''m''-ary function <math>h(x_1,\ldots,x_m)\,</math> and ''m'' ''k''-ary functions <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>: <math display="block">h \circ (g_1, \ldots, g_m) \ \stackrel{\mathrm{def}}{=}\  f, \quad\text{where}\quad f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)).</math>  For <math>m=1</math>, the ordinary [[function composition]] <math>h \circ g_1</math> is obtained.

| 5=''Primitive recursion operator'' <math>\rho</math>: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and the (''k''&nbsp;+&nbsp;2)-ary function <math>h(y,z,x_1,\ldots,x_k)\,</math>:<math display="block">\begin{align} 
             \rho(g, h) &\ \stackrel{\mathrm{def}}{=}\  f, \quad\text{where the }(k+1)\text{-ary function } f \text{ is defined by}\\
    f(0,x_1,\ldots,x_k) &= g(x_1,\ldots,x_k) \\
  f(S(y),x_1,\ldots,x_k) &= h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k).\end{align}</math>
''Interpretation:''
The function <math>f</math> acts as a [[for loop|for-loop]] from <math>0</math> up to the value of its first argument. The rest of the arguments for <math>f</math>, denoted here with <math>x_1,\ldots,x_k</math>, are a set of initial conditions for the for-loop which may be used by it during calculations but which are immutable by it. The functions <math>g</math> and <math>h</math> on the right-hand side of the equations that define <math>f</math> represent the body of the loop, which performs calculations. The function <math>g</math> is used only once to perform initial calculations. Calculations for subsequent steps of the loop are performed by <math>h</math>. The first parameter of <math>h</math> is fed the "current" value of the for-loop's index. The second parameter of <math>h</math> is fed the result of the for-loop's previous calculations, from previous steps. The rest of the parameters for <math>h</math> are those immutable initial conditions for the for-loop mentioned earlier. They may be used by <math>h</math> to perform calculations but they will not themselves be altered by <math>h</math>.
}}

The '''primitive recursive functions''' are the basic functions and those obtained from the basic functions by applying these operations a finite number of times.