View source for Ackermann function

A multi-variable function from the natural numbers to the natural numbers with a very fast rate of growth.

In 1928, W. Ackermann [[#References|[a1]]], in connection with some problems that his PhD supervisor, D. Hilbert, was investigating, gave an example of a recursive (i.e., computable) function that is not primitive recursive. (A [[Primitive recursive function|primitive recursive function]] is one that can be obtained from projections, the zero function, and the successor function using composition and simple inductive definitions. Cf. also [[Recursive function|Recursive function]].) He defined a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201101.png" /> of three variables using a double induction (see below). It subsumes addition, multiplication, exponentiation, and all higher-order analogues of these operations. Because of this it grows too rapidly to be primitive recursive.

Over the years, several authors have given other examples of such functions, which are usually also called  "the"  Ackermann function. Some of these will be described below. These functions show that the operations permitted in primitive recursion fail to capture completely the notion of  "computability"  (cf. also [[Computable function|Computable function]]); one needs to permit an additional operation such as minimization.

Ackermann's original function is defined as follows:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201102.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201103.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201104.png" /></td> </tr></table>

The first case of the definition states that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201105.png" /> is just addition of its first two arguments when the third argument is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201106.png" />. Similarly, it can easily be proved that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201107.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201108.png" />. Furthermore <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a1201109.png" /> consists of an exponential tower of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011010.png" />'s, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011011.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011012.png" />'s in the tower. For example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011013.png" />, a number with more than three trillion decimal digits.

Many authors prefer the following <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011015.png" />-variable Ackermann function, whose definition was given some years later by R. Robinson [[#References|[a7]]], following a version given by R. Péter [[#References|[a5]]]:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011016.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011017.png" /></td> </tr></table>

Here it is easy to show that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011020.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011021.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011022.png" /> less than an exponential tower of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011023.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011024.png" />'s.

A variant described by R. Tarjan [[#References|[a9]]] is as follows:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011025.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011026.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011027.png" /></td> </tr></table>

This time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011028.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011029.png" />, and for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011030.png" /> one finds that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011032.png" /> is an exponential tower of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011033.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011034.png" />'s. Another slight modification of Ackermann's function can be used to define the Grzegorczyk hierarchy of primitive recursive functions [[#References|[a4]]], [[#References|[a6]]].

Tarjan also studied the extremely slowly growing  "inverse"  of his version of Ackermann's function, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011035.png" />, which often arises in computer science (as it did in [[#References|[a9]]]) as part of an analysis of algorithmic complexity, cf. also [[Complexity theory|Complexity theory]]. (Tarjan's result that the well-known path compression algorithm for set unions is almost linear comes from the fact that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011036.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011038.png" /> that could ever arise in practice.) The Ackermann function has also been used to measure performance of implementations of recursive subroutine calls in programming languages because its definition is so highly recursive in form.

Comments on the history of the Ackermann function can be found in [[#References|[a2]]] and [[#References|[a3]]]. In particular, C. Calude and others have pointed out that credit for producing the first example of a recursive function that is not primitive recursive belongs jointly to Ackermann and G. Sudan [[#References|[a8]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W. Ackermann,   "Zum Hilbertschen Aufbau der reellen Zahlen"  ''Math. Ann.'' , '''99'''  (1928)  pp. 118–133</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  C. Calude,   S. Marcus,   I. Ţevy,   "The first example of a recursive function which is not primitive recursive"  ''Historia Math.'' , '''6''' :  4  (1979)  pp. 380–384</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.W. Grossman,   R.S. Zeitman,   "An inherently iterative computation of Ackermann's function"  ''Theoret. Comput. Sci.'' , '''57''' :  2–3  (1988)  pp. 327–330</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Grzegorczyk,   "Some classes of recursive functions"  ''Rozprawy Mat.'' , '''4'''  (1953)  pp. 1–45</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R. Péter,   "Konstruktion nichtrekursiver Funktionen"  ''Math. Ann.'' , '''111'''  (1935)  pp. 42–60</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R.W. Ritchie,   "Classes of recursive functions based on Ackermann's function"  ''Pacific J. Math.'' , '''15'''  (1965)  pp. 1027–1044</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R.M. Robinson,   "Recursion and double recursion"  ''Bull. Amer. Math. Soc.'' , '''54'''  (1948)  pp. 987–993</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  G. Sudan,   "Sur le nombre transfini <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a120/a120110/a12011039.png" />"  ''Bull. Math. Soc. Roumaine Sci.'' , '''30'''  (1927)  pp. 11–30</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  R.E. Tarjan,   "Efficiency of a good but not linear set union algorithm"  ''J. Assoc. Comput. Mach.'' , '''22'''  (1975)  pp. 215–225</TD></TR></table>