Wikipedia:Today's featured article/September 24, 2004

Defintion of the Akermann function
Defintion of the Akermann function

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 (mnp) 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(nn) 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 holeIrish theatreCoronation of the British monarch