Ackermann function

The Ackermann function, an important example in the theory of computation, is a recursively defined function which takes two natural numbers as arguments and returns a natural number as value.

Definition

The definition is as follows:

A(0, n) = n + 1    for n ≥ 0

A(m, 0) = A(m - 1, 1)    for m ≥ 1

A(m, n) = A(m - 1, A(m, n - 1))    for m, n ≥ 1

Recursive, but not primitive recursive

The Ackermann function grows extremely fast; A(4,2) has already 19,729 digits. This extreme growth can be exploited to show that the computable function f(n) = A(n, n) is not primitive recursive.

Explicit description

Intuitively, the Ackermann function defines generalizations of multiplication by two (iterated additions) and exponentiation with base 2 (iterated multiplications) to iterated exponentiation, iteration of this operation and so on. It can be most concisely expressed using [Knuth's up-arrow notation]?:

A(1, n) = 2 + (n + 3) - 3

A(2, n) = 2 * (n + 3) - 3

A(3, n) = 2 ^ (n + 3) - 3

A(4, n) = 2 ^ (2 ^ (2 ^ (.... ^2))) - 3     (n + 3 twos)

            = 2^^(n + 3) - 3

A(5, n) = 2^^^(n + 3) - 3 etc.

History

In 1928, Ackermann? considered a function A(m, n, p) of three variables, the p-fold iterated exponentiation of m with n, and proved that it is a recursive function which is not primitive recursive. This definition was later simplified by Rosza Peter and Raphael Robinson to the two-variable definition given above.