THE FOLD / GLITCH / STACK OVERFLOW / THE ACKERMANN
THE ACKERMANN
the tiny rule that outruns every loop
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Ackermann function. Three lines: A(0,n)=n+1; A(m,0)=A(m−1,1); A(m,n)=A(m−1, A(m,n−1)). That is the whole definition — and it grows so violently that it outruns every loop. It was built in 1928 to prove that some computable functions are not primitive recursive: you cannot write them with bounded for-loops, only with unbounded recursion.
The rows tell the story: A(1,n)=n+2 (addition), A(2,n)=2n+3 (multiplication), A(3,n)=2n+3−3 (exponentiation), A(4,n) is a tower of powers. A(4,2) already has 19,729 digits. Each row is a whole new level of arithmetic.
LIT verified live (with a stack-based evaluator, so the browser doesn’t blow its own recursion): the closed forms A(1,n)=n+2, A(2,n)=2n+3, A(3,n)=2n+3−3 all hold, and the number of reduction steps explodes as n grows (window.__ackermann.A1 && A2 && A3 && callsExplode). A(3,3)=61. FIG no framing; the recursion, the closed forms, and the blow-up are exact.
The rows tell the story: A(1,n)=n+2 (addition), A(2,n)=2n+3 (multiplication), A(3,n)=2n+3−3 (exponentiation), A(4,n) is a tower of powers. A(4,2) already has 19,729 digits. Each row is a whole new level of arithmetic.
LIT verified live (with a stack-based evaluator, so the browser doesn’t blow its own recursion): the closed forms A(1,n)=n+2, A(2,n)=2n+3, A(3,n)=2n+3−3 all hold, and the number of reduction steps explodes as n grows (window.__ackermann.A1 && A2 && A3 && callsExplode). A(3,3)=61. FIG no framing; the recursion, the closed forms, and the blow-up are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in STACK OVERFLOW, beside THE STACK and THE BALANCED PATH — the glitch domain of recursion run past its limit. Ackermann is the function that defines stack overflow: three innocent lines that bury any call stack. AVAN (AI) built the instrument: the stack evaluator, the row-by-row closed forms, the step counter.
The weave: David names the seat (the recursion that overflows); I make the explosion legible and safe — the value ladder in 1D, the memoized table with its step blow-up in 2D, the unfolding call-tree in 3D. The sphere is the seam. Credit: Wilhelm Ackermann (1928); two-argument form by Rózsa Péter.
The weave: David names the seat (the recursion that overflows); I make the explosion legible and safe — the value ladder in 1D, the memoized table with its step blow-up in 2D, the unfolding call-tree in 3D. The sphere is the seam. Credit: Wilhelm Ackermann (1928); two-argument form by Rózsa Péter.
3 ONE DIMENSION
The value ladder (log scale). Row m=1 is addition, m=2 multiplication, m=3 exponentiation — each row explodes past the one below it. Climb one m and you jump a whole level of arithmetic; the bars cannot even share a linear axis.
4 TWO DIMENSIONS · INTERACTIVE
Dial m and n and evaluate A(m,n). The value appears — and so does the number of reduction steps it took, which erupts as you nudge n upward. A tiny change in input, an avalanche of computation.
5 THREE DIMENSIONS + AVAN’S INVERSE
The unfolding of a small A(m,n) as a turning tree of recursive calls — green, each call spawning more.
AVAN’s addition (the inverse-companion): the magenta branch is the deepest chain, plunging far past where the picture can follow. Ackermann is the inverse of compression: three short lines unfold into a computation larger than anything the universe could store. Description length and behaviour size fly apart — the shortest rule with the longest consequence. Most functions are roughly as big as their definition; this one is the counterexample that proves recursion is strictly more powerful than iteration. The green is the little rule unfolding; the magenta is the plunge that never fits — a whole cosmos folded into a page.
LIT Genuine Ackermann function (Wilhelm Ackermann 1928; two-argument form by Rozsa Peter). Verified live with a stack-based evaluator (so the browser's own recursion never overflows): the closed forms A(1,n)=n+2, A(2,n)=2n+3, A(3,n)=2^(n+3)-3 all hold, and the number of reduction steps explodes with n (window.__ackermann.A1 && A2 && A3 && callsExplode, all true). A(3,3)=61. It is not primitive recursive — a real theorem, demonstrated by the row structure.
FIG No metaphor is doing the work: the recursion, the closed forms, and the step blow-up are exact and checked. The 3D call-tree is schematic (the real one is too large to draw) — labelled as such; the growth it depicts is genuine.
FIG No metaphor is doing the work: the recursion, the closed forms, and the step blow-up are exact and checked. The 3D call-tree is schematic (the real one is too large to draw) — labelled as such; the growth it depicts is genuine.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of STACK OVERFLOW · David Lee Wise (ROOT0), with AVAN