解法: MRDP定理:ディオファントス集合は帰納的可算集合と一致する(1970年)

Turingの1936年の停止集合 $K$ の決定不能性とMRDP定理を組み合わせると:$K$ は帰納的可算であり、したがってディオファントスであるから、$e \in K \iff \exists x_1, \ldots, x_n\, P(e, x_1, \ldots, x_n) = 0$ となる固定された多項式 $P$ が存在する。背理法のため、任意の多項式方程式とそのパラメータの任意の値について、それが整数解を持つかどうかを決定する一般的なアルゴリズム $\mathcal{A}$ が存在すると仮定する。

すると、各候補 $e$ について $P(e, x_1, \ldots, x_n) = 0$ に適用された $\mathcal{A}$ は、すべての $e$ について $K$ への成員性を決定することになる——これはTuringの定理、すなわち $K$ が決定不能であることと矛盾する。したがって、そのようなアルゴリズム $\mathcal{A}$ は存在しえない:まさにこのアルゴリズムを求めていたヒルベルトの第十問題には、決定的な否定的答えがある。

この定理は、個々の方程式がすべて謎めいていると言っているのではない——線形方程式、一変数方程式、そして(Hasse–Minkowskiの原理による)多くの二次形式は完全に決定可能なままである——ただ、あらゆる多項式方程式を一挙に扱える単一の普遍的方法は存在しないということであり、1900年にヒルベルトが最初に提起して以来70年間未解決だった問いに決着をつけるものである。