down in the ordering infinitely many times in succession.) However, when decreases there is no upper bound on how much can increase — and it will often increase greatly. For small values of m like 1, 2, or 3, the Ackermann function grows relatively slowly with respect to n (at most exponentially). For , however, it grows much more quickly; even is about 2, and the decimal expansion of is very large by any typical measure. An interesting aspect is that the only arithmetic operation it ever uses is addition of 1. Its fast growing power is based solely on nested recursion. This also implies that its running time is at least proportional to its output, and so is also extremely huge. In actuality, for most cases the running time is far larger than the output; see above. A single-argument version that increases both and at the same time dwarfs every primitive recursive function, including very fast-growing functions such as the exponential function, the factorial function, multi- and superfactorial functions, and even functions defined using Knuth's up-arrow notation (except when the indexed up-arrow is used). It can be seen that is roughly comparable to in the fast-growing hierarchy. This extreme growth can be exploited to show that which is obviously computable on a machine with infinite memory such as a Turing machine and so is a computable function, grows faster than any primitive recursive function and is therefore not primitive recursive. Not primitive recursive The Ackermann function grows faster than any primitive recursive function and therefore is not itself primitive recursive. The sketch of the proof is this: a primitive recursive function defined using up to k recursions must grow slower than , the (k+1)-th function in the fast-growing hierarchy, but the Ackermann function grows at least as fast as . Specifically, one shows that to every primitive recursive function there exists a non-negative integer such that for all non-negative integers , Once this is established, it follows that itself is not primitive recursive, since otherwise putting would lead to the contradiction The proof proceeds as follows: define the class of all functions that grow slower than the Ackermann function and show that contains all primitive recursive functions. The latter is achieved by showing that contains the constant functions, the successor function, the projection functions and that it is closed under the operations of function composition and primitive recursion. Inverse