| • Science | • People | • Locations | • Timeline |
| Contents | ||
In 1928, Wilhelm Ackermann, a mathematician studying the foundations of computation, originally considered a function A(m, n, p) of three variables, the p-fold iterated exponentiation of m with n, or m → n → p as expressed using the Conway chained arrow. When p=1, this is simply mn, m multiplied by itself n times. When p=2, it is a tower of exponents with n levels, or m raised to its own power n times. We can continue to generalize this indefinitely as p becomes larger.
Ackermann proved that A is a recursive function, a function a computer with infinite memory can calculate, but it is not a primitive recursive function, a class of functions including almost all familiar functions such as addition and factorial.
A similar function of only two variables was later defined by Rozsa Peter and Raphael Robinson; its definition is given below. Note that the numbers, except in the first few rows, are three less than powers of two. For the exact relation between the two functions, see below.
The Ackermann function is defined recursively for non-negative integers m and n as follows:
The Ackermann function can be calculated by a simple function based directly on the definition:
The following is wikicode , a proposed pseudocode for use in many articles:
function ack(m, n) if m = 0 return n+1 else if m > 0 and n = 0 return ack(m-1, 1) else return ack(m-1, ack(m, n-1))The same function can be written partially iteratively as:
function ack(m, n) while m ≠ 0 if n = 0 n := 1 else n := ack(m, n-1) m := m - 1 return n+1It may be surprising that these functions always return a value. This is because at each step either n decreases, or n increases and m decreases. Each time that n reaches zero, m must decrease, so m must eventually reach zero as well. Note, however, that when m decreases there is no upper bound on how much n can increase — and it will often increase greatly.
The Ackermann function can also be expressed nonrecursively using Conway chained arrow:
hence
(n=1 and n=2 would correspond with A(m,-2)=-1 and A(m,-1)=1, which could logically be added).
or the hyper operators:
For small values of m like 1, 2, or 3, the Ackermann function grows relatively slowly with respect to n (at most exponentially). For m ≥ 4, however, it grows much more quickly; even A(4, 2) is about 2×1019728, and the decimal expansion of A(4, 3) cannot be recorded in the physical universe. If we define the function f (n) = A(n, n), which increases both m and n at the same time, we have a function of one variable that dwarfs every primitive recursive function, including very fast-growing functions such as the exponential function, the factorial function, multi- and superfactorial functions, and even functions defined using Knuth's up-arrow notation (except when the indexed up-arrow is used).
This extreme growth can be exploited to show that f, which is obviously computable on a machine with infinite memory such as a Turing machine and so is a recursive function, grows faster than any primitive recursive function and is therefore not primitive recursive. In combination with the Ackermann function's applications in analysis of algorithms, discussed later, this debunks the theory that all useful or simple functions are primitive recursive functions.
One surprising aspect of the Ackermann function is that the only arithmetic operations it ever uses are addition and subtraction of 1. Its properties come solely from the power of unlimited recursion. This also implies that its running time is at least proportional to its output, and so is also extremely huge. In actuality, for most cases the running time is far larger than the output; see below.