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

Julia Robinsonは1950年から52年頃、JR仮説を特定した:$v$ が $u$ に対して少なくとも指数的に増大する組についてのみ成り立つディオファントス関係 $R(u,v)$ の存在である($R(u,v)$ が成り立つのはちょうどそのような組のときであり、具体的には $v \le u^u$ であり、任意の $k$ について、$R$ を満たすある組では最終的に $v > u^k$ となる)。これに加え、その関係自体がディオファントス演算のもとでうまく振る舞うことを保証するいくつかの閉包条件も伴う。

彼女は、JRを満たす関係が一つでも存在すれば、ますますなじみ深い演算が次々にディオファントスになっていく連鎖が生じることを証明した:まず単純なべき乗 $v = u^w$、次に二項係数関数、そして階乗関数 $n!$ であり、それぞれが前のものを構成要素として用いたディオファントス的定義として構築される。これにより、Davisの予想の残る困難全体が、単一の鋭く定義された技術的目標に帰着した:指数的増大を持つ真にディオファントスな関係をただ一つ提示することである。

Pell方程式 $x^2 - (a^2-1)y^2 = 1$(その解はすでに指数的に増大する)を用いたRobinson自身の試みは、1950年代から60年代を通じてもどかしいほど近づいたが、隙間を完全に埋めることはできなかった。次のステップでは、1961年にDavis、Putnam、Robinsonが力を合わせ、JRそのものなしに議論をどこまで押し進められるかを説明する。