計算状況とSATのNP完全性の証明における窓について(第11・12回スライド参照)

こんにちは。いつぞやに計算状況の記事を書きましたが、その定義を使って窓について考えると「んん・・・？」ってなります。私がなりました。そこで今回は、窓の書き方に合わせた計算状況を導入した後、合法な窓と非合法な窓について例示していきます。

 第2回スライドの説明記事で紹介した計算状況の定義では、現在の状態とテープ記号列およびヘッド位置の添え字を別々に記録していました。今回はそれをせず、状態およびヘッド位置をテープ記号列の中に組み込んでしまいます。例えばこんな感じに。

上図のように、現在の状態を示す記号の右側が現在のヘッドの位置となっています。

さて、これを基に窓について考えてみましょう。ある行とその下の行の関係は、現在の計算状況とその次の計算状況という関係です。したがって、下図に示す次動作関数に従ったTMを考えると、図のように合法窓と非合法窓が分けられます。

合法窓と非合法窓の例

 順番が前後し、かつ急ぎになりますが某競プロerの彼から質問を頂き緊急だと思いましたので何卒ご容赦ください。次回は決定性のお話をして、その後余裕があればPとNPについて書きます。