ヒルベルトの第10問題は、任意のディオファントス方程式（整数係数をもつ多項式方程式）を与えられたとき、その方程式に整数解があるかどうかを判定する単一のアルゴリズムを求める問題である。1900年にデイヴィッド・ヒルベルトがヒルベルトの問題の一部として提示し、数論と計算機科学の理論を結びつける中心的な問いとなった。
問題の意味
簡単にいえば、ディオファントス方程式とは、いくつかの未知数を含む整数係数の多項式方程式全般を指す。一次方程式、二次形式、さらに複雑な多項式表現も含まれる。求められていたのは、特定の一つの方程式のための手続きではなく、そのような任意の多項式の係数を受け取り、整数解の有無に応じて「はい」または「いいえ」を返して停止する一般的で効果的な方法、つまりアルゴリズムであった。
主要な数学的概念
- ディオファントス集合：多項式方程式の整数解において、ある1つの座標として現れうる整数の集合。
- 再帰的可算と決定可能：どの集合や問題にアルゴリズムが存在するかを分類するために、計算可能性理論で用いられる概念。
- DPRM定理：マーティン・デイヴィス、ヒラリー・パトナム、ジュリア・ロビンソン、ユーリ・マチャセヴィチの共同研究により、再帰的可算集合とディオファントス集合の同値が示された。背景としてディオファントス方程式に関する研究を参照。
歴史と不可決定性の結果
20世紀半ば、研究者たちは数論と計算可能性を結びつけ、整数に関する多くのアルゴリズム的問いが一般の決定問題と同程度に難しいことを示した。決定的な進展は、ユーリ・マチャセヴィチが、任意のディオファントス方程式の可解性を判定する単一アルゴリズムは存在しないことの証明に必要な最後の一歩を完成させたときにもたらされた。この結果はしばしばデイヴィス、パトナム、ロビンソン、マチャセヴィチの共同の成果として帰され、通常は1970年のものとされることが多い。マチャセヴィチの定理と呼ばれることもあり、ヒルベルトの第10問題に対して否定的な答えを与える。数学における自然な不可決定問題の中心的な例である。証明の方針についての補足としては、ヒルベルトの問題群や、DPRMの研究者たちが用いた計算枠組みに関する解説が参考になる。
帰結と重要性
ヒルベルトの第10問題の不可決定性には、いくつもの重要な意味がある。整数上のあらゆる多項式方程式を一律に扱える機械的手法は存在しないことを示している。また、この結果は数論を論理学と計算可能性に結びつける。整数解に関する多くの自然な問いは、この結果から不可決定性や計算量上の難しさを受け継ぐ。有理数についての変種、特定の環や体に対する変種、あるいは制限された種類の方程式に対する変種は、今なお活発な研究対象であり、決定可能なものもあれば未解決のものもある。
例と関連する方向性
- フェルマー型方程式のような具体的なディオファントス方程式は初期の研究を促したが、一般アルゴリズムではなく、個別に解析される。
- 研究によって、計算を符号化する明示的なディオファントス方程式の族が構成され、算術がどのようにアルゴリズムを模倣できるかが示された。この関係が、全般にわたって可解性を判定することが不可能である理由を説明している。
- 拡張的な研究では、他の領域における定義可能性と決定可能性が扱われる。多くの結果は数学論理学と有効手続きの言語で記述されており、より深く学ぶにはアルゴリズム的決定可能性に関する解説や、DPRM定理の概説が役立つ。
ヒルベルトの第10問題は、今も重要な画期的成果である。多項式方程式についての具体的な問いを、数学におけるアルゴリズム的方法の限界を示す基本例へと変えた。異なるレベル向けの入門としては、証明の考え方とその後の研究の流れをまとめた解説や総説が適している。数論におけるディオファントス方程式の役割を知るための出発点としては、一般的なディオファントス方程式の説明がある。証明に関する技術的文献や一次資料については、DPRMの仕事とマチャセヴィチの貢献を扱う専門的な参考文献を参照するとよい（さらなる文献および歴史的注記）。