The Ackermann function is an important example in mathematics of 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 fast – 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.
Read the rest of this article:
Today's selected anniversaries:
1664 In the Second Anglo-Dutch War, the Netherlands surrendered
to England a fortified settlement in the New Netherland
colony known as New Amsterdam, which would eventually
become New York City.
1841 Sultan of Brunei granted Sarawak to British adventurer
James Brooke, who subsequently became the Rajah.
1869 "Black Friday": Gold prices plummeted as a group of
speculators, headed by Jay Gould and James Fisk, plotted
but failed to control the market.
1948 Soichiro Honda founded the Honda Motor Co., Ltd. and began
Wikiquote of the day:
"Goodness alone is never enough. A hard cold wisdom is required,
too, for goodness to accomplish good. Goodness without wisdom
invariably accomplishes evil." ~ Robert Heinlein in Stranger in a