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 [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 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.) He defined a function $\varphi$ 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); one needs to permit an additional operation such as minimization.

Ackermann's original function is defined as follows:

\begin{equation*} \varphi ( a , b , 0 ) = \alpha + b, \end{equation*}

\begin{equation*} \varphi ( a , 0,1 ) = 0 , \varphi ( a , 0,2 ) = 1, \end{equation*}

\begin{equation*} \varphi ( a , 0 , i ) = a \text { for } i \geq 3 , \varphi ( a , b , i ) = \varphi ( a , \varphi ( a , b - 1 , i ) , i - 1 ) \text { for } i \geq 1 , b \geq 1. \end{equation*}

The first case of the definition states that $\varphi$ is just addition of its first two arguments when the third argument is $0$. Similarly, it can easily be proved that $\varphi ( a , b , 1 ) = a. b$ and $\varphi ( a , b , 2 ) = a ^ { b }$. Furthermore $\varphi ( a , b , 3 )$ consists of an exponential tower of $a$'s, with $b + 1$ $a$'s in the tower. For example, $\varphi ( 3,3,3 ) = 3 ^ { 3 ^ { 3 ^ { 3 } } }$, a number with more than three trillion decimal digits.

Many authors prefer the following $2$-variable Ackermann function, whose definition was given some years later by R. Robinson [a7], following a version given by R. Péter [a5]:

\begin{equation*} A ( 0 , n ) = n + 1, \end{equation*}

\begin{equation*} A ( i , 0 ) = A ( i - 1,1 ) \text { for } i \geq 1 , A ( i , n ) = A ( i - 1 , A ( i , n - 1 ) ) \text { for } i \geq 1 , n \geq 1. \end{equation*}

Here it is easy to show that $A ( 1 , n ) = n + 2$, $A ( 2 , n ) = 2 n + 3$, $A ( 3 , n ) = 2 ^ { n + 3 } - 3$, and $A ( 4 , n )$ is $3$ less than an exponential tower of $n + 3$ $2$'s.

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

\begin{equation*} T ( 0 , n ) = 2 n, \end{equation*}

\begin{equation*} T ( i , 0 ) = 0 \text { for } i \geq 1 , T ( i , 1 ) = 2 \text { for } i \geq 1, \end{equation*}

\begin{equation*} T ( i , n ) = T ( i - 1 , T ( i , n - 1 ) ) \text { for } i \geq 1 , n \geq 2. \end{equation*}

This time $T ( i , 2 ) = 4$ for all $i$, and for all $n \geq 1$ one finds that $T ( 1 , n ) = 2 ^ { n }$ and $T ( 2 , n )$ is an exponential tower of $n$ $2$'s. Another slight modification of Ackermann's function can be used to define the Grzegorczyk hierarchy of primitive recursive functions [a4], [a6].

Tarjan also studied the extremely slowly growing "inverse" of his version of Ackermann's function, $\alpha ( m , n ) = \operatorname { min } \{ r \geq 1 : T ( r , 4 \lceil m / n ] ) > \operatorname { log } _ { 2 } n \}$, which often arises in computer science (as it did in [a9]) as part of an analysis of algorithmic complexity, cf. also Complexity theory. (Tarjan's result that the well-known path compression algorithm for set unions is almost linear comes from the fact that $\alpha ( m , n ) \leq 3$ for all $m$ and $n$ 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 [a2] and [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 [a8].

References

[a1]	W. Ackermann, "Zum Hilbertschen Aufbau der reellen Zahlen" Math. Ann. , 99 (1928) pp. 118–133
[a2]	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
[a3]	J.W. Grossman, R.S. Zeitman, "An inherently iterative computation of Ackermann's function" Theoret. Comput. Sci. , 57 : 2–3 (1988) pp. 327–330
[a4]	A. Grzegorczyk, "Some classes of recursive functions" Rozprawy Mat. , 4 (1953) pp. 1–45
[a5]	R. Péter, "Konstruktion nichtrekursiver Funktionen" Math. Ann. , 111 (1935) pp. 42–60
[a6]	R.W. Ritchie, "Classes of recursive functions based on Ackermann's function" Pacific J. Math. , 15 (1965) pp. 1027–1044
[a7]	R.M. Robinson, "Recursion and double recursion" Bull. Amer. Math. Soc. , 54 (1948) pp. 987–993
[a8]	G. Sudan, "Sur le nombre transfini $\omega ^ { \omega }$" Bull. Math. Soc. Roumaine Sci. , 30 (1927) pp. 11–30
[a9]	R.E. Tarjan, "Efficiency of a good but not linear set union algorithm" J. Assoc. Comput. Mach. , 22 (1975) pp. 215–225