The Ackermann function is an important example encountered by mathematicians 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. 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. It grows extremely quickly, and 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. Due to its definition in terms of extremely deep recursion, it can be used as a benchmark of a compiler's ability to optimize recursion. (more...)
Recently featured: Black hole – Irish theatre – Coronation of the British monarch