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) 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.