Aritalab:Lecture/Algorithm/Halting Problem

Revision as of 11:46, 26 October 2011

問題を解くということ

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

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

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

チューリング機械が "解ける" 問題の範囲とはどのようなものでしょう。ここでは

• 任意のプログラムが無限ループを含むかどうか　（停止性問題）
• 文字列が上下に 1 対記されたカードを与えられた時、重複を許して並べることで上側の文字列と下側の文字列を一致させることができるか （ポストの対応問題）

が、理論的に "解けない" 問題である事を示します。

停止性問題

チューリング機械（＝プログラム） 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' に対して停止しなくてはなりません。やはり矛盾になります。^[1]

ポストの対応問題

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

ポストの対応問題

あるアルファベット Σ からなる語 k 対 に対し、重複を許して並べることで上側と下側に同じ文字列 を作れるか。

例

{ 0, 1 } ∈ Σ は解をもつか。

解は存在し、

例

{ 0, 1 } ∈ Σ は解をもつか。

解は存在しない

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

停止性問題の変換

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

状態遷移関数は有限個用意され、 δ: (Q - {q_Y, q_N}) × Γ → Q × Γ × {−1, +1} と書けます（チューリングマシン参照)。まず、初期状態およびヘッドが左に動く場合と右に動く場合に対応する対を作成します。

表現する状態	用意する記号対	説明
初期状態 q0 で入力が a1a2 ... an		ここで # は様相を区切る記号です。q0 という状態記号でヘッドの位置を示しており、ヘッドの右側に入力 a1 ... an があることを示しています。
δ(q, x) = (r, y, +1)	x, y ∈ Γ q, r ∈ Q - {qY, qN}	状態 q でヘッドの右側に記号 x があるとき、 x を y に上書きして状態 r に移動、ヘッドは右に移動して y の左側に来ることを意味しています。この対は、ヘッドを右に動かす遷移関数 1 個につき、1 個用意します。
δ(q, x) = (r, y, −1)	x, y, z ∈ Γ q, r ∈ Q - {qY, qN}	状態 q でヘッドの左側に記号 z 右側に記号 x があるとき、 x を y に上書きして状態 r に移動、ヘッドは左に移動して z の左側に来ることを意味しています。記号 z は状態 q のとき、ヘッドの左側にあるテープ記号を意味します。よってヘッドを左に動かす遷移関数 1 個につき、Σ 個用意しておきます。
ヘッド周辺以外のテープ内容の対応づけ	(x ∈ Γ)	全てのテープ記号について ( Σ 個) 用意します
様相の区切り		2 個用意します
受理後の調整用		受理後の文字列を合わせるために使います

様相の列との対応付けは具体例を用いておこなった方がわかりやすいので、チューリングマシンの入力が 101 と仮定した状態遷移との対応付けを以下に記します。チューリングマシンは 101 を右に読んで 010 に書き換え、今度は左に動きながら 1 だけ 0 に書き戻して 000 という記号列を作って受理する動作を仮定します。

結果として、以下のことがわかりました。

• チューリングマシンが任意の入力に対して受理するか否かという問題は、ポストの対応問題の部分問題になっている。
• ポストの対応問題を解くプログラムがあるなら、チューリングマシンの停止性問題が解けてしまう。

参考

1. ↑ 矛盾の導出には、あらゆるプログラムを自然数と1:1に対応付けるゲーデル数という概念を用いており、カントールの対角線論法と同じ議論になっています。