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

1953年、Martin Davisは、すべての帰納的可算集合 $S \subseteq \mathbb{Z}_{\ge 0}$ がディオファントス集合に等しいと予想した:整数係数の多項式 $P$ が存在し、$a \in S$ であることと $\exists x_1, \ldots, x_n \in \mathbb{Z}_{\ge 0}$ で $P(a, x_1, \ldots, x_n) = 0$ となることが同値である。これはDavis自身の「Davis標準形」の結果——それ自体Gödelによる計算可能述語の算術化を精密化したもの——に基づいており、すべてのr.e.集合はすでに $\exists x\, \forall y \le x\, \exists z_1, \ldots, z_k$(多項式方程式)という形の定義を持つ、すなわち純粋な存在(ディオファントス)的定義を妨げているのはただ一つの有界な全称量化子だけであるというものだった。

その単一の有界量化子を排除することは、さらに二十年近い研究を要することが判明した。なぜなら、それは有界探索や指数サイズの計算を何らかの形で模倣できる多項式方程式を見つけることを要求したからであり、通常の多項式的増大(入力の固定されたべき乗で有界)は根本的にそれをするには弱すぎるように見えたからである。

1950年代を通じて発展した前進の道は、まさにどの追加の要素が欠けているのかを特定することだった。次のステップでは、それを指数的増大を持つ単一の関係として正確に特定する。