Skip to content
All apps

Ackermann function

About this app

Follow recursive calls and stack depth as a few simple rules produce explosive growth. Explore a growth matrix and the limits of direct computation.

With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.

Three rules, enormous growth

The Ackermann function is defined by three rules: A(0, n) = n + 1, A(m, 0) = A(m − 1, 1) and A(m, n) = A(m − 1, A(m, n − 1)). It is computable and terminates for all natural numbers, but it grows faster than any primitive recursive function. The first parameter moves the operation one level higher: m = 0 is the successor, m = 1 corresponds to addition, m = 2 to multiplication, m = 3 to exponentiation and m = 4 to a power tower. A(4, 2) = 2^65536 − 3 already has 19,729 decimal digits.

What the app shows

On the left the recursion runs live: the three rules light up when they apply, a chain of coloured calls shows the current nesting, and a mountain plots the stack depth over all steps, with its peak marked. The result is shown at the top. On the right a growth matrix shows A(m, n) for every level together with the name of the operation. For m = 4 from n = 1 on, the app refuses to animate and shows the size of the number instead.

Try it yourself

Choose m from 0 to 4 and n from 0 to 5, play the recursion, step through it or drag the playback position across the mountain. The speed goes from one to 10,000 steps per second. Compare A(2, 3) with A(3, 3) and watch the mountain shoot up, then try m = 4 to see why the app refuses.

Frequently asked questions

How is the Ackermann function defined?
A(0, n) = n + 1; A(m, 0) = A(m − 1, 1) for m > 0; A(m, n) = A(m − 1, A(m, n − 1)) for m, n > 0. These three rules are enough to compute the function for all natural numbers m and n.
Why is the Ackermann function not primitive recursive?
Primitive recursive functions can be written with loops whose number of iterations is fixed in advance. For each such function there is an m from which A(m, ·) grows faster. The Ackermann function is therefore computable and total, but cannot be expressed with loops bounded in advance.
How large is A(4, 2)?
A(4, 2) = 2^65536 − 3, a number with 19,729 decimal digits. A(4, 1) is only 65533, while A(4, 3) = 2^(2^65536) − 3 is too large for its digits ever to be written out.
What can I watch in the Ackermann app?
How each rule applies, how the call chain grows and shrinks and how high the stack gets, for any m and n you choose. The growth matrix shows which operation each level m stands for and, at m = 4, how large the results are.

Subject: Computer science

More from Computer science

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps