Editing Ackermann function (section)

=== Not primitive recursive ===

The Ackermann function grows faster than any [[primitive recursive function]] and therefore is not itself primitive recursive. Proof sketch: primitive recursive function defined using up to k recursions must grow slower than <math>f_{k+1}(n)</math>, the (k+1)-th function in the fast-growing hierarchy, but the Ackermann function grows at least as fast as <math>f_\omega(n)</math>.

Specifically, one shows that, for every primitive recursive function <math>f(x_1,\ldots,x_n)</math>, there exists a non-negative integer <math>t</math>, such that for all non-negative integers <math>x_1,\ldots,x_n</math>,<math display="block">f(x_1,\ldots,x_n)<A(t,\max_i x_i).</math>Once this is established, it follows that <math>A</math> itself is not primitive recursive, since otherwise putting <math>x_1=x_2=t</math> would lead to the contradiction <math>A(t,t)<A(t,t).</math>

The proof proceeds as follows: define the class <math>\mathcal{A}</math> of all functions that grow slower than the Ackermann function

<math display="block">\mathcal{A}=\left\{ f\,\bigg|\,\exists t\ \forall x_1\cdots \forall x_n:\ f(x_1,\ldots,x_n)<A(t, \max_i x_i) \right\} </math>

and show that <math>\mathcal{A}</math> contains all primitive recursive functions. The latter is achieved by showing that <math>\mathcal{A}</math> contains the constant functions, the successor function, the projection functions and that it is closed under the operations of function composition and primitive recursion.