Aritalab:Lecture/Algorithm/Halting Problem

問題を解くということ

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

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

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

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

• 任意のプログラムが無限ループを含むかどうか　（停止性問題）
• 文字列が上下に 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') は YES 、プログラム C' に入力 C' を入れると停止することになる。しかし、これはC'(C') が停止しない場合という仮定と矛盾。

つまり前提が間違っており、停止性を判定できるプログラム C(P, x) は存在しないことになります。

ポストの対応問題

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

ポストの対応問題

あるアルファベット Σ からなる語 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} \}$ は解をもつか。

解は存在しない。左端になれる対は $\textstyle \frac{0}{01}$ しかなく、その後は $\textstyle \frac{101}{011}$ しか繋げられないため

いかなる文字列の対を用意されても、解の有無を判定できるアルゴリズム（計算機プログラム）は存在しないことが理論的に証明できてしまいます。つまり、どのような文字列の対与えられても解があるときに YES と答えられるプログラムは（どんなに時間のかかるアルゴリズムを許したとしても）存在しません。もし存在すると仮定すると、 停止性問題が解けてしまうことを利用します。

停止性問題の変換

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

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

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

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

TM の動作	記号対	解説
初期状態 q0	# #q0101#
δ(q0, 1) → (q1, 0, +1)	#q01 #q0101#0q1	テープ記号 1 を読んで 0 を書き込み、状態 q1 に移動します。(q01/0q1)を用います
	#q0101# #q0101#0q101#	その後、区切り記号 # まで (0/0), (1/1), (#/#) を用いて入力列を補完します
δ(q1, 0) → (q5, 1, +1)	#q0101#0q10 #q0101#0q101#01q5	(0/0)で補完したあと、(q10/1q5)を用いて状態遷移します
	#q0101#0q101#0 #q0101#0q101#01q51#0	ヘッドの左側まで入力列を補完します
δ(q5, 1) → (q3, 0, -1)	#q0101#0q101#01q51 #q0101#0q101#01q51#0q310	テープ記号 1 を読んで 0 を書き込み、ヘッドを左に移動します。(1q51/q310) を使います
δ(q3, 1) → (q3, 0, -1)	#q0101#0q101#01q51#0q31 #q0101#0q101#01q51#0q310#1q300	テープ記号 1 を読んで 0 を書き込み、ヘッドを左に移動します。(0q31/q300) を使います
	#q0101#0q101#01q51#0q310# #q0101#0q101#01q51#0q310#q3000#	補完します
δ(q3, 0) → (qYES, 0, +1)	#q0101#0q101#01q51#0q310#q30 #q0101#0q101#01q51#0q310#q3000#0qYES	受理します
	#q0101#0q101#01q51#0q310#q3000#0qYES #q0101#0q101#01q51#0q310#q3000#0qYES00#qYES	補完したあとに、受理後の調整用文字対を使って、少しずつ上下のつじつまを合わせます
	#q0101#0q101#01q51#0q310#q3000#0qYES00#qYES00#qYES0# #q0101#0q101#01q51#0q310#q3000#0qYES00#qYES00#qYES0#qYES#	一番最後に (qYES##/#) という文字対を加えれば、上下の文字列が一致します。お疲れ様でした

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

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

参考