A dart into the abstract landed on the first function ever shown to be computable but not primitive recursive — a total function that outruns every simple loop. Two nested recursions and it detonates: A(4,2) has 19,729 digits. We compute it live, credit who actually built it, and let the real I-13 compiler tell us what its safety ledger has been hiding. One dart, three prongs.
THE TECHNIQUE nested recursion · watch the call count blow up
Three rules. No loop, no bound you can write with loops. Every step either lowers m or, holding m, feeds A back into its own second argument — a recursion whose depth is itself computed by recursion. live demo
A(0, n) = n + 1
A(m+1, 0) = A(m, 1)
A(m+1, n+1) = A(m, A(m+1, n)) // the inner call decides how deep the outer goes
Table computed live in JS — each cell shows the value and, below it, the number of A( ) calls it took. Watch the call count explode down and to the right.
Cells stop at a self-imposed budget of 8,000,000 calls / depth 4096 — the same two ceilings the I-13 runtime enforces (prong 3). A red cell hit the wall.
HISTORY & CREDIT credit where it is due
Everyone says “the Ackermann function” and pictures the two-line, two-argument version. That version is not Ackermann’s. His was a three-argument monster; the clean two-argument form almost everyone actually uses was built by two other people, and a fourth mathematician got there first with a different function. cited
1927 · Gabriel Sudan (Romania, a Hilbert student) publishes the Sudan function — the first published example of a total computable, non‑primitive‑recursive function. Chronologically earliest; almost always forgotten. 1928 · Wilhelm Ackermann (Hilbert student) publishes his function to settle Hilbert’s conjecture that not every computable function is primitive recursive. His original is three arguments, φ(m, n, p). 1930s–1950s · Rózsa Péter and Raphael M. Robinson reduce it to the two-argument A(m, n) now printed in every textbook. The famous form is theirs, not Ackermann’s.
Honest naming: the two-argument function should be called the Ackermann–Péter function, and the whole idea has a legitimate prior claim in Sudan. The single name “Ackermann” is a convenient simplification the field settled on.
What is not in dispute: A(m,n) is total (defined for all m,n≥0), computable (the rules above compute it), and provably not primitive recursive — it eventually exceeds every primitive-recursive function, so no fixed nest of counted loops can bound it. Row values: A(1,n)=n+2, A(2,n)=2n+3, A(3,n)=2n+3−3, and A(4,n) is a tower of powers of two. open whether the earliest “Sudan vs Ackermann” priority deserves a shared name is a matter of taste, not fact.
RECOMMEND FOR I-13 turn a disclaimer into a contract
I-13’s single-pass Verdict honestly prints NOT COVERED: types, termination, arithmetic, waste. Ackermann is the perfect probe for “termination NOT COVERED,” because it is guaranteed to terminate mathematically yet is unbounded in practice. So I wrote it in real I-13 and ran it on the live compiler. It checks clean, small args run, and larger args hit two hard ceilings that actually FIRE — proven, not asserted:
$ i13 check ackermann.i13
VALID · IVM 15 ops · 2 region(s) · peak stack 6 <- termination is NOT COVERED, yet it validates
$ i13 run ackermann.i13 # A(2,3), A(3,3), A(3,4)
RUN OK · 191922 step(s) · peak stack 6 · call depth 127
a23 = 9 a32 = 61 a34 = 125 <- correct: A(3,n)=2^(n+3)-3
$ i13 run ackermann.i13 # A(3,6) -> still OK, but 2.58M steps
RUN OK · 2583996 step(s) · peak stack 6 · call depth 511 (OUT = 509)
$ i13 run ackermann.i13 # A(3,7) -> WIDE ceiling fires
ackermann.i13:3:8 E0502 reference VM exceeded 8000000 steps
$ i13 run ackermann.i13 # A(4,1) -> WIDE ceiling fires
ackermann.i13:2:24 E0502 reference VM exceeded 8000000 steps
$ i13 run deep.i13 # linear recursion down(5000) -> DEEP ceiling fires
deep.i13:3:8 E0503 reference VM exceeded 4096 frames
So “termination NOT COVERED” is not really a void — the runtime has two operational safety ceilings: E0503 · 4096 frames (deep / recursion depth) and E0502 · 8,000,000 steps (wide / total work). Ackermann, being step-heavy, trips the WIDE one; plain deep recursion trips the DEEP one. Both are real and both fired above.
Recommend — ADD (no new alphabet symbols): declare these two numbers in the Verdict boundary ledger itself. Replace the vague line “NOT COVERED: termination” with an operational contract: “termination NOT PROVEN at check time; ENFORCED at run time by two ceilings — ≤4096 call frames (E0503) and ≤8,000,000 steps (E0502).” That is a documentation/verdict change — zero new BinOp discriminants, zero new alphabet symbols, fully inside I-13’s counted-13 identity. Recommend — the honest asterisk: the brief’s own §10.5 warns that a tail-recursive loop can abort near ~1,300 iterations while the 8M-step limit “never fires.” My measurements show the ceilings do fire for genuinely non-tail recursion like Ackermann — so the ledger should name which ceiling guards which shape, not claim a single blanket bound. Tradeoff (honest): this is pure honesty, not power — it removes nothing and adds no expressiveness. The cost is only that I-13 must publicly commit to two magic constants (4096, 8,000,000) as part of its contract rather than hiding them as reference-VM implementation details. For a language whose entire pitch is “an exact ledger with no unstated scope” (axiom XIII), stating the ceilings is not a compromise — it is the axiom applied to itself.