解決不可能な問題

計算可能性理論と計算複雑性理論において、決定不能問題とは、常に正しい「はい」か「いいえ」の答えを導くアルゴリズムを構築することが不可能であることが証明されている決定問題である。停止問題はその一例であり、任意のプログラムを実行したときに最終的に停止するかどうかを正しく決定するアルゴリズムは存在しないことが証明されている。^[1]

決定問題とは、無限の入力集合内の各入力に対して「はい」または「いいえ」で答える質問です。^{[2]これらの入力は数値（たとえば、「入力は素数ですか？」という決定問題）または}形式言語の文字列など、他の種類の値である可能性があります。

決定問題の形式的表現は、自然数のサブセットです。自然数に関する決定問題の場合、セットは決定問題が「はい」と答える数で構成されます。たとえば、「入力は偶数か?」という決定問題は、偶数のセットとして形式化されます。入力が文字列またはより複雑な値で構成される決定問題は、特定のゲーデル番号付けを介して、決定問題の基準を満たす入力に対応する数のセットとして形式化されます。

決定問題Aは、 Aの形式化された集合が再帰集合である場合に決定可能または実質的に解決可能であると呼ばれます。そうでない場合、Aは決定不可能と呼ばれます。 A が再帰的に可算な集合である場合、問題は部分的に決定可能、半決定可能、解決可能、または証明可能であると呼ばれます。^{[注 1]}

計算可能性理論では、停止問題は次のように述べることができる 決定問題です。

任意のプログラムの説明と有限の入力が与えられた場合、プログラムの実行が終了するか、永久に実行されるかを決定します。

アラン・チューリングは1936 年に、チューリング マシン上で実行され、すべての可能なプログラムと入力のペアの停止問題を解決する一般的なアルゴリズムは必然的に存在し得ないことを証明しました。したがって、停止問題はチューリング マシンにとって 決定不可能です。

ゲーデルの不完全性定理によって提起された概念は、停止問題によって提起された概念と非常に似ており、証明もかなり似ています。実際、第一不完全性定理の弱い形式は、停止問題の決定不能性の簡単な帰結です。この弱い形式は、完全かつ健全な自然数の公理化は不可能であると主張する点で、不完全性定理の標準的な記述とは異なります。「健全」な部分が弱められた部分です。つまり、問題の公理体系は、自然数に関する真の記述のみを証明することを要求するということです。健全性は一貫性を意味するので、この弱い形式は強い形式の帰結と見なすことができます。ゲーデルの第一不完全性定理の標準形式の記述は、記述の真理値にはまったく関係がなく、数学的証明を通じてそれを見つけることができるかどうかという問題にのみ関係していることに留意することが重要です。

定理の弱い形式は、停止問題の決定不能性から次のように証明できます。^[3]自然数に関するすべての真の一階論理ステートメントの健全な（したがって一貫性のある）完全な公理化があると仮定します。次に、これらすべてのステートメントを列挙するアルゴリズムを構築できます。これは、自然数nが与えられたときに自然数に関する真の一階論理ステートメントを計算するアルゴリズムN ( n )が存在し、すべての真のステートメントに対して、 N ( n ) がそのステートメントを生成するnが少なくとも 1 つ存在することを意味します。ここで、表現 a を持つアルゴリズムが入力iで停止するかどうかを決定したいとします。このステートメントは、たとえばH ( a , i )などの一階論理ステートメントで表現できることがわかっています。公理化は完全であるため、N ( n ) = H ( a、i )となるnが存在するか、 N ( n ′ ) = ¬ H ( a、i ) となるn ′が存在することになります。したがって、H ( a、i ) またはその否定が見つかるまですべてのnを反復すると、常に停止し、さらに、得られる答えは真になります (健全性により)。つまり、これにより停止問題を決定するアルゴリズムが得られます。このようなアルゴリズムは存在できないことがわかっているため、自然数に関するすべての真の一階論理ステートメントの一貫した完全な公理化が存在するという仮定は偽でなければなりません。

決定不能問題は、論理、抽象マシン、トポロジーなど、さまざまなトピックに関連している可能性があります。決定不能問題は無数に存在するため、^{[注 2]任意のリストは、}無限の長さのリストであっても、必然的に不完全です。

現代では、「決定不能」という言葉には 2 つの明確な意味があります。1 つ目は、ゲーデルの定理に関連して使用される意味であり、指定された演繹システムで証明も反証もできないステートメントを指します。2 つ目の意味は、計算可能性理論に関連して使用され、ステートメントではなく、それぞれが「はい」または「いいえ」で答える必要がある質問の可算無限セットである決定問題に適用されます。問題セット内のすべての質問に正しく答える計算可能な関数がない場合、そのような問題は決定不能であると言われます。これら 2 つの関係は、決定問題が (再帰理論の意味で) 決定不能である場合、問題内のすべての質問Aに対して「 Aへの答えははいである」または「A への答えはいいえである」のいずれかを証明する、一貫性のある効果的な形式システムが存在しないという点です。

決定不能という単語には 2 つの意味があるため、 「証明も反駁もできない」という意味で、決定不能ではなく独立という用語が使用されることがあります。ただし、「独立」の使用法も曖昧です。単に「証明できない」という意味になることもあり、独立ステートメントが反駁されるかどうかは不明のままです。

特定の演繹体系における文の決定不能性は、それ自体では、文の真理値が明確に定義されているかどうか、または他の手段で決定できるかどうかという問題には対処しません。決定不能性とは、検討中の特定の演繹体系が文の真偽を証明しないことを意味するだけです。真理値が決して分からない、または明確に定義されていない、いわゆる「絶対的に決定不能な」文が存在するかどうかは、さまざまな哲学学派の間で議論の的となっています。

2番目の意味で決定不可能であると疑われた最初の問題の一つは、1911年にマックス・デーンが初めて提起した群に関する単語問題であり、これは2つの単語が等しいかどうかを判定するアルゴリズムが存在しない有限に提示された群が存在するかどうかを問うものである。これは1955年にその通りであることが示された。^[4]

ゲーデルとポール・コーエンの共同研究により、決定不可能な命題（最初の意味で）の具体的な例が2つ示されている。連続体仮説はZFC （集合論の標準的な公理化）では証明も反証もできず、選択公理はZF （選択公理を除くすべてのZFC公理）では証明も反証もできない。これらの結果には不完全性定理は不要である。ゲーデルは1940年に、これらの命題はどちらもZFやZFC集合論では反証できないことを証明した。1960年代にコーエンは、どちらもZFからは証明できず、連続体仮説はZFCから証明できないことを証明した。

1970年、ロシアの数学者ユーリ・マティヤセビッチは、1900年に次の世紀の数学者への挑戦として提起されたヒルベルトの第10問題が解けないことを示した。ヒルベルトの挑戦は、ディオファントス方程式のすべての解を求めるアルゴリズムを求めた。ディオファントス方程式はフェルマーの最終定理のより一般的なケースであり、整数係数を持つ任意の数の変数の多項式の整数根を求める。方程式は1つしかないが変数はn個なので、複素平面には無限の解が存在する（そして簡単に見つけられる）。しかし、解が整数値のみに制限されると、問題は不可能になる。マティヤセビッチは、ディオファントス方程式を再帰的に可算な集合にマッピングし、ゲーデルの不完全性定理を適用することで、この問題が解けないことを示した。^[5]

1936 年、アラン・チューリングは、停止問題(チューリング マシンが特定のプログラムで停止するかどうかという問題) が、用語の 2 番目の意味で決定不可能であることを証明しました。この結果は、後にライスの定理によって一般化されました。

1973年、サハロン・シェラは群論におけるホワイトヘッド問題が、標準的な集合論では、その言葉の最初の意味で決定不可能であることを示した。 ^[6]

1977年、パリスとハリントンは、ラムゼー定理の一種であるパリス・ハリントン原理が、ペアノ公理によって与えられた算術の公理化においては決定不可能であるが、より大規模な二次算術システムにおいては真であることが証明できることを証明した。

コンピュータサイエンスに応用されているクラスカルの木定理も、ペアノの公理からは決定不可能ですが、集合論では証明可能です。実際、クラスカルの木定理（またはその有限形式）は、述語主義と呼ばれる数学の哲学に基づいて受け入れられる原理をコード化した、はるかに強力なシステムでは決定不可能です。

グッドスタインの定理は、カービーとパリスがペアノ算術では決定不可能であることを示した自然数の ラムゼー理論に関する声明です。

グレゴリー・チャイティンは、アルゴリズム情報理論において決定不能な命題を提示し、その設定で別の不完全性定理を証明した。チャイティンの定理は、十分な算術を表現できる理論には上限cがあり、その理論では特定の数がcよりも大きいコルモゴロフ複雑度を持つことが証明できないことを述べている。ゲーデルの定理は嘘つきのパラドックスに関連しているが、チャイティンの結果はベリーのパラドックスに関連している。

2007年、研究者のカーツとサイモンは、1970年代のJHコンウェイによる以前の研究を基に、コラッツ問題の自然な一般化は決定不可能であることを証明した。^[7]

2019年にベン・デイビッドとその同僚は学習モデル（EMXと名付けられた）の例を構築し、EMXにおける学習可能性が標準的な集合論では決定できない関数の族を示しました。^{[8] [9]}

• 決定可能性（論理）
• 結論問題
• 不可能の証明
• 不可知性
• 厄介な問題