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:
http://en.wikipedia.org/wiki/Ackermann_function
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.
(
http://en.wikipedia.org/wiki/New_Amsterdam)
1841 Sultan of Brunei granted Sarawak to British adventurer
James Brooke, who subsequently became the Rajah.
(
http://en.wikipedia.org/wiki/Sarawak)
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.
(
http://en.wikipedia.org/wiki/Black_Friday_%281869%29)
1948 Soichiro Honda founded the Honda Motor Co., Ltd. and began
manufacturing motorcycles.
(
http://en.wikipedia.org/wiki/Honda)
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
Strange Land
(
http://en.wikiquote.org/wiki/Stranger_in_a_Strange_Land)