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.
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) is already about 2.0035299*1019728. 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.
Table of Values
| m\n | 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | |
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 2 | 3 | 5 | 7 | 9 | 11 | |
| 3 | 5 | 13 | 29> | 61 | 125 | |
| 4 | 13 | 65533 | 265536-3 | A(3,A(4,265536-3 | A(3,A(4,3) | |
| 5 | 65533 | A(4,65533) | A(3,A(5,1)) | A(3,A(5,2) | A(4,A(5,3)) | |
| 6 | A(4,A(5,0)) |
It might be noted that for each item, we need to compute its predecessor in the row just to find the position (index in programming terms) at which to look up the item in the previous row. A(4,2) is greater than the number of particles in the universe raised to the power 200. A(5,2) is the item at index A(4,2) in A(4,2)'s own row, and cannot be written as a decimal expansion in the physical universe. It is also amusing to note that beyond row 4, the values can only be written by resorting to the definition of the Ackermann function - writing them as decimal expansions, or as references to rows with lower m, would not be possible.
Intuitive explanation
Intuitively, the first row of the Ackermann function (or more accurately the values A(0,n)) is simply a list of all positive integers, and the only mathematical operation is the addition of 1 to n for the values in that row. All subsequent rows simply give directions to look up a value in that row. In the case of the m=1 row, the directions simplify to give the value A(0,n+1) from the m=0 row, but the simplification is quite complex - for example,
A(1, 2) =A(0, A(1,1)) =A(0, A(0, A(1,0))) =A(0, A(0, A(0,1))) =A(0, A(0, 2)) =A(0, 3) =4
Now let us attempt a more complex case - specifically A(4,3), the first value which cannot be recorded as a decimal expansion in the physical universe.
A(4, 3) =A(3, A(4, 2)) =A(3, A(3, A(4, 1))) =A(3, A(3, A(3, A(4, 0)))) =A(3, A(3, A(3, A(3, 1)))) =A(3, A(3, A(3, A(2, A(3, 0))))) =A(3, A(3, A(3, A(2, A(2, 1))))) =A(3, A(3, A(3, A(2, A(1, A(2, 0)))))) =A(3, A(3, A(3, A(2, A(1, A(1, 1)))))) =A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0))))))) =A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1))))))) =A(3, A(3, A(3, A(2, A(1, A(0, 2)))))) =A(3, A(3, A(3, A(2, A(1, 3))))) =A(3, A(3, A(3, A(2, A(0, A(1, 2)))))) =A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1))))))) =A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0)))))))) =A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1)))))))) =A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2)))))) =A(3, A(3, A(3, A(2, A(0, A(0, 3))))) =A(3, A(3, A(3, A(2, A(0, 4))))) =A(3, A(3, A(3, A(2, 5))))
This is about the simplest the expansion will be for some time, and it is now obvious why values of the function like those in the table above are very seldom calculated directly. It is also interesting to note how many steps are needed to simplify even the simplest-looking Ackermann expressions - each line in the example above is a single application of the appropriate one of the 3 parts of the definition of the Ackermann function. At this point, if we skip many logical steps, we would be evaluating A(2, 5) to 13, and then trying to evaluate A(3, 13), which is 8179. Then the next call to A(3, 8179) returns a number which is equal to the number of atoms in the universe raised to a power of several dozen. This number n is then input into the computation of the final A(3, n) call, expanding that call to an expression A(2, A(2, A(2...))) which cannot be written explicitely in the physical universe.
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 nonrecursively using Conway's arrow:
or the hyper operators:
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 very rapidly, its inverse grows very slowly; this inverse occurs in the run-time analysis of certain algorithms.