Cookの定理 その4

それでは、Cookの定理、手順2の続きです。

その前に、鈴木先生、根岸先生　ノーベル賞受賞おめでとうございます。先生方に力を頂いてこのブログも復活です。

さて、とぼけた持ち味でおそらくノーベル賞受賞の先生方もしかしたら読んでおられて、なおかつ、もしかしてもしかするとご好評頂いているかも知れないこのブログですが、まず、リラックスしましょう。ラジオ体操第二ぃよぉぃ。えぇ、はしゃぎすぎですね、はい。すいません。だって根岸先生、朝のTV番組で、化学は陽子と電子と中性子の組み合わせでものを考えるんだなどと仰ってたから、つい（笑い）

さて、前回、状態遷移の記述をするための準備として、SATの節がいろいろな状態やデータに１対１で対応している（節の中の各元のブール変数は原則そのうちの一つしかTの値を取らないので）ということを説明しました。今回は、NTMのいろいろな状態を表わすブール変数について説明します。

NTMの状態を表わすブール変数を以下のように定義します。

　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である

こうやって状態遷移に関するブール変数をようやく導入できました。プログラムMLはこのブール変数の真理値を満たします。当たり前ですが。何が言いたいかというと、プログラムMLがyesかnoを出すというのは、言語Lに対する真理関数（クラスPの問題とチューリングマシン　その１の決定問題の部分を参照して下さい）があるとして、その真理関数は、計算の途中で、 Q[i,k],H[i,j],S[i,j,k]に対して真理値を与えますよね、ということです。適正な真理関数はプログラムMLでの計算を満たす、すなわち、計算の途中ですべての Q[i,k],H[i,j],S[i,j,k]に対して真理値を与えるはずだよね、ということです。（この辺の話は、竹内外史先生のPとNPのｐ.12に書かれています。というよりこの記事自体そこを参照しています）

もう一つ言っておくとプログラムMLの計算は最高でp(n)回行われます。それ以前に終わることも当然ある訳なので、その場合は、 Q[i,k],H[i,j],S[i,j,k]は答えが出たと同じ状態とします。SATに変換するための便宜上です。

では、どうやってSATにしていくのか。それは次回で。

でも、ちょっとだけ書いておくと、ある段階iでマシンMの状態が決まってるとしたときつまり、i番目の処理の時、マシンMの状態がquとなるuが存在して、それは以下のような集合のSATとして表わされると言うことになります。詳細は次回で説明しますが、とりあえず見といてね。

　　{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

これはある状態iの時に成り立つ、って事ですからね、念のため。