Entscheidungs Problem｜決定問題

① ダフィット・ヒルベルト（David Hilbert）の出生地

• ケーニヒスベルク（Königsberg、現在のロシア・カリーニングラード）

② ヒルベルトによる「決定問題（Entscheidungsproblem）」の提起（発表場所）

• ボローニャ（Bologna、イタリア）
  1928年にイタリア・ボローニャで開催された国際数学者会議（International Congress of Mathematicians, ICM）において、この問題を初めて正式に提起しました。

Entscheidungsproblem（決定問題）とは、ドイツ語で「決定問題」を意味し、数学者ダフィット・ヒルベルトが1928年に提起した数学的課題です。その本質は、次のような問いです：

「与えられた任意の数学的命題が、機械的かつ有限の手順で、それが真か偽かを常に決定できるような方法（アルゴリズム）が存在するか？」

つまり、あらゆる数学的な問題を自動的に「解ける」一般的な手法があるかどうかを問う問題でした。

チューリングによる証明（否定的解決）

③ アラン・チューリング（Alan Turing）による決定問題の否定的証明（発表場所）

アラン・チューリング（Alan Turing） は、1912年にイギリスの ロンドン（London） で生まれました。

• ケンブリッジ（Cambridge、イギリス）
  1936年、チューリングはケンブリッジ大学において、決定問題が一般には解決不可能であることを証明しました。この論文は『On Computable Numbers』として発表されています。

アラン・チューリングは1936年、論文『計算可能数とその決定問題への応用（On Computable Numbers, with an Application to the Entscheidungsproblem）』において、この問題を否定的に解決しました。彼の主な業績は以下の通りです：

1. チューリングマシンの提唱
   • チューリングは、「計算とは何か？」という本質的な問いを明確化するため、「チューリングマシン」という抽象的な計算モデルを提案しました。
   • このモデルは、現代のコンピュータの理論的基盤となりました。
2. 決定不可能性の証明
   • チューリングは、このチューリングマシンの概念を用いて、任意の数学的命題について真偽を判定するような汎用アルゴリズムが存在しないことを証明しました。
   • 具体的には、停止性問題（Halting Problem）という「あるチューリングマシンが特定の入力に対して計算を停止するかどうかを機械的に判定する問題」が解けないことを示しました。

つまり、チューリングは、

• 「すべての数学的問題を機械的に判定できる」という夢のような手法は原理的に存在しないことを明らかにしました。

意義と現代への影響

チューリングのEntscheidungsproblemに対する否定的な解決は、

• 「数学には原理的に計算不可能な問題が存在する」
• 「コンピュータにも本質的な限界がある」

という現代コンピュータ科学の重要な基盤を作りました。

その後の計算理論、複雑性理論、さらには人工知能研究にまで影響を与え、チューリングの証明は今なお、理論計算機科学の根幹をなす理論の一つとして位置づけられています。

まとめ