Editing Ackermann function (section)

=== General remarks ===
*It may not be immediately obvious that the evaluation of <math>A(m, n)</math> always terminates. However, the recursion is bounded because in each recursive application either <math>m</math> decreases, or <math>m</math> remains the same and <math>n</math> decreases. Each time that <math>n</math> reaches zero, <math>m</math> decreases, so <math>m</math> eventually reaches zero as well. (Expressed more technically, in each case the pair <math>(m,n)</math> decreases in the [[lexicographic order]] on pairs, which is a [[well-order]]ing, just like the ordering of single non-negative integers; this means one cannot go down in the ordering infinitely many times in succession.) However, when <math>m</math> decreases there is no upper bound on how much <math>n</math> 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 [[exponential growth|exponentially]]). For <math>m\geq 4</math>, however, it grows much more quickly; even <math>A(4,2)</math> is about 2.00353{{e|19728}}, and the decimal expansion of <math>A(4, 3)</math> is very large by any typical measure, about 2.12004{{e|6.03123{{e|19727}}}}.
*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 <math>f(n)=A(n,n)</math> that increases both <math>m</math> and <math>n</math> 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 <math>f(n)</math> is roughly comparable to <math>f_{\omega}(n)</math> in the [[fast-growing hierarchy]]. This extreme growth can be exploited to show that <math>f</math> 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.