◄ WORLD V · SONNY 5DART 132 · a helldive at the net

MCCARTHY 91 a nest of m(m(...)) that is always 91

m(n) = n − 10 if n > 100, else m(m(n + 11)). The double self-application makes the control flow almost impossible to trace by eye — yet it is total, and returns exactly 91 for every n ≤ 100 (and n−10 above). McCarthy built it as a deliberate trap for program verifiers: the whole difficulty is seeing that a tangle of m(m(m(…))) collapses to one constant.

THE TECHNIQUE watch the nest collapse to 91

Below 101, each call replaces n with m(m(n+11)) — the inner call climbs above 100, the outer subtracts back down, and every path funnels to 91. Above 100 it is just n−10. Pick an n and watch the nested calls resolve. It is total over all integers, including negatives. live demo







  
HISTORY & CREDIT 1970 papers, not the 1974 book

  
“It comes from Manna’s 1974 book” — no; two 1974 1970 papers introduced it. The 1974 book only popularized it. cited

  

    ~1968–70 · John McCarthy engineers the function as a deliberately hard-to-verify nested-recursion test — posed, not published, by him.

    1970 · Manna & Pnueli (J.ACM 17(3)) and Manna & McCarthy (Machine Intelligence 5) — the first formal termination/validity proofs; the “91-function” is named here.

    1978 / 1979 · Takeuchi’s TAK (a separate triple-recursion benchmark, always paired but not the same); Boyer & Moore’s NQTHM makes m91 a standard theorem-prover challenge.

    1991 · Knuth generalises it to parameters (a,b,c,d) in the McCarthy Festschrift — “Textbook Examples of Recursion.”
  

  
Structurally Ackermann-like (nested recursion) but bounded — the challenge is seeing it terminates and returns 91, not taming explosive growth. McCarthy ~1970






  
RECOMMEND FOR I-13 arguably the best-fitting classic

  
The whole function is a single named recursive procedure over f64 — every value it touches is an exact integer far inside 253, and it lands on 91:

  
$ i13 run mc.i13    # def m(n){ if n>100 {->n-10} -> m(m(n+11)) }
m(1)=91  m(50)=91  m(99)=91  m(100)=91  m(101)=91  m(111)=101

  

    Recommend: nothing new, and arguably the best-fitting classic for the I-13 surface — no arrays, no strings, no state: one def m(n) with a single comparison and the nested double call (verified 91 for n=1/50/99/100/101, 101 for n=111). Every value (91, 100, 101, 111) is an exact f64 integer.

    Note: it exercises exactly what the 8/19 benchmark’s runtime governors guard — recursion depth (bounded at 4096 frames) and totality. m91 is the canonical “does this obviously-tangled recursion even terminate?” — and here it runs, bounded and total, in the counted language.