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

Frequently asked questions

Does this mean no Diophantine equation can ever be solved?

No — countless specific equations and entire well-behaved classes (linear equations, one-variable equations, many quadratic forms) are perfectly solvable by known methods. The theorem only rules out a single universal algorithm that would work for every possible equation without exception.

Was Hilbert's tenth problem the only one of his 23 problems to get a negative solution?

No — several others also received negative answers, most famously the first problem (the continuum hypothesis, shown independent of $\mathrm{ZFC}$ by Gödel and Cohen) and the second (consistency of arithmetic, addressed by Gödel's incompleteness theorems).

Source

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

Matiyasevich theorem

Condensed summary

Step 9 of 9: Conclusion: no algorithm can decide Diophantine solvability

Previous step Next step

In plain words

Combining everything: the set $K$ of self-halting programs is Diophantine (by MRDP), meaning there is a fixed polynomial that captures exactly which programs halt on themselves through the solvability of an equation. If a general algorithm for deciding Diophantine solvability existed, one could feed it that very equation and use its answer to decide the halting problem — but Turing already proved in 1936 that no algorithm can do that.

So Hilbert's tenth problem, posed in 1900 as a request for exactly such an algorithm, has a definitive negative answer: no algorithm deciding Diophantine solvability can possibly exist.

\text{Halting problem} \le_m \text{Diophantine solvability} \implies \text{Hilbert's tenth problem is undecidable}

Detailed analysis

Combining Turing's 1936 undecidability of the halting set $K$ with the MRDP theorem: $K$ is recursively enumerable, hence Diophantine, so there is a fixed polynomial $P$ with $e \in K \iff \exists x_1, \ldots, x_n\, P(e, x_1, \ldots, x_n) = 0$ . Suppose, for contradiction, a general algorithm $\mathcal{A}$ existed that decides, for any polynomial equation and any values of its parameters, whether it has an integer solution.

Then $\mathcal{A}$ , applied to $P(e, x_1, \ldots, x_n) = 0$ for each candidate $e$ , would decide membership in $K$ for every $e$ — contradicting Turing's theorem that $K$ is undecidable. Hence no such algorithm $\mathcal{A}$ can exist: Hilbert's tenth problem, which asked for exactly this algorithm, has a definitively negative answer.

The theorem does not say every individual equation is mysterious — linear equations, one-variable equations, and (via the Hasse–Minkowski principle) many quadratic forms remain fully decidable — only that no single universal method can handle every polynomial equation at once, closing a question that had stood open for seventy years since Hilbert first posed it in 1900.

Knowledge used in this step

Recursive functions and Turing machines Linear Diophantine equations