DPRM theorem

「ディオファントス方程式の解を（しらみつぶしに）手探りで探す行為」は、「チューリングマシン（プログラム）を実行して、それが終わるのをじっと待つ行為」と完全に同義（本質的に同じこと）になる。

チューリング（1936）が「プログラムが停止するかどうかを判定する一般的方法はない」と証明した。

DPRM（1970）が「プログラムの停止問題は、ディオファントス方程式の解の有無と完全に同じ問題に変換できる」と証明した。

結論： したがって、「ディオファントス方程式の解の有無を判定する一般的方法（アルゴリズム）も存在しない」。

これは存在しないことの証明であるとともに「ディオファントス方程式の解を（しらみつぶしに）手探りで探す行為」は、「チューリングマシン（プログラム）を実行して、それが終わるのをじっと待つ行為」と完全に同義（本質的に同じこと）になります。

1. 「手探りで探す」＝「プログラムを実行する」

ある複雑なディオファントス方程式 $P(x_1, x_2, \dots, x_n) = 0$ があるとします。この解を手探りで探す一番愚直な方法は、以下のような手順になります。

1. $(x_1, x_2, \dots, x_n) = (0, 0, \dots, 0)$ を代入してみる。
2. 次は $(1, 0, \dots, 0)$、その次は $(0, 1, \dots, 0)$……と、すべての整数の組み合わせを順番に代入していく。
3. もし計算結果が $0$ になったら、「解が見つかった！」として探索を終了する。

この「手探りの探索」のプロセス自体が、まさに1つの決定論的なアルゴリズム（チューリングマシン）です。

2. 「解の発見」＝「プログラムの停止」

DPRM定理が証明したのは、この2つの挙動の完全な一致です。

• ディオファントス方程式に「整数解が存在する」$\iff$ その方程式に対応するチューリングマシンが「いつか停止する」
• ディオファントス方程式に「整数解が存在しない」$\iff$ その方程式に対応するチューリングマシンは「永遠に停止しない（無限ループする）」

つまり、効率的な解法がないディオファントス方程式に対して、私たちが整数を1つずつ代入して手探りで探しているとき、私たちは「人間の手でチューリングマシンを1ステップずつ動かして、プログラムが止まるかどうかを追いかけている」状態です。

3. なぜ「効率的な発見」ができないのか？

「もっと賢い、効率的な解の発見方法（数式をこねくり回して一発で解くような方法）はないのか？」と思うかもしれません。しかし、それこそが不可能であることが証明されています。

なぜなら、もし任意のディオファントス方程式に対して「手探り」以外の効率的な解の判定法（アルゴリズム）が存在するとしたら、それを使って「あらゆるコンピュータプログラムが無限ループに陥るかどうかを事前に100%判定できる魔法のツール（停止性問題を解決するアルゴリズム）」が作れてしまうことになるからです。

アラン・チューリングは1936年に「そんな魔法のツール（停止性問題を解くアルゴリズム）は絶対に作れない」ことを証明しました。したがって、その裏返しとして、ディオファントス方程式の解の探索も、本質的に「手探りでプログラムを進めて、止まる（解が出る）のを待つ」以上のスマートな一般解法は存在し得ないということになります。

ただし、一度NPの解法を3-SATで構築した場合に、再現するのはとても簡単です。したがって証明構築がすでにされたものについては模範解答を見てしまった方が圧倒的に早いし効率的であるというのはNPやチューリングマシン、ディオファントス方程式の性質から導出することができます。「解の見つからないディオファントス方程式を手探りで解こうとする営み」は、「いつ終わるか（そもそも終わるかどうかも）分からないプログラムの実行ボタンを押して、画面をじっと眺めていること」と完全に同じです。

数学者たちが何百年もディオファントス方程式の難問（フェルマーの最終定理など、歴史的な難問の多くがこれに属します）に頭を悩ませてきたのは、彼らが挑んでいたのが「宇宙で最も複雑なコンピューティング」だからと言えます。

1. 幕開け：問題の提示（1900年）

• 1900年：ヒルベルトの23の問題（デヴィット・ヒルベルト）
  • 著者: David Hilbert
  • 論文名: Mathematische Probleme（数学諸問題）
  • 掲載誌: Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse, pp. 253–297 (1900).
  • ※翌1901年にフランス語訳、1902年に英語訳（Bulletin of the American Mathematical Society）が公開され世界に広まりました。この中の「Problem 10」が該当の問題です。

2. 土台：計算可能性の定義とチューリングの証明（1930年代）

• 1931年：不完全性定理（クルト・ゲーデル）
  • 著者: Kurt Gödel
  • 論文名: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I（プリンキピア・マテマティカおよび関連する体系の形式的に決定不能な命題について I）
  • 掲載誌: Monatshefte für Mathematik und Physik, Vol. 38, pp. 173–198 (1931).
• 1936年：チューリングマシンの提示と停止性問題（アラン・チューリング）
  • 著者: Alan M. Turing
  • 論文名: On Computable Numbers, with an Application to the Entscheidungsproblem（計算可能数について、附・決定問題への応用）
  • 掲載誌: Proceedings of the London Mathematical Society, Series 2, Vol. 42, pp. 230–265 (1936年受付、1937年発行).

3. 架け橋：計算と方程式の結びつけ（1950年代〜1960年代）

• 1953年：ディオファントス集合の先駆的研究（マーティン・デーヴィス）
  • 著者: Martin Davis
  • 論文名: Arithmetical Problems and Recursively Enumerable Predicates（算術的問題と帰納的可算述語）
  • 掲載誌: Journal of Symbolic Logic, Vol. 18, No. 1, pp. 33–41 (1953).
  • ※すべての帰納的可算集合が数式（の形の1つであるガジ・プレディケート）で表せることを示し、DPRM定理への最初のレンガを敷きました。
• 1952年：指数関数の増大度の研究（ジュリア・ロビンソン）
  • 著者: Julia Robinson
  • 論文名: Existential Definability in Arithmetic（算術における存在記号による定義可能性）
  • 掲載誌: Transactions of the American Mathematical Society, Vol. 72, No. 3, pp. 437–449 (1952).
  • ※のちに「ロビンソンの仮説」と呼ばれる、指数関数を多項式で縛るための基礎理論を確立しました。
• 1961年：DPR定理の確立（デーヴィス、パトナム、ロビンソン）
  • 著者: Martin Davis, Hilary Putnam, Julia Robinson
  • 論文名: The Decision Problem for Exponential Diophantine Equations（指数ディオファントス方程式の決定問題）
  • 掲載誌: Annals of Mathematics, Second Series, Vol. 74, No. 3, pp. 425–436 (1961).
  • ※「指数関数が使えればチューリングマシンと等価である」ことを証明した、DPRMの「DPR」部分にあたる論文です。

4. 結末：最終解決（1970年）

• 1970年：マティヤセヴィチの定理 / DPRM定理の完成（ユーリ・マティヤセヴィチ）
  • 著者: Yuri V. Matiyasevich (Ю. В. Матиясевич)
  • 論文名: Диофантовость перечислимых множеств（英訳題: Enumerable sets are Diophantine ／ 和訳: 帰納的可算集合はディオファントス的である）
  • 掲載誌: Doklady Akademii Nauk SSSR, Vol. 191, pp. 279–282 (1970).
  • 英訳版: Soviet Mathematics. Doklady, Vol. 11, No. 2, pp. 354–358 (1970).
  • ※フィボナッチ数列を用いて「指数関数は多項式で表現できる」ことを証明し、ヒルベルトの第10問題を完全に否定的に解決（不可能であることを証明）した決定打の論文です。

もし「1対1対応」なら…

もし将来、宇宙がチューリングマシンと完全に1対1対応していると証明されるとしたら以下の帰結となります。

1. 宇宙のすべての物理現象（星の爆発から、あなたの脳の思考まで）は、ある巨大なディオファントス方程式の挙動に完全に翻訳できる。
2. そして、この宇宙が未来永劫どうなるか（いつか滅びるのか、永遠に続くのか）は、「やってみないとわからない（計算の既約性）」。事前に100%予言する近道は、神様にも不可能である。