Editing Ackermann function (section)

==History==
In the late 1920s, the mathematicians [[Gabriel Sudan]] and [[Wilhelm Ackermann]], students of [[David Hilbert]], were studying the foundations of computation. Both Sudan and Ackermann are credited{{sfn|Calude|Marcus|Tevy|1979}} with discovering [[total function|total]] [[computable function]]s (termed simply "recursive" in some references) that are not [[primitive recursive function|primitive recursive]]. Sudan published the lesser-known [[Sudan function]], then shortly afterwards and independently, in 1928, Ackermann published his function <math>\varphi</math> (from Greek, the letter ''[[phi]]''). Ackermann's three-argument function, <math>\varphi(m, n, p)</math>, is defined such that for <math>p=0,1,2</math>, it reproduces the basic operations of [[addition]], [[multiplication]], and [[exponentiation]] as

<math display="block">\begin{align}
\varphi(m, n, 0) &= m+n \\
\varphi(m, n, 1) &= m\times n \\
\varphi(m, n, 2) &= m^n 
\end{align}</math>

and for <math>p > 2</math> it extends these basic operations in a way that can be compared to the [[hyperoperation]]s:

<math display="block">\begin{align}
\varphi(m, n, 3) &= m[4](n+1) \\
\varphi(m, n, p) &\gtrapprox m[p+1](n+1) && \text{for } p > 3
\end{align}</math>

(Aside from its historic role as a total-computable-but-not-primitive-recursive function, Ackermann's original function is seen to extend the basic arithmetic operations beyond exponentiation, although not as seamlessly as do variants of Ackermann's function that are specifically designed for that purpose—such as [[Reuben Goodstein|Goodstein's]] [[hyperoperation]] sequence.)

In ''On the Infinite'',{{sfn|Hilbert|1926|p=185}} David Hilbert hypothesized that the Ackermann function was not primitive recursive, but it was Ackermann, Hilbert's personal secretary and former student, who actually proved the hypothesis in his paper ''On Hilbert's Construction of the Real Numbers''.{{sfn|Ackermann|1928}}{{sfn|van Heijenoort|1977}}

Rózsa Péter{{sfn|Péter|1935}} and Raphael Robinson{{sfn|Robinson|1948}} later developed a two-variable version of the Ackermann function that became preferred by almost all authors.

The generalized [[Hyperoperation|hyperoperation sequence]], e.g. <math>G(m, a, b) = a[m]b</math>, is a version of the Ackermann function as well.{{sfn|Ritchie|1965|p=1028}}

In 1963 [[Robert Creighton Buck|R.C. Buck]] based an intuitive two-variable <ref group="n" name="letop3">with parameter order reversed</ref> variant <math>\operatorname{F}</math> on the [[Hyperoperation|hyperoperation sequence]]:{{sfn|Buck|1963}}{{sfn|Meeussen|Zantema|1992|p=6}}

<math display="block">\operatorname{F}(m,n) = 2[m]n.</math>

Compared to most other versions, Buck's function has no unessential offsets:

<math display="block">\begin{align}
\operatorname{F}(0,n) &= 2[0]n = n + 1 \\
\operatorname{F}(1,n) &= 2[1]n = 2 + n \\
\operatorname{F}(2,n) &= 2[2]n = 2 \times n \\
\operatorname{F}(3,n) &= 2[3]n = 2^n \\
\operatorname{F}(4,n) &= 2[4]n = 2^{2^{2^{{}^{.^{.^{{}_.2}}}}}} \\
 &\quad\vdots
\end{align}</math>

Many other versions of Ackermann function have been investigated.{{sfn|Munafo|1999a}}{{sfn|Ritchie|1965}}