The Ackermann function is a killer: It looks very simple, yet it plays a major
role in computer science and computational complexity theory. This is its
definition.

(Source and copyright: kosara.net/thoughts/ackermann.html)

m = 0	A(0, n) = n+1
m > 0, n = 0	A(m, 0) = A(m-1, 1)
m > 0, n > 0	A(m, n) = A(m-1, A(m, n-1))

Looks harmless, doesn't it? If you calculate the first three lines (where
'line' means that m is fixed, and n varies), you get the following table:

	n
m	0	1	2	3	4	5	6	7	8	9	10
0	1	2	3	4	5	6	7	8	9	10	11
1	2	3	4	5	6	7	8	9	10	11	12
2	3	5	7	9	11	13	15	17	19	21	23
3	5	13	29	61	125	253	509	1021	2045	4093	8189

This is the table that you find in many books on programming or recursions.
In fact, this so-called function hardly counts as one, since it doesn't do
any real calculations (except for one '+'). It is more like an array, whose
values are used to access other parts of the array. This is easy to see
when you write
the function slightly differently, with square brackets instead of parentheses:

m = 0	A[0, n] = n+1
m > 0, n = 0	A[m, 0] = A[m-1, 1]
m > 0, n > 0	A[m, n] = A[m-1, A[m, n-1]]

If you think of the first function as the initialization for line 0 of the
array, it becomes obvious that
this function doesn't contain any calculations of the actual values, only of
their indices. Putting this into a computer program is pretty
straight-forward, but there are
some restrictions in the real world that will be addressed now.

For this purpose, let's go back to the way the values grow with different parameters m and n. The first
two lines are pretty boring, and my 'not-a-function-but-an-array'-hypotheses isn't very exciting, either. The third line still
seems to follow a simple rule, but the fourth one (m=3) shows a very strange behaviour. Suddenly, the
numbers grow quite quickly, in fact, they more than double from n to n+1.

You can try it yourself, and write a small program that calculates these numbers, and you will notice
that it takes a lot of time to calculate the values in line m=3, so finding a more direct way would be
needed. And this is where the trouble starts ...

No, it's not finding the functions, that is particularly difficult. Just look at one line at a time, and
you will find it easy to work out the following functions (where 'x^y' stands for 'x to the power of y'):

m	A(m, n) = f(n)
0	A(0, n) = n+1
1	A(1, n) = n+2
2	A(2, n) = 3+2*n
3	A(3, n) = 5+8*(2^n-1)

Wonderful, isn't it? This actually seems to make the function a lot less scary, since you don't have to
wait for the result any more, you can calculate it for any n within the same time. But wait, what am I
writing here? Any n? Mathematically speaking, that's true, but suppose we want to write a program
that calculates the value of the Ackermann function, and let C be the chosen language. In C, we can easily handle numbers up to 2^32-1, but let's call the
largest number we have H (for 'Huge'). Using the formulas above, we can easily find out the largest n for
every H and every m < 4 ('ld' is the 'logarithmus dualis', the base 2 logarithm):

So much for the C programming! We can't go further to the right than n=29 in the m=3-row, and we still
don't have a formula for the m=4-row (please not, by the way, that we can, in fact, use the whole range
of n we just computed, since the intermediate results in all the formulas in the last table are smaller
than their final results!). Using the table from the very top of this article, we see that A(4, n) =
A(3, A(4, n-1)), which is a bit of a problem, since we still can't calculate A(4, n-1). But wait! If
n-1 = 0, we can use A(m, 0) = A(m-1, 1), so A(4, 0) = A(3, 1), which we can look up in the second table,
or calculate easily. So, by using a small number of recursions, we can reduce the problem to one we can
solve very quickly.

But there is a catch (you've expected that, haven't you?): A(4, 0) = 13, that's easy. A(4, 1) is a
lot larger, A(4, 1) = 65533! And now, when trying to evaluate A(4, 2), we get into real trouble: A(4, 2) =
A(3, A(4, 1)) = A(3, 65533) = 5+8*(2^65533-1)! The result is a number which consists of 19729 digits!!
Now we can go one line further, to A(5, 0) = A(4, 1) = 65533, but A(5, 2) = A(4, A(5, 1)) = A(4, 65533)
already is far beyond our reach, we can't even calculate A(4, 3) = A(3, A(4, 2))!!

This is also true for A(6, 0) = A(5, 1) - which means, that we can't calculate a single value from
the seventh line, or those beyond! So this is the final table:

Please have a look at A(4, 2), it's really impressing (it will make you
understand why there were only the first four lines in the first table ;-)!

Programs

Finally, I want to show you the programs I used for calculating the number above. They are pretty
straight-forward, really! I used LISP, for its ability to work with arbitrarily large numbers; the LISP
interpreter I used was CLISP, which is freeware, and should run on almost every computer, and under most
operating systems. Here's the program:

(defun ackermann (m n) "The Ackermann Function"
(cond ((= m 0) (+ n 1))
      ((= m 1) (+ n 2))
      ((= m 2) (+ 3 (* n 2)))
      ((= m 3) (+ 5 (* 8 (- (expt 2 n) 1))))
      (t (cond ((= n 0) (ackermann (- m 1) 1))
               (t (ackermann (- m 1) (ackermann m (- n 1))))
         ))
))

You can run it by cutting it out here, and pasting into your favorite LISP interpreter (Emacs LISP won't
work, because it can't handle arbitrarily large numbers), and invoking it with (You have to substitute m
and n by the parameters you want to have the result for, of course):

(ackermann m n)

The function that counts the number of digits is very bad LISP style, I know, and it is very slow, but I
am not a LISP wizard (ha! not even remotely), and it is sufficient for this purpose.

(defun digits (num) "number of digits of num"
(setq a 0)
(loop
 (setq a (+ a 1))
 (setq num (floor (/ num 10)))
 (when (= num 0) (return a))
))

Invoking it with

(digits (ackermann m n))

will give you the number of digits of A(m, n).