[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