
The Ackermann function is defined by recursion as follows:
The Ackermann function grows extremely fast; A(4,2) already has 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.
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 uparrow notation:
In 1928, Wilhelm Ackermann considered a function A(m, n, p) of three variables, the pfold 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 twovariable definition given above.
Since the function f(n) = A(n,n) considered above grows really fast, its inverse grows really slowly. Interestingly, this inverse occurs in the runtime analysis of some algorithms.
Search Encyclopedia

Featured Article
