停止問題と決定不能性

与えられたプログラムが与えられた入力に対して停止するかどうかを決定する停止問題は、アルゴリズム的に決定不能な問題の典型例であり、これからの帰着によって他の多くの問題の決定不能性が証明されます。

Definition

決定問題は、すべての入力に対してチューリングマシンがそれを正しく決定できない場合、決定不能であるとされます。停止問題は、任意の機械が任意の入力に対して停止するかどうかを問い、他の問題が帰着によって決定不能であることを示すための典型的な決定不能問題です。

Scope

このトピックでは、停止問題の正確な記述、対角線論法によるその決定不能性の証明、決定不能性を転送するための多対一帰着のテクニック、プログラムの非自明な特性に関するライス​​の定理、およびEntscheidungsproblemや群の語の問題などの古典的な決定不能な問題について扱います。

Core questions

• プログラムが停止するかどうかを決定するアルゴリズムが存在しないのはなぜですか？
• ある問題から別の問題の決定不能性を証明するために、帰着はどのように使用されますか？
• プログラムの特性を決定することについて、ライスの定理は何を述べていますか？
• どの有名な数学的問題が決定不能であることが判明しましたか？

Key theories

停止問題の非可解性

対角線論法は、停止判定器を仮定すると矛盾が生じることを示しており、したがって、すべてのプログラムと入力に対して停止を決定できるアルゴリズムは存在しません。

帰着と決定不能性の転送

既知の決定不能な問題が対象の問題に帰着される場合、対象も決定不能であり、帰着は決定不能性を確立するための標準的なツールとなります。

ライスの定理

プログラムによって計算される関数の非自明な特性はすべて決定不能であるため、プログラムの本質的に興味深い振る舞いの特性はアルゴリズム的に決定できません。

Clinical relevance

決定不能性の結果は、自動推論とプログラム解析における厳密な限界を確立します。これらは、終了やプログラムの特性を検証するための完璧な汎用ツールは存在し得ないことを示し、論理学、代数学、数論における多くの問題がアルゴリズム的な解決策を持たない理由を説明します。

History

チューリングとチャーチは1936年に、一階述語論理の妥当性を決定するアルゴリズムの問いであるEntscheidungsproblemが解決不能であることを示しました。チューリングの議論の中心には停止問題がありました。ライスは1953年にこの現象を一般化し、その後、ノビコフによる群の語の問題やマチャセビッチによるヒルベルトの第10問題など、具体的な問題に対して決定不能性が確立されました。

Key figures

• Alan Turing
• Alonzo Church
• Henry Gordon Rice
• Pyotr Novikov

Seminal works

• sipser2013
• turing1936
• rogers1987

Frequently asked questions

なぜより高速なコンピュータでも停止問題を解決できないのですか？

決定不能性は速度やメモリとは無関係です。対角線論法は、与えられた時間に関係なく、いかなるアルゴリズムも排除します。停止問題は、単に非実用的なだけでなく、原理的に解決不能です。

プログラムが停止するかどうかを判断することはできますか？

特定のプログラムについては、解析や実行によってしばしば可能です。不可能なのは、すべてのプログラムと入力に対して質問に正しく答える単一のアルゴリズムです。したがって、実用的な終了チェッカーは、制限されたクラスでのみ成功するか、または答えを出すことができない場合があります。