Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  belisarius Oct 19 '12 at 11:35
1  
Good work +1 to the question now! –  belisarius Oct 19 '12 at 14:07
add comment

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

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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