x² − 2y² = 1 — decides whether it has an integer solution. For most of the twentieth century no one knew if such a procedure existed. Julia Robinson spent decades on it, building the crucial machinery — the Robinson hypothesis and the Davis–Putnam–Robinson theorem — that reduced the whole question to one missing piece. In 1970 a 22-year-old in Leningrad, Yuri Matiyasevich, supplied it, completing a proof that is hers as much as anyone's: no such algorithm can exist.A 70-year problem, closed. The MRDP theorem (Matiyasevich–Robinson–Davis–Putnam) settles Hilbert's tenth: Diophantine sets are exactly the computably enumerable sets, so no algorithm decides Diophantine solvability. Rigorous and deep.
Four names, two generations, one Cold War. Davis, Putnam, and Robinson built the frame across the 1950s–60s; Matiyasevich (1970) added the final Fibonacci step. Robinson's was the central, sustained contribution — but it was a collaboration.
Why the demo has a wall. Hunting for solutions can confirm a "yes," but can never prove a "no" in general — exactly what the theorem says. The toy below finds solutions; it cannot settle the undecidable in the abstract.
A Diophantine equation asks for whole-number solutions. Some have infinitely many, some have exactly one, some have none — and there is no telling which from the look of it. Pick an equation; the machine searches a bounded range for integer solutions. Notice the asymmetry that is Hilbert's tenth: when solutions exist, a search finds them; when they don't, no bounded search can ever prove it — and the theorem says no unbounded procedure can either.
"I would rather not be remembered as the first woman this or that. I would rather be remembered… for the theorems I have proved." — Julia Robinson
The deep equivalence: a set of numbers can be defined by a Diophantine equation exactly when it can be listed by a computer program. Number theory and computability are the same reach.
Since some computably-enumerable sets are undecidable (Turing), some Diophantine questions must be too. No algorithm decides solvability for all equations.
The bridge is breathtaking: Robinson and her collaborators showed that the humble whole-number polynomial is secretly as powerful as a computer — anything a program can enumerate, an equation can capture. So the undecidability that [[alan-turing]] found in machines and [[kurt-godel]] found in proof reappears, exactly, in the arithmetic of integers. Hilbert asked for a decision machine; the answer, decades in the building, was that the integers themselves are Turing-complete, and so no such machine exists. It is one of the most surprising unifications in mathematics — number theory is computability — and Julia Robinson is at its center.
Gate kept on. The result is rigorous and monumental, and the credit is genuinely shared — the honest name is MRDP (Matiyasevich–Robinson–Davis–Putnam). Martin Davis and Hilary Putnam built early pieces; Robinson's hypothesis (that some Diophantine relation grows exponentially) was the keystone the whole edifice waited on for over a decade; and in 1970 the young Yuri Matiyasevich proved her hypothesis using Fibonacci numbers, completing it. Robinson immediately and generously credited him, and the two became close collaborators and friends across the Cold War divide — a rare thing in that era. Her contribution was the sustained spine of a twenty-year effort, not a single flourish. The woman: weakened for life by childhood rheumatic fever that damaged her heart, told she might not live long and could not have children, she poured herself into mathematics; she became the first woman president of the American Mathematical Society and the first woman mathematician elected to the National Academy of Sciences, often working without a regular faculty appointment at Berkeley for years because she was a professor's wife. She asked to be remembered for her theorems — so: she helped prove that arithmetic itself is undecidable, that the integers are as powerful as any computer. ⚑ [[rozsa-peter]] ← · next → Ruth Barcan Marcus.