[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