Ackermann function

Wilhelm Ackermann in about 1935.

The Ackermann function is one of the most important functions in computer science. Its most outstanding property is that it grows astonishingly fast. In fact, it gives rise to such large numbers very quickly that these numbers, called Ackermann numbers, are written in a special way known as Knuth's up-arrow notation.

The Ackermann function was discovered and studied by Wilhelm Ackermann (1896–1962) in 1928. Ackermann worked as a high-school teacher from 1927 to 1961 but was also a student of the great mathematician David Hilbert in Göttingen and, from 1953, served as an honorary professor in the university there. Together with Hilbert he published the first modern textbook on mathematical logic. The function he discovered, and that now bears his name, is the simplest example of a well-defined and total function that is also computable but not primitive recursive (PR). "Well-defined and total" means that the function is internally consistent and doesn't break any of the rules laid down to define it. "Computable" means that it can, in principle, be evaluated for all possible input values of its variables. "Primitive recursive" means that it can be computed using only for loops – repeated application of a single operation a predetermined number of times. The recursion, or feedback loop, in the Ackermann function overruns the capacity of any for loop because the number of loop repetitions isn't known in advance. Instead, this number is itself part of the computation, and grows as the calculation proceeds. The Ackermann function can only be calculated using a while loop, which keeps repeating an action until an associated test returns false. Such loops are essential when the programmer doesn't know at the outset how many times the loop will be traversed. (It's now known that everything computable can be programmed using while loops.)

The Ackermann function can be defined 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

Two positive integers, m and n, are the input and A(m, n) is the output in the form of another positive integer. The function can be programmed easily in just a few lines of code. The problem isn't the complexity of the function but the awesome rate at which it grows. For example, the innocuous-looking A(4, 2) already has 19,729 digits! The use of a powerful large-number shorthand system, such as the up-arrow notation, is indispensable as the following examples show:

     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.

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.