Aritalab:Lecture/Algorithm/Halting Problem

問題を解くということ

チューリング機械（＝プログラム）が "問題を解ける" ためには、全ての可能な入力に対して

• 必ず停止する（無限ループに陥らない）
• 必ず正しい答えをだす

ことが要求されます。例えば、階乗を計算するプログラムがあったとして、入力する値によって無限ループに陥ったり、計算結果が間違っている可能性があるとしたら、皆さんもプログラムは "バグがある" と思うでしょう。

停止性問題

チューリング機械（＝アルゴリズム） T に任意の入力 x を入れたとき有限時間で停止するか、を判定する問題。この問題を解くアルゴリズムは存在しない、つまり解くことができません。もし停止性を判定できる万能なチューリング機械が存在すると仮定すると、それが停止すると判定した時に無限ループをおこなう別のチューリング機械を簡単に設計できてしまい、矛盾が生じます。

導かれる事例

• プログラムが無限ループを含むか判定できるコンパイラやデバッガは作れない
• いかなるアルゴリズムをもってしても解けない問題が存在する

矛盾の導き方

任意のプログラム P と入力 x を受け取って、P が止まるか否かを有限時間で YES/NO と答えられるプログラム C(P, x) があると仮定します。（C をコンパイラと考えると分かりやすい。）C は必ず有限時間で止まり、C(P, P) という入力（つまりプログラム P 自身を数値に置き換えて入力にしてしまう）に対しても YES/NO と答えます。ここで、このコンパイラ C のプログラムに細工をして、C(P, P) が YES なら無限ループさせ、C(P, P) が NO なら YES と出力して停止する C' を作成します。この新しいコンパイラ C' に C' 自身を数値に置き換えた値を入力するとどうなるでしょうか。

• C'(C', C') が停止する場合

C(C', C') が NO となるため、プログラム C' は 入力 C' に対して停止しないことになります。ですから、C'(C', C') が停止するのは矛盾です。

• C'(C', C') が停止しない場合

C(C', C') が YES となるため、`プログラム C' は入力 C' に対して停止しなくてはなりません。やはり矛盾になります。

参考