Demonstrating Ackermann's Function

Question

The Ackermann function is an extremely fast growing function. There are some slightly different versions of the function, but the one that I am looking for can be defined as:

$$ A_0(x)=x+1 \\ A_{k+1}(x)=A_k^x(x) $$

where $A_k^i = \underbrace{A_k \circ \dots \circ A_k}_i$. It can be defined in Mathematica as,

A[0, 1, x_] := x + 1;
A[k_, 1, x_] := A[k - 1, x, x];
A[k_, i_, x_] := Nest[Function[y, A[k, 1, y]], x, i];

There might be faster implementations (I am looking for it too), but the above one works correctly. I want to demonstrate the function for a number of students and for myself so that it is understood deeply. How can I demonstrate how rapidly the Ackermann's function grows?

Note that while computing the function for large numbers take a long time, there are fast lower bound for the function. For instance we know:

$$A_0(x) = x + 1$$

$$A_1(x) = A_0^x(x) = 2x$$ $$A_2(x) = A_1^x(x) = x2^x \ge 2^x$$ $$A_3(x) = A_2^x(x) \ge \underbrace{2^{2^{{ ... }^2}}}_x = 2 \uparrow x $$ $$A_4(x) = A_3^x(x) \ge \underbrace{2\uparrow(2\uparrow\dots\uparrow(2\uparrow 2)\dots)}_x=2\uparrow\uparrow x$$

Answer 1

With regards to speeding up your algorithm:

Memoization looks like something that can definitely speed this up. Since only $A_0$ is non-recursively defined, you always rely on it for your calculations.

yourA[0, 1, x_] := x + 1
yourA[k_, 1, x_] := yourA[k - 1, x, x]
yourA[k_, i_, x_] := Nest[Function[y, yourA[k, 1, y]], x, i]

And the one that utilizes memoization:

A[0, 1, x_] := x + 1
A[k_, 1, x_] := Block[{a}, A[k, 1, a_] = A[k - 1, a, a]; A[k, 1, x]];
A[k_, i_, x_] := Nest[Function[y, A[k, 1, y]], x, i]

Here's the difference:

yourA[3, 1, 2] // AbsoluteTiming
A[3, 1, 2] // AbsoluteTiming
(* {0.0100006, 2048} *)
(* {0., 2048} *)

When evaluating something like A[1,20,2], you'll get an error message about the fact that there is no machine-sized integer for Nest. Adding an additional DownValue helps out (this makes the first one obsolete, by the way).

A[0, i_, x_]:= i + x

EDIT

I was playing around with the function, but when I tried A[3,1,3], my computer froze since the memory-intensive program was using up 95% of my 8GB RAM. You can try to use your original function (the one without memoization), but it will definitely take a while to compute.