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$$

  • 1
    $\begingroup$ This is a nice topic, but "I am looking for some ideas for demonstrations." is not a question. Try to reformulate your post to form a question. $\endgroup$ Oct 19, 2012 at 11:35
  • 1
    $\begingroup$ Good work +1 to the question now! $\endgroup$ Oct 19, 2012 at 14:07

1 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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.