ヒルベルトの第10問題

任意のディオファントス方程式（一つ以上の未知数について整数係数を持つ多項式方程式）が与えられたとき、それが整数解を持つかどうかを有限回の手順で判定する、一般的なアルゴリズムを考案せよ。

否定的な解答は、現在MRDP定理（マティヤセビッチ・ロビンソン・デイヴィス・パトナムの定理）と呼ばれ、段階を経て築かれた。1953年、マーティン・デイヴィスは、整数の再帰的可算集合はすべて、あるディオファントス方程式族の解集合と一致すると予想した——これは（チューリングの停止問題に由来する）判定不能性を数論へ移すために必要な鍵となる着想であった。ジュリア・ロビンソンは、指数的に増大するディオファントス関係（「JR仮説」）という本質的な技術的要素を特定した。1961年、デイヴィス、ヒラリー・パトナム、ロビンソンは、指数ディオファントス方程式についてデイヴィスの予想の一形態を証明し、問題全体を、真にディオファントス的（多項式的）である指数増大の関係を一つ見つけることに帰着させた。ユーリ・マティヤセビッチは1970年にその欠けていた部分を補い、フィボナッチ数列がディオファントス条件を満たすことを示し、証明を完成させて、そのようなアルゴリズムが存在しえないことを示した。