Microsoft PowerPoint - 5.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 5.ppt [互換モード]"

あかりかがんじ
4 years ago
Views:

1 5. チューリングマシンと計算 1

2 5-1. チューリングマシンとその計算これまでのモデルではテープに直接書き込むことができなかったまた入力テープヘッドの操作は右方向だけしか移動できなかったこれらの制限を取り除いた機械を考えるこのような機械をチューリングマシン (Turing Machine,TM) と呼ぶ ( 実は TMは現実のコンピュータの能力を持つ ) TM の特徴 (DFA との比較 ) 無限長テープを持つ書き込み可能ヘッドを持つヘッドは左右に移動可能 2

3 TM の概略無限長テープ 0 1 読み書きヘッド有限制御部 TM を定める要素テープ入力記号テープ記号空白記号有限制御部内部状態初期状態状態変化受理かどうかの判断 3

4 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

5 TM の図式表現 ( 状態遷移図 ) TMは状態遷移図で表現できるセルへの書き込み δ ( qs, ) = ( q', s', R) のときヘッド位置のテープ記号を書き換える読み込み記号ヘッドの移動方向 s q 状態の変化 s', R 右方向に移動 q ' 5

6 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

7 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

8 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) q ( q,0, R) ( q, Y, L) ( q, Y, R) q ( q,0, L) ( q, X, R) ( q, Y, L) q ( q, Y, R) ( q,, R) q 4 8

9 TM の計算例 T 1 ここでは TM が0011 を受理する計算を示すなお TMの計算は TMの様相の列として表される q Xq 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

10 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

11 TM の計算例 2 T 2 ここでは TM が0000 を受理する計算を示す q 0000 X q 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

12 練習 L = w w w a b 言語 TM を作成せよ * { # {,,}} } を認識する 12

13 5-2. 多テープ TM チューリング機械の拡張としてリング機械の拡張として多テープチューリング機械を考えると便利なことが多い無限長テープ 0 1 テープ1 有限制御部テープテープ k 多テープチューリング機械の概略 13

14 多テープ TM の状態遷移関数多テープTMの形式的定義では状態遷移関数 δ を次のように定めればよい k k k δ : Q Γ Q Γ { L, R} k 状態とヘッドの読み取り値が決まると遷移後の状態と k ヘッドの書き込み値および移動方向が定まる 14

15 多テープ TM と TM の等価性 1 本のテープを用いて多テープをシミュレートできればよいアイディアヘッド位置を表す記号を導入するテープ a 1 a 2 a k ヘッド a 1 a 2 k a 15

16 テープ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

17 5-3. ランダムアクセスマシン (RAM) より現実的な計算機モデルとして RAM が考えられている間接アドレス方式のアドレジスタジスを蓄えるレメモリアドレスレジスタ (MAR) R 0 2 レ1 プログラム (ROM) R 1 2 スタR15 メモリ 17

18 RAM と TM の等価性多テープを用いて RAMをシミュレートすることができるトすることができる ( すなわち 1テープTMによってもシミュレートすることができる ) ここでは厳密な証明はおこなわない直感的にシミュレートが可能であると認識できればよいアイディア機能ごとにテープを用意して模倣するメモリテープ # 0$ x 1$ 10$ 11$ 0 # x 1 # x 2 # x 3 MAR ワークテープ R 0 R 15 18

19 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

20 NTM の状態遷移関数 NTMの形式的定義では状態遷移関数 δ を次のように定めればよい ( ) δ : Q Γ P Q Γ { L, R} 状態とヘッドの読み取り値が決まるといくつかの遷移の可能性のなかで都合の良いものに遷移する δ ( qs, ) = {( q', s', R),( q'', s'', L)} 20

21 NTM の計算の木 ( 様相の遷移の可能性 ) DTM の計算 NTM の計算 : 様相 21

22 DTM による NTM のシミュレーション NTMの計算の木を一本道で辿るような DTMを設計すればよい計算の途中ではどのくらいの深さか不明深さ優先探索幅優先探索計算の途中が長くても NTM が受理でれば TM もできる 22

23 非決定性 TM と TM の等価性証明すべての NTM N に対してそれと等価な DTM D が存在するテープ 3 D は 3 つのテープを持つものとする 0 1 入力テープ D X # 0 1 シミュレーションテープアドレステープ 23

24 テープ1( 入力テープ ) は常に入力文字列を含み決して変更しないテープ 2 は現在シミュレートしている非決定的計算上での Nのコピーを維持するテープ 3 は現在シミュレートしている非決定的な計算木の探索点の位置を保持する 24

25 Nの遷移可能の選択数の最大値をbとする木のすべての節点に対して Σ = {1, 2,, b} の文字列を割り当てる ε b 122 次のようなアルゴリズムにしたがってシミュレーションを行うションを行う 25

26 w 1. テープ 1 に N への入力をセットしテープ2 テープ3は空とする 2. テープ 2にテープ 1をコピーする 3. テープ3のアドレスにしたがって Nの一つの枝をシミュレートする受理状態になれば受理するテープ 3 のアドレスを使いきったり遷移不可能になったらステージ4にいく 4. テープ3の文字列を長さの順でかつ辞書式順に並べ換えるステージ2に行って対応する計算を一つシミュレートするこのアルゴリズムによって D はN をシミュレートすることがわかる QED 26

27 5-5. チャーチチューリングのテーゼ ( 計算の定義 ) このように DTM はいろいろなモデルと等価であることが示されたこのような状況証拠から機械的な計算( アルゴリズム ) とはチューリング機械で計算できるものとしようという提唱がなされたこれをチャーチチューリングのテーゼ (Church-Turing thesis) というつまりアルゴリズムの定義とは対応するチューリング機械が存在することである 27

Microsoft PowerPoint - 3.ppt [互換モード]

Microsoft PowerPoint - 3.ppt [互換モード] 3. プッシュダウンオートマトンと文脈自由文法 1 3-1. プッシュダウンオートマトンオートマトンはメモリがほとんど無かったこの制限を除いた機械を考える理想的なスタックを利用できるようなオートマトンをプッシュダウンオートマトン (Push Down Automaton,PDA) という 0 1 入力テープ 1 a 1 1 0 1 スタッb 入力テープを一度走査したあとク2 入力テプを度走査したあと