Cookの定理 その6

布団が吹っ飛んだってね、へぇ

それでは、Cookの定理、手続き２の５回目です。

今回はちょっとクイック攻撃で攻めてみました。どんどんバレーボールのようになってきてますね。でも、つまんない？そうですか、もしかしたらもしかすると、そうかもしれません、へぇ。

さて、前回は、「こんな具合にして、NTMをSATに変換していくわけです。それには、つぎのG1～G6の様に書けます。ちなみにG1はここまで説明した段階iでマシンMの状態です。竹内外史先生の「PとNP」p.13から引用しましょう。」と終わりました。コピペって楽ですね、へぇ。

では、G1～G6です。G1～G5には、下に対応するSAT形式での表現も書いておきます。G6に関しては、ちょっと説明が長くなるので、これについては、次の回にします。Q[i,k],H[i,j],S[i,j,k]に関しては、Cookの定理　その4を参考にして下さい。ちなみに、そこから引用しておくと、次のようになります。

　　Q[i,k]　(0≦i≦p(n),　0≦k≦r)

　　　i番目の処理の段階でプログラムML(=現在の処理中のNTMの

　　　マシンML）は、状態qkとなるブール変数

　　　　（注：プログラムM即ちマシンMというと言うことは、

　　　　　　チューリングマシンの数理モデルの回の終わりの方で

　　　　　　軽く触れました）

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

　　　i番目の処理の段階でヘッドはテープのj番地の場所を見ている

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

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

では、NTMからSATへ変換、G1～G6です。

　　G1　：i番目の段階において、Mの状態qはただ一通りに定まる

　　　　　　{Q[i,0],Q[i,1],……,Q[i,r]}　,0≦i≦p(n)

　　　　　　{￢Q[i,j],￢Q[i,j’]}　,0≦i≦p(n), 0≦j<j’≦r

　　G2　：i番目の段階において、ヘッドは、

　　　　　テープ上のただ一つだけのデータを見ている

　　　　　{H[i,-p(n)],H[i,-p(n)+1],……,H[i,p(n)+1]}　,0≦i≦p(n)

　　　　　{￢H[i,j],￢H[i,j’]}　,0≦i≦p(n), -p(n)≦j<j’≦p(n)+1

　　G3　：i番目の段階において、テープ上の各データは、

　　　　　ただ一つだけに定まっている

　　　　　{S[i,j,0],S[i,j,1],……,S[i,j,ν]}　,0≦i≦p(n),　-p(n)≦j≦p(n)+1

　　　　　{￢S[i,j,k],￢S[i,j,k’]}　,0≦i≦p(n), -p(n)≦j<≦p(n)+1, 0≦k<k’≦ν

　　G4　：0番目の段階すなわち初めには、テープには、

　　　　　試行ヘッドによるインプットxが入っており、

　　　　　実行を始めるときである。

　　　　　(ただし、ここでは、x=sk1sk2…sknとする場合)

　　　　　{Q[0,0]},{H[0,1]},{S[0,0,0]},

　　　　　{S[0,1,k1]},{S[0,2,k2]},…,{S[0,n,kn]}

　　　　　{S[0,n+1,0]},{S[0,n+2,0]},…,{S[0,p(n)+1,0]},

　　　　　{S[0,-1,0]},{S[0,-2,0]},…,{S[0,-p(n),0]}

　　　　　{S[0,j,k]}の部分を説明しておくと、

　　　　　　0≦j≦nでは、xが入っており

　　　　　　その他の部分は空白が入っている、

　　　　　という意味です。

　　　　　　（s0=bということをCookの定理　その3の終わりの方で

　　　　　　　説明しています。参考にしてみて下さい）

　　　　　H[0,1]となっているのは、入力xが、

　　　　　テープの１番目から始まるためです

　　G5　：p(n)番目の段階にではMはqyの状態でxが受容されている

　　　　　{Q[P(n),1]}

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

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

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

　　　　　によって決定される　　　

ということになります。

今回は以上です。次回はG6をSAT形式で表現するにはどうするかについて説明します。

それでは。

隣の客は良く柿食う客なんだってねぇ、へぇ。