布団が吹っ飛んだってね、へぇ
それでは、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が入っており
その他の部分は空白が入っている、
という意味です。
説明しています。参考にしてみて下さい）
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形式で表現するにはどうするかについて説明します。
それでは。
隣の客は良く柿食う客なんだってねぇ、へぇ。
