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

Frequently asked questions

Did Turing already know about Hilbert's tenth problem when he proved this in 1936?

Turing's 1936 paper addressed the closely related Entscheidungsproblem (the decision problem for first-order logic), not Hilbert's tenth problem directly; the specific connection to Diophantine equations, via the notion of recursively enumerable sets, was made by Martin Davis and others starting in the 1950s.

Source

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

Matiyasevich theorem

Condensed summary

Step 8 of 9: The halting problem: a listable set that is not decidable

Previous step Next step

In plain words

Imagine trying to write a master-checker program that looks at the code of any other program and correctly predicts, in advance and without running it forever, whether that program will eventually halt or run forever. Alan Turing proved in 1936, with a clever self-referential trick, that no such master-checker can ever exist for all programs at once.

Yet the set of "programs that halt on their own code" is still listable: you can always confirm "yes it halts" by literally running the program and waiting for it to stop, you just can never be sure "no, it never halts" in any fixed amount of time. This is a concrete example of a set that is recursively enumerable but not decidable — and, by the MRDP theorem, it must therefore already be Diophantine.

K = \{ e : \text{program } e \text{ halts on input } e \}, \quad K \text{ is r.e. but not decidable (Turing, 1936)}

Detailed analysis

Alan Turing, in his foundational 1936 paper on computable numbers, defined a precise mathematical model of computation (the Turing machine) and used a diagonal, self-referential argument to prove the halting problem is undecidable: the set $K = \{ e : \Phi_e(e){\downarrow} \}$ (the codes $e$ of programs that halt when run on their own code as input) has no algorithm that correctly decides membership for every $e$ .

$K$ is nonetheless recursively enumerable: an algorithm can simulate program $e$ on input $e$ step by step, and output $e$ if and when the simulation halts; it simply never terminates for $e \notin K$ , so it can confirm membership but never definitively refute it. $K$ is the canonical example of an r.e.-but-not-decidable set, and essentially every classical undecidability result reduces to it in one way or another.

By the MRDP theorem proved in the previous step, $K$ , being recursively enumerable, must itself be Diophantine: there is a polynomial $P$ such that $e \in K \iff \exists x_1, \ldots, x_n\, P(e, x_1, \ldots, x_n) = 0$ . This sets up exactly the reduction the final step needs to transfer Turing's undecidability result to Hilbert's tenth problem.

Terms in this step

Decidable (recursive) set: A set for which an algorithm exists that halts on every input and correctly outputs "yes" or "no" according to membership; strictly stronger than merely being recursively enumerable.
Halting problem: The question of whether a given program halts on a given input; Turing proved in 1936 that no single algorithm can correctly answer this question for every program and input.

Knowledge used in this step

Recursive functions and Turing machines