Ackermann function

The Ackermann function (also known as Ackermann-Peter function), an important example in the theory of computation, is a recursive function which takes two natural numbers as arguments and returns a natural number as its value.

Table of contents 1 Definition 2 Recursive, but not primitive recursive 3 Explicit description 4 History 5 Inverse

Definition

The Ackermann function is defined by recursion 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) already has 19,729 digits. This extreme growth can be exploited to show that the computable function f(n) = A(n, n) grows faster than any primitive recursive function and is therefore 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, Wilhelm 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.

Inverse

Since the function f(n) = A(n,n) considered above grows really fast, its inverse grows really slowly. Interestingly, this inverse occurs in the run-time analysis of some algorithms.