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' に対して停止しなくてはなりません。やはり矛盾になります。

ポストの対応問題

無限ループを含むか否かをあらゆるプログラムについて判定できるという停止性問題は、直感的にも大変難しいように思えます。しかし、以下に述べる簡単な問題が、少なくとも停止性問題と同等に難しいことを示せます。

ポストの対応問題

あるアルファベット Σ からなる語 k 対 $\textstyle \{ \frac{x_1}{y_1}, \frac{x_2}{y_2}, ... , \frac{x_k}{y_k} \} \ (x_i, y_i \in \Sigma^*)$ に対し、重複を許して並べることで上側と下側に同じ文字列 $x_{i_1}, x_{i_2}, ... , x_{i_n} = y_{i_1}, y_{i_2}, ... , y_{i_n} \ (1 \leq i_1, i_2, ... i_n \leq k)$ を作れるか。

例

{ 0, 1 } ∈ Σ $\textstyle \{ \frac{00}{0}, \frac{01}{010}, \frac{11}{011} \}$ は解をもつか。

解は存在し、$\textstyle \frac{01}{010} \frac{00}{0} \frac{00}{0} \frac{11}{011}$

例

{ 0, 1 } ∈ Σ $\textstyle \{ \frac{0}{01}, \frac{101}{011}, \frac{111}{10} \}$ は解をもつか。

解は存在しない

この問題を解くアルゴリズムは存在しません。つまり、どのようなリスト対を与えられても解があるなら YES と答えられるプログラムは存在しません。もし存在すると仮定すると、 停止性問題が解けてしまうことを利用します。

停止性問題の変換

チューリングマシン T が入力 x を受理する際の様相の列 (q₀, ε, x) ⇒...⇒ (q_f, y, z) が存在するときに限って、その列を解に持つような対応問題を構成できることを示します。それには、マシン T の状態遷移関数を表現する記号対を作れば十分です。

参考