解法: MRDP定理:ディオファントス集合は帰納的可算集合と一致する(1970年)
ディオファントス方程式とは、整数の答えだけが数えられる多項式のパズルであり、例えば (解を持つ——ピタゴラス数)や、有名な に対する (フェルマーの最終定理によれば解を持たない)である。1900年、David Hilbertは自身の23の有名な問題の第十番目として、そのような方程式が与えられれば常に正しく「はい、整数解を持つ」あるいは「いいえ、持たない」と答える単一の万能なレシピを求めた。
当時、「アルゴリズム」は非形式的な概念だった。1930年代になってようやくAlan TuringとAlonzo Churchがこの概念を、このような問いに対して「そのようなアルゴリズムは存在しない」という決定的な答えを証明できるほど正確に定めた。
ヒルベルトの第十問題は、1900年の国際数学者会議での演説で提起されたもので、整数係数を持つ任意の多項式 について、方程式 が整数解を持つかどうかを判定するアルゴリズムを求める。いくつかのクラスはすでに完全に決定可能であることが知られていた:線形ディオファントス方程式(ユークリッドの互除法と による)、そして1920年代までには、連分数とペル方程式の理論による二変数の一般的な二次方程式である。
一般の高次・多変数方程式はあらゆる古典的技法に抵抗し、この問題は半世紀以上未解決のまま、「アルゴリズム」という概念自体の正確な数学的定義を待っていた。その定義は1930年代、TuringマシンとChurchやGödelの同値な形式主義を通じてもたらされ、単に方法を見つけられないというだけでなく、厳密な不可能性の結果を証明することがついに可能になった。
1950年代以降に発展した、この問題に取り組むための鍵は、ディオファントス方程式という代数的概念を、計算可能性理論における「可算リスト化可能」集合という概念と直接比較することだった——これが次のステップの主題である。
- ディオファントス方程式
- 整数係数を持つ多項式方程式 であり、整数(あるいは時に非負整数)の解のみが関心の対象となるもので、古代の数学者ディオファントスにちなんで名付けられた。
- アルゴリズム(判定手続き)
- 有限で機械的な段階的手続きであり、あらゆる可能な入力に対して必ず停止し正しい是非の答えを与えることが保証されているもの。1930年代にTuringマシンおよび同値な形式主義によって数学的に厳密化された。