1 2. チューリング機械の拡張 2 チューリング機械の拡張 標準 TM (1テープ1ヘッドTM) の拡張 標準 TMに段階的に機能を拡張する. 拡張したTMは標準 TMより高い能力を持つか? 結論 : 機能を拡張したTMの言語受理能力は標準のTMと同じ 標準 TMと拡張したTMが言語受理能力において等価であることを示す. ある言語 ( 問題 ) が決定可能 / 半決定可能かどうかを証明する際に, 機能を拡張した TM が使えるようになる (TMによるプログラミングが簡単化グが簡単化 ). 1
3 拡張する機能と等価性の証明法 拡張する機能 多重トラック 複数のテープ 非決定性 機械語命令 ( 算術演算, 条件分岐等 ), ランダムアクセスメモリ ( 付録 B) 等価性の証明 2 つのマシンが等価 言語受理能力が同じ, と定義する. 各機能を拡張した TM が, 標準 TM で模倣できること, およびその逆を示す. 証明のための TM の動作は抽象レベルで説明する. 4 多重トラックテープを持つ TM テープの各セルが k ( 2) 個のトラックに分割された TM M 1 3トラックテープを持つ TM M 1 $ 0 1 0... $ 1 1 0 1... $ 1 0 0 0... q 有限制御部 TM M 1 k トラック ΤΜ Μ 1 の定義 テープの各セルが k 個のマスに分かれている. 入力アルファベットの Σ={0,1}: 入力 w Σ は 1 番目のトラックに置かれる ( 他は空白 ) テープ記号 Γ ={0,1,, $}: 各記号は各トラックのセルで使用 遷移関数 δ(q, (x,y,z))=(r,(x,y,z ), D): テープ記号の組 (x,y,z) を読み込んで, 新しい記号の組 (x, y, z ) を書き込み, ヘッドを右または左に移動 (D {L,R}). 2
定理 2.1: 多重トラック TM は標準 TM と等価 5 ( 証明 )k トラック TM M 1 を標準 TM M 2 で模倣できることを示す. 3 トラックテープ M 1 $ 0 1 0... $ 1 1 0 1... $ 1 0 0 0... q 有限制御部 TM M 1 標準 ΤΜ Μ 2 を以下のように構成する. 標準 1テープTM M 2 一つの記号とみなす [$,$,$] [0, 1, ] [1, 1, 1]... q 有限制御部 TM M 2 テープ記号 :Γ 2 = Γ Γ Γ= {[0,0,0],[0,0,1],...,[1,1,1],...,[,, ],..., [$,$,$]} 遷移関数 :δ 2 (q, [x,y,z])=(r, [x,y,z ], D) M 2 が 3 トラック TM M 1 を模倣できることは明らか.k トラック TM についても同様にそれを模倣する標準 TM が構成できる. 逆に k トラック TM が 1 テープ TM を模倣できることは明らか. 多重トラック TM と 1 テープ TM は等価. 複数のテープを持つ TM 6 k 本のテープとk 個のヘッドを持つTM M 1 の定義 入力 w Σ * は1 本目のテープ上に置かれる. 2 本目以降のテープの内容は最初は空白文字で初期化されている. 全てのヘッドで文字を読み取り, 記号の組と現在の状態から, 各テープ上において, 文字の書換およびヘッドの移動 ( 右 / 左 / 静止 ) を行う. kテープtmの遷移 δ(q, x 1,,x k )=(r, x 1,,x k, D 1,..., D k ) x i, x j Γ, D l {L, R, S} (1 i, j, l k) q r x 1,,x k /x 1,,x k, (D 1,..., D k ) 状態遷移図における記法 ヘッドの静止も可 テープ 1 テープ 2 テープ 3 3テープチューリング機械 $ 0 1 0... $ 1 1 0 1... $ 1 0 0 0... q 有限制御部 3
定理 2.2: k テープ TM と標準 TM は等価 有限制御部に, q (a,b,a) のような状態を持たせることで読んだ 1 回の遷移を以下のステップで実行文字を区別 (1) テープ上で全ての が左側にくる位置に M 2 のヘッドを移動 (2) 左にヘッドを移動しながら, 各テープのヘッド上の文字を読み込む (3) 右にヘッドを移動しながら, 遷移関数どおりに各テープの記号を書換え, ヘッドを移動 以上により,2kトラックTMがkテープTMを模倣可能であることがわかる. 一方,kテープTMが標準 TMを模倣可能であることは明らか. 以上の議論および定理 2.1より,kテープTMと標準 TMは等価. ( 証明 )k テープ TM M 1 を 2k トラック TM M 2 で模倣する. 7 テープ 1 $ 0 1 0... を模倣 *... テープ2 $ 1 1 0 1... を模倣 *... テープ3 $ 1 0 0 0... を模倣 *... M 2 のヘッド ヘッドの位置を * で表現 TM M 2 の例 (6 トラックテープ ) 練習問題 8 問 2.1: 言語 {a n b n c n n 0} を決定する 3 テープ TM を構成せよ ( 抽象レベルで良い ). 問 2.2: 言語 {w#w#w w {0,1} * } を受理する多テープ TM を構成せよ ( ただし, 入力アルファベット Σ={#,0,1} である. 抽象レベルで良い ). 4
例 2.1: 3 テープ TM による整数の和の計算 9 Σ={0,1,#} 3テープチューリング機械 計算の手順テープ1 $ 1. 整数の 2 進列 u, v が, 最初 u#vの形式でテーププ... 1に与えられるとする テープ2 $ 1 0 1... 2. u, vを, それぞれ, テープ2, テープ3にコピーし, テープ1を空白記号で消去 3. テープ2, テープ3のヘッドを, それぞれ,u, vの右端に移動. テープ1のヘッドをmax( u, v )+1 番 テープ3 $ 1 1 0 1... 目のセルに移動 q 有限制御部 4. 次の操作で, ビット毎にuとvの和をとり, 結果を ( テープ2, 3で読み込んだテープ 1 に書込み数字, キャリー c の内容 テープ2, テープ3のヘッド上の数字をx, yとする. を状態で区別 ) 前回の桁上がりをcとする x+y+cのビット和を計算し, 結果が0なら0を,1 標準 TMより, プログラミングが容易 なら1をテープ1に書込む. 以降では, 多テープTMを使用して x+y+cの和が2 以上なら,c=1にセット計算手順の抽象レベル記述を行う テープ1, 2, 3のヘッドを左に1つ移動際に, 基本的な演算が使用できる 5. 全ての桁について終了したら, 受理状態で停として良い止し, 計算終了 ( テープ1に計算結果が残る ). 非決定性チューリング機械 (NTM: Nondeterministic Turing Machine) 10 直感的には, 並列計算 ができるよう拡張した TM 形式的な定義ある状態 q で文字 x を読み込んだ時の遷移が複数あり, どれかを選択実行 決定性 TM: δ(q, x)=(r,y,d)) 動作は一つ ( 決定的 ) q, r Q,x, y Γ, D {L,R} 非決定性 TM: δ(q,x)= {(r 1,y 1,D 1 ),..., (r k,y k,d k )} 動作は複数から選択 ( 非決定的 ) q, r 1,..., r k Q,x,y i Γ, D i {L,R} 同じ入力 wに対して, 途中どの遷移を選ぶかで, 動作 ( 様相の列 ) および結果 ( 受理 / 非受理 ) が異なる. NTMの動作 ( 様相の列 ) は木で表される. 計算木 (computation tree) と呼ぶ q x/y 1 r 1 x/y k x/y 2 r 2 : r k 5
NTM が受理する言語 11 NTM M は入力 w に対し計算木上の全てのパスを並列に実行し, 以下のように動作 w を受理するパスがあれば,w を受理して停止する そうでなければ,w を受理しない ( 全てのパスが q reject に到達する場合は停止し, そうでない場合, 永久に動作を継続する ) 以下の時,NTM Mは言語 Lを受理する, と定義する. 任意のw Lについて,Mの計算木の中に受理状態 q accept に到達するものが少なくとも1つ存在する. 任意のw Lについて,Mの計算木のどのパスも拒否状態 q reject に到達する, もしくは, 停止しない. NTM の例 12 例 2.2: 言語 a * ab * b を受理する NTM M を構成せよ. a/a, R b/b, R q 0 a/a, R q 1 b/b, R /, R a/a, R /, R q reject b/b, R q 2 a/a, R b/b, R /, R q accept Mにaabを入力した時の計算木 q 0 aab aq 0 ab aq 1 ab aaq 0 b aaq 1 b aaq reject b aabq reject aabq 1 aabq 2 aab q reject aab q accpet 受理! 6
定理 2.3: NTM と標準 TM は等価 13 NTM では計算木上の全パスを並列に計算する 標準 TM で実行するには? 初期様相 C 0 C 1,1 C 1,2... C 1, k_1 C 2,1 C 2,2....... C 2, k_2... 計算木 (computation tree) 問 : 深さ優先で探索するとどうなる? アイデア : 幅優先探索による時分割処理初期様相 C 0 から 1 ステップで導出可能な全ての様相 C 1,1 ~C 1, k_1 を計算計算された各様相から,1 ステップで導出可能な様相 C 2,1 ~C 2, k_2 を計算同様に, 木の頂点から深さ i の全ての様相について, 深さ i+1 の様相を導出いずれかの様相が受理状態 q accept に到達する ( もしくは, 全ての様相が q reject に到達する ) までこれを繰り返す 定理 2.3 の証明 14 標準 TMでNTMを模倣する 深さiおよび深さi+1の全ての様相を記録する2 本のテープ,NTM Mの遷移集合を記録するテープなどがあれば NTM を模倣可能 多テープ TM で模倣可能 定理 2.2より, 標準 TMでも模倣可能 一方,NTMが標準 TMを模倣可能であることは明らか 以上の議論および定理 2.2より,NTMと標準 TMは等価である. 7
NTM による推測 15 例 2.3: 言語 {ww w {0,1} * } を受理する1テープNTMを構成せよ ( ただし, 入力アルファベットΣ={0,1} である. 抽象レベルで良い ). ( アイデア ) ヘッドを入力記号列の中央に移動し, 最初から中央の一つ手前までの記号列と, 中央から最後までの記号列を比較して一致したら受理する ( 次頁参照 ). 中央を見つけるのは難しいので, 非決定性を使ってあらゆるヘッド位置が計算木に出現するようにする入文 wwの境目を非決定的に決める 計算木の中にヘッドがちょうど中央に移動した後でq 1 に遷移するパターンが一つ含まれる 0/0, R q 0 1010 1/1, R 0/0, R 1/1, R 1q 0 010 1q 1 010 /, R q 0 q 10q 0 10 10q 1 10 1 101q 0 0 101q 1 0 図 2.1: ヘッド位置の非決定的な選択 1010 q 1 1010q 0 1010q 1 入力 1010 に対する計算木 例 2.3 の解答例 16 (1) 入力がεの時はaccept (2) ヘッドの位置を非決定的に移動する ( 前頁の図 2.1 参照 ) (3) 文字を読み込み,Xで書き換える. 左端の文字を調べ, 読み込んだ文字と同じかどうか比較する. 同じなら,Yで書き換える. 異なる場合は,reject (4) 以下を繰り返し実行する テープ上に0も1も存在しなければaccept Xのブロックの右側の文字と,Yのブロックの右側の文字を比較し, 同じなら, それぞれ, X,Yで書き換える. 異なる場合はreject 1 0 0 1 0 0 1 0 0 X 0 0 Y 0 0 X 0 0 YYYXXX 比較 (2) (3) (4) (5) 8
NTM で効率よく解ける問題 17 例 2.4: クリーク問題 C={ G k 無向グラフ G は大きさ k のクリーク ( 完全部分グラフ ) を持つ } を決定する NTM を構成せよ. G=(V,E) で表す. ここで,V={v 1,...,v n } は頂点の集合,E={e 1,...,e m } は辺の集合である.G を各要素が 0 または 1 の n n 行列 ( 隣接行列 ) として符号化する. v 2 隣接行列 v v 6 1 v 5 v 4 k=4のクリークを持つグラフ v 1 v 2 v 3 v 4 v 5 v 6 v 3 v 1 0 1 0 0 1 1 v 2 1 0 1 0 0 1 符号化 v 3 0 1 0 1 1 1 v 4 0 0 1 0 1 1 v 5 1 0 1 1 0 1 v 6 1 1 1 1 1 0 例 2.4 の解答例 18 2テープNTMを使う (1) 頂点の部分集合を非決定的に推定し, テープ2に書込む ( 非決定性モード ) (2) 各部分集合について頂点数 =k, かつ, どの頂点間にも辺があるかどうかを判定 する ( 決定性モード ) v1 選択除外 v v 2 2 選除選除 (1) V の部分集合を非決定的に推定 O(n) ステップ必要 (n は頂点の数 ) O(n 2 ) ステップ 選 v n 除 v n v n 除 (2) 選択された部分集合の頂点数が k かつ完全グラフであるかどうかを隣接行列でチェック O(n 2 ) ステップ必要 決定性 TM では, 全ての ( あるいは n C k 個の ) 部分集合に対してクリークを持つかどうかをしらみつぶしに調べるため, 部分集合の数 =2 n に比例したステップがかかる NTM だと多項式ステップ 9
練習問題 19 問 2.3: ブール論理式の充足可能性判定問題 論理関数 f(x 1, x 2,..., x n ) に対し,f(x 1,..., x n )= 1 となる各変数への割り当て方は存在するか? を決定する NTM( 多テープでも良い ) を構成せよ. 論理関数の例 f(x 1, x 2, x 3, x 4 )= ( x 1 x 2 x 3 ) (x 2 x 4 x 3 ) ( x 2 x 4 ) x 1,, x n の具体的な値 (0 or 1) に対し, 論理関数 f(x 1,,x n ) を計算するサブルーチンを使用してよい. TM の計算量について 20 言語受理能力は同じでも, 標準 TM は拡張された TM より多くの処理ステップが必要 k テープ TM の n 個の遷移の実行 標準 TM により O(n 2 ) ステップで模倣可能 テープ TM の 1 ステップの模倣 テープ上でヘッドが 1 往復 ( 付録 A 参照 ) 計算機 ( メモリへのランダムアクセス機能含む ) の n 個の命令の実行 標準 TM により O(n 6 ) ステップで模倣可能 証明は付録 B および参考書 2 を参照 計算機 / 標準 TM で入力サイズの多項式ステップ 1 で決定できる問題 この問題のクラスを P と呼ぶ. NTMのn 個の遷移の実行 ( 同じ状態 同じ入力から実行可能な遷移が2つの場合 ) 標準 TMによりO(2 n ) ステップで模倣可能 NTM で入力サイズの多項式ステップ数で決定できる問題 計算機で決定するのに指数ステップ 2 かかるかも知れない この問題のクラスを NP と呼ぶ. NP 完全問題 : クラス NP の中で最も難しい問題 1 入力サイズ m に対し, 計算ステップ数が m の多項式 (m 3 や m 6 等 ) で表せるもの 2 入力サイズ m に対し, 計算ステップ数が 2 m や 3 m などで表されるもの 10
21 まとめ TMの拡張 多トラックテープ, 多テープ, 非決定性, ランダムアクセス ( 付録 B 参照 ) 上記の機能を拡張しても言語受理能力は標準 TMと同じ 拡張されたTMでは, 問題を解くアルゴリズムの記述が容易 言語の決定性, 半決定性を証明するのに拡張されたTMを使って良い 拡張されたTMの計算量 NTM 以外 : 多項式ステップのアルゴリズム 標準 TMでも多項式ステップで模倣可能 NTM: 多項式ステップのアルゴリズム 標準 TMによる模倣は指数ステップかかる 制限された TM( 本講義では扱わない ) 2スタック機械,2 計数機械はTMと等価 ( 参考書 2. 参照 ) 1スタック機械はPDAと等価 (TMより能力は劣る. 計算理論 IIIで学ぶ ) Homework 問 2.1~2.3 付録 A: k テープ TM と標準 TM の計算時間比較 22 定理 2.4: k テープ TM の n 動作は標準 TM で O(n 2 ) ステップで模倣可能 ( 証明 ) k テープ TM M 1 で n 回遷移を実行した後の, テープ間でのヘッドの位置の距離は最大 2n セル M 1 の 1 回の遷移を標準 TM M 2 で模倣するには, ヘッドの往復に2n 2ステップ k 本のテープでの記号の書き込みとヘッドの移動に2k 以上より,M 2 でM 1 のn 動作を実行するためのステップ数は n (4n+2k)=O(n 2 ) 最大 4n+2k ステップ必要 11
付録 B: 23 現代計算機のモデル RAM の標準 TM による模倣実行 RAM と標準 TM の計算時間の比較 現代の計算機による TM の模倣実行 RAM (Random Access Machine) 24 TMにメモリへのランダムアクセス機能などを追加 ランダムアクセス可能なメモリとレジスタ ( 各要素へ1ステップでアクセス可能 ) 論理演算, 算術演算 条件分岐, ジャンプ など RAMの構成要素 メモリ :T[0],T[1], T[2], 有限個の汎用レジスタ :R 1 ~R k メモリ, レジスタは, 任意の整数を記憶可能 プログラムカウンタ :PrC PC アキュムレータ : AC(R 1 としても使用 ) RAMへの入力: 有限個の命令からなるプログラム メモリ上に配置 RAM は現代の計算機とほぼ同じ 命令セットの例 read j AC:=T[Rj] write j T[Rj]:=AC store j Rj:=AC load j AC:= Rj loadc c AC:=c add j AC:=AC+ Rj addc c AC:=AC+cAC+c sub j AC:=max{AC-Rj,0} subc c AC:= max{ac-c,0} half AC:= AC/2 jump s PrC:=s jpos s if (AC>0) PrC:=s jzero s if (AC=0) PrC:=s halt 停止 12
RAM の構成例 25 PrC: プログラムカウンタ R 1 (AC): アキュムレータ ( 算術演算等が可能 ) R 2,..., R k : 汎用レジスタレジスタ PrC AC(R 1 ) R 2 R k 制御ブロック read 2 addc 10 sub 3 jpos L : L: write 2 : halt プログラム R 2 =n+1 ならここに R 1 の内容を書き込み メモリ T[0] T[1] T[n-1] T[n] T[n+1] プログラムはメモリに記憶 26 定理 2.5: RAM と標準 TM の言語受理能力は等価 ( 証明 )RAM M 1 を TM M 2 で模倣する. プログラム中の命令 (write, add など, およびそのオペランド ) は全て整数として与えられる ( 仮定 ) M 1 に与えられるプログラム ( 整数の列 ) を M 2 の入力記号 Σ 2 の列に対応づける必要がある プログラム中に出現する整数が m 種類だとすると ( すなわち,Σ 1 ={1,2,,m}),M 2 の入力アルファベットは Σ 2 ={a 1,a 2,,a m } とすれば良い. 1 対 1 関数 E: Σ 2 {1,2,...,m} を使って,TM の記号 Σ 2 と RAM の整数 Σ 1 の間の対応関係を定義しておく. RAM への入力 1 2 1 2 3 2 1 1 対 1 関数 E TM への入力 ababcba RAM M 1 を k+3 テープ TM M 2 で模倣 (k は M 1 のレジスタ数 ) 第 1 のテープ : 入力の受け取りと結果の出力 ( 1* の要素 ). 第 2 のテープ : M 1 のメモリを模倣 第 3 のテープ : 補助的な作業用テープとして使用 残りの k 本のテープ :M 1 のレジスタを模倣 ( レジスタの値は 2 進で表現 ) プログラムカウンタ PrC の値は TM M 2 の有限制御部の状態で区別 ( プログラムの長さは有限 ) 13
メモリの実現 27 メモリの各セルをテープに ( アドレス, 値 ) の形式で記録 アドレスと値は整数の 2 進表記とする. セル間は空白で区切る ( セルの順番は任意 ) メモリの末尾を表す記号 を追加 カッコやコンマも Γ 2 の要素 以上より,M 2 のテープ記号は Γ 2 =Σ 2 {$, 0, 1,, (,,, ), } とする. $ (0,3) (2,5) (1,0) (7,45) 実際には数字は 2 進数で書き込む プログラムの TM M 2 による実行 28 プログラムは1 対 1 関数 Eを逆に使って,Σ 2 の記号列 a 1 a 2 a n として与えられると仮定 1 第 1テープに置かれた入力 a 1 a 2 a n を変換し, 第 2テープに (0, E(a 1 ) ), (1, E(a 2 ) ),, (n-1 1, E(a n )) ) として書き込む. 2 PrC( 初期値は0) の指す命令を実行し,PrCの値を1 増やす (jump 時は値を代入 ). 3 haltが実行されるまで2を繰り返す. 4 第 2テープの内容を, 2 の要素に変換し, 第 1テープに書き込む. プログラムα 1,α 2,...,α n (α i はM 1 の命令のいずれか ) の模倣 add 3: R 1 +R 3 を計算しR 1 に保存. 例 2.1の方法で実現可能 jump 10:PrC に 10 を代入し, 次の命令として α 10 を選択 write 3: R 1 の内容 (4とする) を, メモリのR 3 が指すアドレス (7とする) に保存第 2のテープを左端から読み込み,(7,xx) を探す.xxの位置に4を書き込む. 見つからない場合は, を (7,4) に書き換える. 省略するが, 他の命令も同様に模倣可能 以上により,k+3 テープ TM で RAM が模倣できることが分かる. 定理 2.2 より標準 TM でも模倣可能となる. 一方,RAM が標準 TM を模倣できることは明らか. 以上より,RAM と標準 TM は等価である. 14
29 TM による RAM の模倣の効率 定理 2.4より, 標準 TMによるkテープTMのn 動作の模倣にはO(n 2 ) ステップかかる. kテープtmによるramのn 動作の模倣にかかるステップ数はO(n 3 ) である. 仮定 :1 命令の実行でメモリの値のワード長 ( セル数 ) は1 しか増えないとする n 命令後のメモリの内容は高々 O(n) 個のエントリ ( アドレス, 値 ) しか持たない n 命令後のメモリの各エントリのワード長は高々 O(n) 従って,n 命令の実行ではO(n 3 ) となる. 以上より, 標準 TMによるRAMのn 動作の模倣にかかるステップ数はO(n 6 ) である. 30 計算機で TM を模倣できるか? RAMは無限容量のメモリを持つ点で, 現代の計算機とは異なる. 計算機単独では, メモリ容量, 補助記憶装置の容量が限られているため,TMの無限長テープを模倣できない. 実は, 計算機は有限オートマトンと等価 補助記憶装置の入れ替えが可能 ( もしくは, ネットワーク経由でデータをいくらでも保存可能 ) と仮定すると, 計算機による TM の模倣が可能. 15