|
|
A few months ago, I posted an algorithm for Ackermann's function, but I did not give a very good background or explanation for it. Here it is:
In the 1920's the German logician and mathematician Wilhelm Ackermann defined a function that now bears his name. This function is very important in computer science because it helps answer the question of what can and cannot be computed on a computer. It's definition is as follows:
A(0,n) = n+1 For all nonnegative integers n, A(m,0) = A(m-1, 1) For all positive integers m, A(m,n) = A(m-1, A(m, n-1)) For all positive integers m and n.
The special properties of the Ackermann function are a consequence of it's phenominal rate of growth. While the values of A(0,0) = 1, A(1,1) = 3, A(2,2) = 7, and A(3,3) = 61 are not especially impressive,
A(4,4) = 22265535
and the values A(n, n) continue to grow with extraordinary rapidity.
