Ackermann function

In mathematics and computer science, the Ackermann function (also known as Ackermann-Peter function) is an important example in the theory of computation. It 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 recursively for non-negative integers m and n as follows:

$A(m,n)=\left\{{\begin{matrix}n+1,\qquad \qquad \qquad \quad \,&&{\mbox{if }}m=0;\ \ \qquad \qquad \\A(m-1,1),\qquad \qquad \ \,&&{\mbox{if }}m>0{\mbox{ and }}n=0;\\A(m-1,A(m,n-1))\,&&{\mbox{otherwise.}}\,\qquad \qquad \end{matrix}}\right.$

The Ackermann function can be calculated by a simple function based directly on the definition:

 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+1

Recursive, but not primitive recursive

The Ackermann function grows extremely fast; A(4, 2) is about 2×10¹⁹⁷²⁸. 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

Values of A(m, n)

m\n	0	1	2	3	4	A(m, n) in general
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2$
2	3	5	7	9	11	$2n+3$
3	5	13	29	61	125	$8\times {2}^{n}-3$
4	13	65533	265536 − 3	A(3, 265536 − 3)	A(3, A(4, 3))	${{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}}-3{\mbox{ (n + 3 terms)}}$
5	65533	A(4, 65533)	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))
6	A(5, 1)	A(5, A(5, 1))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))

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(5, 1) in the m = 4 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. A(5, 0) is an exception, as is A(5, 1) = A(6, 0), which can at least have their index in row 4 expressed as a decimal expansion.

Despite the inconceivably large values occurring early in this table, some even larger numbers have been defined, such as Graham's number, which cannot be written with any small (or, indeed, recordable) number of Knuth arrows. Of course, it appears in rows 0 and 1, but at a very high index—and comparable numbers do not appear at low indices in low rows of the table.

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, 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 three 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, eventually expanding that call to an expression of the form A(2, A(2, A(2, ... A(2, 0) ...))) which cannot be written explicitly in the physical universe.

The truly amazing aspect of the Ackermann function is that the only actual computation (rather than recursive calling) occurring is the computation of A(0, n), which simply increments n and returns the result.

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:

$A(m,n)=2\rightarrow (n+3)\rightarrow (m-2)-3$

or the hyper operators:

$A(m,n)=\mathrm {hyper} (2,m,n+3)-3\;$

History

In 1928, Wilhelm Ackermann considered a function A(m, n, p) of three variables, the p-fold iterated exponentiation of m with n or m → n → p in Conway's notation. He proved that it is a recursive function which is not primitive recursive. This definition was later simplified by Rozsa 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 complexity of some algorithms. In this and other contexts, the Ackermann function is often slightly redefined to a function with similar asymptotic behavior, but without the −3 terms, or using the powers of 2 for row 0 (and hence omitting rows 0–2). These modified functions are not equal to the Ackermann function, but in terms of computational complexity theory, they can be regarded as being so. The inverse of the function  f  is less than 4 for any conceivable input size, so for practical algorithm analysis, it can be regarded as a constant.

Use as benchmark

The Ackermann function, due to its definition in terms of extremely deep recursion, can be used as a benchmark of a compiler's ability to optimize recursion. For example, a compiler which is able to "realize" that A(3, 30) is slightly less than a power of 2, or which is able to save intermediate values like the A(3, n) and A(2, n) in that calculation rather than recomputing them, can speed up computation of A(3, 30) by a factor of hundreds of thousands. Also, if A(1, n) is computed directly rather than as a recursive expansion of the form A(1, A(1, A(1,...A(1, 0)...))), this will save significant amounts of time. Computing A(1, n) takes linear time in n. Computing A(2, n) requires quadratic time, since it expands to O(n) nested calls to A(1, i) for various i. Computing A(3, n) requires time proportionate to 4ⁿ⁺¹, according to several web sources.

It may be noted that A(4, 2), which appears as a decimal expansion in several web pages, cannot possibly be computed by recursive application of the Ackermann function in any reasonable amount of time.

External links

• Some values of the Ackermann function.
• Example use of the Ackermann function as a benchmark. Note the huge number of function calls used in computing low values.
• Decimal expansion of A(4,2)