5. チューリングマシンと計算 1
5-1. チューリングマシンとその計算 これまでのモデルでは テープに直接書き込むことができなかった また 入力テープヘッドの操作は右方向だけしか移動できなかった これらの制限を取り除いた機械を考える このような機械をチューリングマシン (Turing Machine,TM) と呼ぶ ( 実は TMは 現実のコンピュータの能力を持つ ) TM の特徴 (DFA との比較 ) 無限長テープを持つ 書き込み可能ヘッドを持つ ヘッドは左右に移動可能 2
TM の概略 無限長テープ 0 1 読み書きヘッド有限制御部 TM を定める要素 テープ入力記号テープ記号空白記号 有限制御部内部状態初期状態状態変化受理かどうかの判断 3
TM の数学的定義 TMは T = ( Q, Σ, Γ, δ, q の7 項組で与えられる 0,, F) ここで 1. Q は有限集合で 状態を表す 2. Σ は有限集合で 入力アルファベットを表す 3. Γ は有限集合で テープアルファベットを表す 4. δ は Q Γ から Q Γ { L, R} への写像 ( δ : Q Γ Q Γ { L, R} ) で 状態遷移を表す δ を状態遷移関数という 5. q 0 Q は 初期状態を表す 6. Γ は空白記号を表す 5. F Q は受理状態の集合を表す ここで Σ Γ, Σ である 4
TM の図式表現 ( 状態遷移図 ) TMは 状態遷移図で表現できる セルへの書き込み δ ( qs, ) = ( q', s', R) のとき ヘッド位置のテープ記号を書き換える 読み込み記号 ヘッドの移動方向 s q 状態の変化 s', R 右方向に移動 q ' 5
TM の様相 TM では 複数の対象が同時に変更される すなわち 一回の遷移で 状態 テープ内容 ヘッド位置の3つが同時に変化する これらの3つによってTMの様相が定義される また 下のような TM の様相は aa 1 2 amqbb i 1 2 bn と記述できる a1 a2 b b am b1 2 n q i 6
TM の状態遷移図例 n n 言語 L1 = {0 1 n 1} を受理するTM を示す 0 0,R Y Y, R q 1 T 1 0 XR, 1 Y, L q0 3 Y Y, R q, R q 4 X X, R q 2 Y Y, R 0 0,L Y Y, L 7
TM の形式的定義例 T = ( Q, Σ, Γ, δ, q,, F) 1 0 = q 0 q 1 q 2 q 3 q 4 Q {,,,, } Σ={0,1} Γ= F {0,1, XY,, } { q } = 4 δ 0 1 X Y q ( q, X, R) ( q, X, R) 0 1 3 q ( q,0, R) ( q, Y, L) ( q, Y, R) 1 1 2 1 q ( q,0, L) ( q, X, R) ( q, Y, L) 2 2 0 2 q ( q, Y, R) ( q,, R) 3 3 4 q 4 8
TM の計算例 T 1 ここでは TM が0011 を受理する計算を示す なお TMの計算は TMの様相の列として表される q 00011 Xq 011 1 X 0 q 11 Xq 2 0 Y 1 q 1 q 2 XY 0 1 Xq 0 0Y 1 XXq1Y 1 XXYq 1 1 q2 0 XXq YY Xq 2 XYY XXq 0 YY XXYq 3 Y 2 XXYYq XXYYq 4 3 9
TM の例 2 言語 L 2 = {0 を2のべき乗個並べた文字列 } n 2 = {0 n 0} を受理する TM T 2 を示す X X, R q 1 0 XR, X X, R X X, R 0 XR, q2 q3 0 R,, R, L 0 0,R q 0, R q 4 q 5 X X, L 0 0,LL 10
TM の計算例 2 T 2 ここでは TM が0000 を受理する計算を示す q 0000 X 0 0 0 q 1 000 Xq 00 q 2 3 X 0Xq 2 X 0qq X Xq 0X 4 4 q 4 X 0X qx 4 0X q 1 X 0X Xq 0X 1 XXq2X XXXq2 XXq4X q 4 XXX q 2 XXX XXXq2 XXXq5 11
練習 L = w w w a b 言語 TM を作成せよ * { # {,,}} } を認識する 12
5-2. 多テープ TM チューリング機械の拡張としてリング機械の拡張として 多テープチューリング機械を考えると便利なことが多い 無限長テープ 0 1 テープ1 有限 制御部 1 1 0 テープ2 1 1 0 テープ k 多テープチューリング機械の概略 13
多テープ TM の状態遷移関数 多テープTMの形式的定義では 状態遷移関数 δ を次のように定めればよい k k k δ : Q Γ Q Γ { L, R} k 状態とヘッドの読み取り値が決まると 遷移後の状態と k ヘッドの書き込み値および移動方向が定まる 14
多テープ TM と TM の等価性 1 本のテープを用いて 多テープをシミュレートできればよい アイディアヘッド位置を表す記号を導入する テープ a 1 a 2 a k ヘッド a 1 a 2 k a 15
テープ1 a a 1 2 ai al テープ 2 b1 b j b m テープ 3 c1 c2 ck cn a c c c c a # # 1 a a b1 b b m 1 2 k n # i l j テープ区切りを表す特別な記号 16
5-3. ランダムアクセスマシン (RAM) より現実的な計算機モデルとして RAM が考えられている 間接アドレス方式のアドレジスタジスを蓄えるレ メモリアドレスレジスタ (MAR) R 0 2 レ1 プログラム (ROM) R 1 2 スタR15 メモリ 17
RAM と TM の等価性 多テープを用いて RAMをシミュレートすることができるトすることができる ( すなわち 1テープTMによってもシミュレートすることができる ) ここでは 厳密な証明はおこなわない 直感的に シミュレートが可能であると認識できればよい アイディア機能ごとにテープを用意して模倣する メモリテープ # 0$ x 1$ 10$ 11$ 0 # x 1 # x 2 # x 3 MAR ワークテープ R 0 R 15 18
5-5. 非決定性 TM 状態の遷移を非決定的にできる TM を非決定性チューリングマシン (Non-deterministic Turing Machine,NTM) という ( なお これまでのTMは 決定性チューリングマシン (Deterministic Turing Machine,DTM) といわれる q s s', R q ' 同一様相から 2つ以上の状態遷移が可能なTM s s'', L q '' 19
NTM の状態遷移関数 NTMの形式的定義では 状態遷移関数 δ を次のように定めればよい ( ) δ : Q Γ P Q Γ { L, R} 状態とヘッドの読み取り値が決まると いくつかの遷移の可能性のなかで都合の良いものに遷移する δ ( qs, ) = {( q', s', R),( q'', s'', L)} 20
NTM の計算の木 ( 様相の遷移の可能性 ) DTM の計算 NTM の計算 : 様相 21
DTM による NTM のシミュレーション NTMの計算の木を一本道で辿るような DTMを設計すればよい 計算の途中では どのくらいの深さか不明 深さ優先探索 幅優先探索 計算の途中が長くても NTM が受理でれば TM もできる 22
非決定性 TM と TM の等価性 証明 すべての NTM N に対して それと等価な DTM D が存在する テープ 3 D は 3 つのテープを持つものとする 0 1 入力テープ D X # 0 1 シミュレーションテープ 1 2 3 2 1 アドレステープ 23
テープ1( 入力テープ ) は常に入力文字列を含み 決して変更しない テープ 2 は 現在シミュレートしている非決定的計算上での Nのコピーを維持する テープ 3 は 現在シミュレートしている非決定的な計算木の探索点の位置を保持する 24
Nの遷移可能の選択数の最大値をbとする 木のすべての節点に対して Σ = {1, 2,, b} の文字列を割り当てる ε b 122 次のようなアルゴリズムにしたがって シミュレーションを行う ションを行う 25
w 1. テープ 1 に N への入力をセットし テープ2 テープ3は空とする 2. テープ 2に テープ 1をコピーする 3. テープ3のアドレスにしたがって Nの一つの枝をシミュレートする 受理状態になれば 受理する テープ 3 のアドレスを使いきったり 遷移不可能になったら ステージ4にいく 4. テープ3の文字列を長さの順でかつ辞書式順に並べ換える ステージ2に行って対応する計算を一つシミュレートする このアルゴリズムによって D はN をシミュレートすることがわかる QED 26
5-5. チャーチ チューリングのテーゼ ( 計算の定義 ) このように DTM はいろいろなモデルと等価であることが示された このような状況証拠から 機械的な計算( アルゴリズム ) とは チューリング機械で計算できるものとしよう という提唱がなされた これを チャーチ チューリングのテーゼ (Church-Turing thesis) という つまり アルゴリズムの定義とは 対応するチューリング機械が存在することである 27