Organization:

Alexa Crawls
Starting in 1996,

Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the

Wayback Machine after an embargo period.

Crawl data donated by Alexa Internet. This data is currently not publicly accessible

[Overview]
[Previous]
[Next]
# Ackermann's Function

Ackermann's function is an example of a function that is
*mu-recursive* but not primitive recursive.
(Mu-recursive functions have the power of a Turing machine.)
Here is the definition:

A(0, y) = y + 1

A(x, 0) = A(x - 1, 1)

A(x, y) = A(x - 1, A(x, y - 1))
Looks innocuous, doesn't it?

Ackermann's function is one of the few things I actually
remember from the recursive function theory course I
took many long years ago.
It's just a really neat function.
Play with it a bit and you'll see what I mean.

## Good uses for Ackermann's function

**Stress-test your computer.** See just how many values of
Ackermann's function you can compute.
**Liven up a boring meeting.** Instead of sitting there
doodling, bring in a copy of Ackermann's function and see how
far you can get with it.
If you have ever played with numbers, I guarantee it will
be a lot more interesting than drawing random designs.

**Test your programming skills.**
There are a lot of short cuts you can find to help compute
Ackermann's function much faster. How many of them can you find?

**Make money fast.** Bet a hotshot programmer that s/he
can't write a program in less than an hour to compute A(5,5).
Or be generous -- give them a week.

Copyright © 1996 by David Matuszek

Last modified Apr 18, 1996