The Ackermann Function

The Ackermann Function was defined by Ackermann in 1928:

ack (0,y) = y+1
ack (x,0) = ack (x-1, 1)
ack (x,y) = ack (x-1, ack (x, y-1))

It looks quite harmless, but I'm pretty sure it grows faster than any other function you ever heard of before. If you don't believe it, try to compute all values of ack(x,y) for 0 <= x,y <= 5.

The Ackermann function became famous because unlike normal everyday functions it is NOT primitive recursive.

June 9, 1995
Mark Dettinger