Difference between revisions of "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].

How to Cite This Entry:
Ackermann function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ackermann_function&oldid=18747
This article was adapted from an original article by Jerrold W. GrossmanR. Suzanne Zeitman (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article