Rózsa Péter

1905 – 1977 · Budapest · founder of recursion theory · author of "Recursive Functions" (1951) & "Playing with Infinity"

When Gödel, Church, and Turing pinned down what a machine can compute, the engine under all of it was recursion — functions defined in terms of themselves. Rózsa Péter took that engine and made it a subject: her 1951 book Recursive Functions was the first systematic treatment, and she is rightly called a founder of recursion theory, the mathematics of computability. Her signature result is a single, startling function. The "safe" functions — built from primitive recursion, the bounded loops every beginner writes — seem like they should be everything. Péter's two-variable form of the Ackermann function is total and computable, yet grows so violently it provably escapes them: a function no bounded loop can hold.

✓ STRONG

A field, and a theorem. Péter systematised recursion theory and gave the Ackermann function its standard two-argument form — a clean, total, computable function proven to outrun primitive recursion. Rigorous and foundational to computability.

◐ SHARED ROOTS

Built on Ackermann, with others. Wilhelm Ackermann found the original; Péter simplified and generalised it (the "Ackermann–Péter function") and built the surrounding theory. Recursion theory also has Gödel, Kleene, and others in its parentage.

◔ SURVIVED TO BUILD IT

The work was done against history. A Hungarian Jew, she lost her teaching post under the fascist laws and survived confinement in the Budapest ghetto; she wrote much of her foundational work in and after that. The mathematics carried through.

I · The Ackermann–Péter function — total, computable, unbounded

The rule is tiny: A(0,n)=n+1; A(m,0)=A(m−1,1); A(m,n)=A(m−1, A(m,n−1)). It always halts (it is total and computable). But watch the value — and the number of recursive calls — as m climbs. By m=4 the result is a tower of exponentials; the function provably grows faster than anything you can write with bounded for-loops. That is the proof that primitive recursion ≠ all computation.

m = n = (inputs capped — it explodes fast)

A(2,n) is roughly 2n+3; A(3,n) is exponential (2ⁿ⁺³−3); A(4,n) is a tower of 2's of height n — A(4,2) already has 19,729 digits. Each is computed by pure recursion, no loop bound in sight. ⚑ This is the precise mathematical line between "what a simple loop can do" and "what computation can do" — and Péter drew it.

"Mathematics is one of the oldest of the sciences and yet one of the youngest — for it grows by what it learns to ask." — in the spirit of Rózsa Péter, "Playing with Infinity"

II · Primitive recursion — building arithmetic from the successor

Recursion theory starts from almost nothing: zero, the successor (+1), and the schema of primitive recursion — define a function's value at n+1 from its value at n. From that alone, all of basic arithmetic unfolds. Watch addition and multiplication build themselves by recursion.

a = b =

Addition is "apply successor b times"; multiplication is "add a, b times" — each defined purely by recursion on the previous case, no magic. ⚑ These are primitive recursive: safe, always-halting, loop-bounded. Péter's achievement was to map this whole world precisely — and to show, with Ackermann's function, exactly where it ends.

III · The field, the limit, the survivor

RECURSION THEORY

Her "Recursive Functions" (1951) was the first book to organise the theory of computable functions as a subject — a cornerstone of the mathematics of computation.

THE ACKERMANN–PÉTER FUNCTION

A total computable function that is provably not primitive recursive — the clean witness that bounded loops are weaker than full computation.

Gate kept on. The mathematics is solid and foundational — recursion theory is a pillar of computability, and the two-variable Ackermann function is a textbook result, total and computable yet beyond primitive recursion. Honest attributions: the original function is Wilhelm Ackermann's (1928); Péter gave the standard two-argument simplification now usually taught (hence "Ackermann–Péter"), and her larger and more important contribution was making recursion theory a coherent field — though Gödel, Kleene, and others share its foundations. The woman: Rózsa Péter (born Politzer) was a Hungarian Jew who, under Hungary's fascist racial laws, was dismissed from teaching and forbidden to work, and survived confinement in the Budapest ghetto during the war — doing and preserving mathematics through it. Afterward she became a beloved professor and wrote Playing with Infinity, one of the finest popular books on mathematics ever written, insisting the subject was for everyone. She made the theory of "functions that call themselves" into a science — the formal soul of every program that loops or recurses in [[psephos-processors-domain]]. ⚑ [[christine-ladd-franklin]] ← · next → Julia Robinson.