Worked solution: The MRDP theorem: Diophantine sets are exactly the recursively enumerable sets (1970)

Frequently asked questions

Why is this combined result called the MRDP theorem rather than just "Matiyasevich's theorem"?

Because the full result required all four contributions in sequence: Robinson's JR-hypothesis and bootstrapping machinery, Davis's normal form and original conjecture, Putnam's contribution to the 1961 exponential-Diophantine result, and Matiyasevich's Fibonacci relation closing the final gap; the initials MRDP honor all four.

Source

Yuri Matiyasevich, completing work of Martin Davis, Hilary Putnam, and Julia Robinson, 1970

Matiyasevich theorem

Condensed summary

Step 7 of 9: Completing the chain: the MRDP theorem

Previous step Next step

In plain words

With the Fibonacci growth engine finally proven Diophantine, all of Robinson's earlier bootstrapping machinery from the JR-hypothesis kicks in at once: first plain exponentiation $y = 2^x$ becomes Diophantine, then binomial coefficients, then factorials.

With those tools in hand, one can Diophantine-encode the entire step-by-step run of any computer program — each snapshot of its memory and instruction pointer indexed by these fast-growing numbers — completing the proof that recursively enumerable sets are exactly the Diophantine sets, precisely matching Davis's 1953 conjecture. This combined result is now called the MRDP theorem, after Martin Davis, Hilary Putnam, Julia Robinson, and Yuri Matiyasevich.

y = 2^x,\ \binom{n}{k},\ n! \text{ all Diophantine} \implies \text{every r.e. set is Diophantine (MRDP theorem)}

Detailed analysis

Once $v = F_{2u}$ is known to be Diophantine (Step 6), Robinson's JR-machinery from Step 4 fires in sequence: exponentiation $y = 2^x$ becomes Diophantine (essentially by relating powers of $2$ to Fibonacci-like recurrences with the required growth rate), then the binomial coefficient function $\binom{n}{k}$ (via generating-function identities reducible to exponentiation), then the factorial function $n!$ .

With factorial and exponentiation both Diophantine, one can encode the entire configuration history of a Turing machine — the contents of its tape, head position, and internal state at every time step — as a single large number via a Gödel-style numbering scheme, and express "this number encodes a valid, halting computation of machine $e$ on input $a$ " as a Diophantine condition on $a$ and $e$ . This shows every recursively enumerable set is Diophantine, matching Davis's 1953 conjecture exactly.

Combined with the easy direction from Step 2 (Diophantine $\implies$ r.e.), this establishes the MRDP theorem: recursively enumerable sets and Diophantine sets are exactly the same class. The final step uses this equivalence to derive Hilbert's tenth problem's negative answer.

Knowledge used in this step

Recursive functions and Turing machines Linear Diophantine equations