Cookの定理 その7

それでは、Cookの定理、手順2の6回目です。

カニは静かに

今回は、今日テレビで見た駄洒落をぱくりました。白いワニが見える（(c)江口寿史）

おっほん。さて、静かになったところで、そろそろCookの定理の説明も大詰めです。前回はNTMをSATに変換するためにはG1～G6を行えば良いということと、そのうちG1～G５にあたっては具体的なSAT形式を説明しました。

今回はG6のSAT形式での表現を説明します。まず、G6を再掲しましょう

　　G6　：i番目の段階(ただし、0≦i<p(n))において,

　　　　　マシンMLのi+1番目の状態は、

　　　　　i番目の状態からチューリングマシンの状態遷移関数δ

　　　　　によって決定される　　　

でした。

チューリングマシンの状態遷移関数δにかんしては、NTMの数理モデルとクラスPとNPの違いの回を参照して下さい。

最初に一番ややこしいところを説明しましょう。

実は、G6をSATに変換するときに一番ややこしいのは、ヘッドのないところのテープの状態は、次もそのままであるという、われわれにとっては一番当たり前に思えるところだったりします。

テープの番地は以下のブール変数で表せるのでした。

　　S[i,j,k]　（0≦i≦p(n),　-p(n)≦j≦p(n)+1,　0≦k≦ν）

　　　i番目の処理の段階でテープのj番地のデータはskである

そういうわけで、i番目にヘッドのないテープの番地kのデータlは、i+1番目もそのままである、というのをちょっと考えてみてみましょう。

われわれがいきなりSAT形式で考えるのは難しいので、比較的考えやすい論理式から入ることにしましょう。自分で考えたい人は、ここからしばらくは飛ばしても良いと思います。

では、まず、i番目にテープの番地kにヘッドがないというブール変数を考えます。これは簡単で、

¬H[i,k]

がTになればいいのですね。

つぎにi番目のテープの番地kのデータlは、i+1番目もそのままであると言うのは、次のように表わします。

S[i,k,l]⇒S[i+1,k,l]　（S[i,k,l]ならばS[i+1,k,l]）

これは、次のような式に置換されると言うことが分かっています。

S[i,k,l]⇒S[i+1,k,l]＝￢S[i,k,l]∨S[i+1,k,l]

真理値表をつけておきましょうか。

　　　　　　

と、なります。こういう定義なので、こういうもんだと思って下さい。つまり、AがTならばBを判定しますが、AがFであれば、この式事態は、判定せずにTとしておくという意味になります。こういう定義です。まぁ、AがFであればこの式はFとしてもいいのですが、たくさんの計算が必要な論理式においてTにしておいた方が計算がうまくいくようです。納得いかない方はネットで調べてみて下さい。分かりやすく説明してあるところがあります。これは、ある種の経験則といって良いでしょう。わたしも、大学の卒業論文でプロダクションシステムというのをやったので、だいぶこの論理式にはお世話になったのですが、確かにこれで問題はありませんでした。

さて、まとめましょう。

¬H[i,k]⇒(S[i,k,l]⇒S[i+1,k,l])

という三段論法の論理式で表わされるわけですね。変形していくと、

¬H[i,k]⇒(S[i,k,l]⇒S[i+1,k,l])＝H[i,k]∨(S[i,k,l]⇒S[i+1,k,l])

＝H[i,k]∨(￢S[i,k,l]∨S[i+1,k,l])

最後の式は括弧をとっても問題ないので、最終的に、i番目にヘッドのないテープの番地kのデータlは、i+1番目もそのままである、という事はつぎのSATの表現で表わされることになります

{H[i,k],￢S[i,k,l],S[i+1,k,l]}

というわけです。われわれにとって一番簡単にみえることががけっこう難しいという変な感じですが、まぁこういうことです。

今回はカニもAB（エビ）もでてきたというわけで、お後がよろしいようで。

という論理式を最後に書いて終わります（笑い）