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

ヒルベルトの第十問題は、1900年の国際数学者会議での演説で挙げられた23問題の第十番目で、任意の多項式 $P(x_1, \ldots, x_n) \in \mathbb{Z}[x_1, \ldots, x_n]$ に対して、方程式 $P(x_1, \ldots, x_n) = 0$ が整数解を持つかどうかを判定する有限回の操作による手続きを求める。この要求を強いものにしている特徴が二つある:アルゴリズムは一様でなければならず(すべての次数とすべての係数の組を一つの手続きでカバーする)、そして決定可能な部分クラスで成功するだけではなく、すべての入力で正しい是非の答えを出して停止しなければならない。

いくつかの部分クラスはすでに決定可能だった。線形方程式 $a_1 x_1 + \cdots + a_n x_n = b$ は $\gcd(a_1, \ldots, a_n)$ の計算に帰着し、一変数方程式 $P(x) = 0$ は分母を払った後、定数項の整除性に帰着する。また二変数の二次方程式は二元二次形式とペル方程式の理論に属し、連分数によって実質的に解決済みだった。どの古典的技法も届かなかったのは一般の場合で、ディオファントス方程式は任意に複雑な算術的構造を符号化でき、未知数の個数 $n$ に上界がない。

1970年にMatiyasevichによって完成された解決は否定的であり、「手続き」という非形式的な言葉を数学的对象に変えることを要する。以下の証明はMatiyasevichの2008年のScholarpedia解説に沿った経路を辿る:ディオファントス定義可能性を帰納的可算性と同一視し、Turingの停止問題の決定不能性を輸入する。