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

集合 $S \subseteq \mathbb{Z}_{\ge 0}$ が帰納的可算(r.e.)、あるいはリスト化可能であるとは、十分な時間を与えられれば $S$ の要素をある順序でちょうど出力するアルゴリズムが存在することをいう(停止する保証はなく、非成員について何かを言う必要もない)。集合 $S$ がディオファントスであるとは、整数係数の多項式 $P$ が存在して、$a \in S \iff \exists x_1, \ldots, x_n \in \mathbb{Z}_{\ge0}$ かつ $P(a, x_1, \ldots, x_n) = 0$ となることをいう。

「ディオファントス $\implies$ r.e.」という含意は直ちに分かる:すべての組 $(x_1, \ldots, x_n)$ とすべての候補値 $a$ を対角線的に走査し、解が見つかるたびに $a$ を出力すればよい。逆方向の含意——すべての r.e. 集合はディオファントスである——は決して自明ではない、なぜなら多項式方程式は、任意のアルゴリズムの柔軟な段階的論理よりもはるかに硬直した、純粋に代数的な道具に見えるからである。

Martin Davisは1953年、この二つの概念が実は完全に一致すると予想した。次のステップではこの予想とその意義を正確に述べる。