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

Alan Turingは、計算可能数についての1936年の基礎的論文において、計算の精密な数学的モデル(Turingマシン)を定義し、対角線的で自己言及的な議論を用いて、停止問題が決定不能であることを証明した:集合 $K = \{ e : \Phi_e(e){\downarrow} \}$(自分自身のコードを入力として走らせたとき停止するプログラムのコード $e$)には、すべての $e$ について成員性を正しく決定するアルゴリズムが存在しない。

それでも $K$ は帰納的可算である:アルゴリズムはプログラム $e$ を入力 $e$ 上で一段階ずつシミュレートし、シミュレーションが停止すればそのとき $e$ を出力すればよい。$e \notin K$ の場合は単に決して終了しないので、成員性を確認することはできるが、決して確実に反証することはできない。$K$ はr.e.だが決定可能ではない集合の代表例であり、本質的にあらゆる古典的な決定不能性の結果は何らかの形でこれに帰着する。

前のステップで証明されたMRDP定理により、帰納的可算である $K$ はそれ自体ディオファントスでなければならない:ある多項式 $P$ が存在して $e \in K \iff \exists x_1, \ldots, x_n\, P(e, x_1, \ldots, x_n) = 0$ となる。これはまさに、Turingの決定不能性の結果をヒルベルトの第十問題へと移すために最後のステップが必要とする帰着を設定するものである。