Microsoft PowerPoint - tm ppt [互換モード]

2. チューリング機械の拡張

2

„

標準

TM （1テープ1ヘッドTM）の拡張

標準

階的 機能を拡

す

チューリング機械の拡張

¾

標準TMに段階的に機能を拡張する．

¾

拡張したTMは標準TMより高い能力を持つか？

„

結論：機能を拡張した

TMの言語受理能力は標準のTMと同じ

¾

標準

TMと拡張したTMが言語受理能力において

等価

であることを示す．

¾

ある言語（問題）が決定可能/半決定可能かどうかを証明する際に，機能を拡

張 た

が使え よう な （

よ プ グ

グが簡単化）

張したTMが使えるようになる（TMによるプログラミングが簡単化）．

拡張する機能と等価性の証明法

„

拡張する機能

¾

多重トラック

¾

複数のテープ

¾

非決定性

¾

機械語命令（算術演算，条件分岐等），ランダムアクセスメモリ（付録B）

„

等価性の証明

¾

2つのマシンが等価⇔言語受理能力が同じ，と定義する．

¾

各機能を拡張したTMが，標準TMで模倣できること，およびその逆を示す．

•証明のためのTMの動作は抽象レベルで説明する． 4

テープの各セルが k (≥2) 個のトラックに分割されたTM M

₁

多重トラックテープを持つ

TM

3トラックテープを持つTM M₁ q 有限制御部 ↑

$

0

1 □ □

0

...

$

1

1

0

□

1

...

$

□

1 0

0

0

...

3トラックテ プを持つTM M₁

TM M

1 „

kトラック

ΤΜ

Μ

₁

の定義

¾ テープの各セルが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.1: 多重トラックTMは標準TMと等価

（証明）kトラックTM M

₁

を標準

TM M

₂

で模倣できることを示す．

標準1テープTM M2 3トラックテープ M1 一つの記号 とみなす

標準

を

う 構成す

[$,$,$] [0, 1, □] [1, 1, 1] ... q 有限制御部 ↑

TM M

₂ 2 q 有限制御部 ↑

$

0

1 □ □

0

...

$

1

1

0

□

1

...

$

□

1 0

0

0

...

TM M

1 とみなす „

標準ΤΜ Μ

₂

を以下のように構成する．

„ テープ記号：Γ₂= Γ×Γ×Γ= {[0,0,0],[0,0,1],...,[1,1,1],...,[□, □, □], ..., [$,$,$]} „ 遷移関数：δ₂(q, [x,y,z])=(r, [x’,y’,z’], D) z M₂が3トラックTM M1を模倣できることは明らか．kトラックTMについても同様にそれを 模倣する標準TMが構成できる． z 逆にkトラックTMが1テープTMを模倣できることは明らか．∴多重トラックTMと1テープ TMは等価．□ 6

複数のテープを持つ

TM

„k本のテープとk個のヘッドを持つTM M

₁

の定義

• 入力w∈Σ

*

_は

_{1本目のテープ上に置かれる．}

2本目以降のテ プの内容は最初は空白文字で初期化されている

• 2本目以降のテープの内容は最初は空白文字で初期化されている．

• 全てのヘッドで文字を読み取り，記号の組と現在の状態から，各テープ上に

おいて，文字の書換およびヘッドの移動（右/左/静止）を行う．

$

0

1

□ □

₀

_...

テープ1 3テープチューリング機械

kテープTMの遷移

δ(q, x1,…,xk)=(r, x’1,…,x’k, D1, ..., Dk ） q

$

1

1

0

□

₁

_...

$

□

_{1 0}

₀

₀

_...

テープ2 テープ3

有限制御部

xi, x’j∈Γ, Dl ∈{L, R, S} (1≤i, j, l

≤

k)

q

x1,…,xk/x’1,…,x’k, (D1, ..., Dk )

r

状態遷移図における記法

ヘッドの静止も可

定理

2.2: kテープTMと標準TMは等価

（証明）kテープTM M

₁

を2kトラックTM M

₂

で模倣する．

1回の遷移を以下のステップで実行 (1) テ プ上で全ての“ ”が左側にくる位置にM のヘ ドを移動 有限制御部に， q(a,b,a)のような状態を 持たせることで読んだ 文字を区別 (1) テープ上で全ての“∗”が左側にくる位置にM2のヘッドを移動 (2) 左にヘッドを移動しながら，各テープのヘッド上の文字を読み込む (3) 右にヘッドを移動しながら， 遷移関数どおりに各テープの記号を書換え，ヘッドを移動 • 以上により，2kトラックTMがkテープTMを模倣可能であることがわかる． • 一方，kテープTMが標準TMを模倣可能であることは明らか． • 以上の議論および定理2.1より，kテープTMと標準TMは等価．□ テープ1 $ 0 1 0 □ □ □ ... テ プ1 を模倣 テープ2 を模倣 テープ3 を模倣 $ 0 1 0 ... □ □ * □ □ □ □ ... $ 1 1 0 1 □ □ ... □ □ * □ □ □ □ ... $ □ 1 0 0 0 □ ... □ □ □ * □ □ □ ... TM M₂の例 (6トラックテープ) ヘッドの位置を“*”で 表現 M2のヘッド 8

練習問題

問

2.1: 言語{a

n

_b

n

_c

n

| n≥0}を決定する3テープTMを構成せよ（抽象レベ

ルで良い）．

問2.2: 言語{w#w#w | w

∈ {0,1}

*

_{}を受理する多テープTMを構成せよ}

（ただし，入力アルファベット

Σ={#,0,1}である．抽象レベルで良い）．

例

2.1: 3テープTMによる整数の和の計算

$

□ □ □ □ □

_...

テープ1 3テープチューリング機械

計算の手順

1 整数の2進列u vが 最初u#vの形式でテープ

Σ={0,1,#}

q

$

1

0

1

□ □

_...

$

1

1

0

1

□

_...

テープ2 テープ3 有限制御部 （テープ2, 3で読み込んだ 数字 キャリーcの内容 1. 整数の2進列u, vが，最初u#vの形式でテ プ

1に与えられるとする

2. u, vを，それぞれ，テープ2, テープ3にコピーし， テープ1を空白記号で消去 3. テープ2，テープ3のヘッドを，それぞれ，u, vの右 端に移動．テープ1のヘッドをmax(|u|,|v|)+1番 目のセルに移動 4. 次の操作で，ビット毎にuとvの和をとり，結果を テープ1に書込み 数字，キャリ cの内容 を状態で区別） •標準TMより，プログラミングが容易 •以降では，多テープTMを使用して 計算手順の抽象レベル記述を行う 際に，基本的な演算が使用できる として良い テ プ1に書込み „テープ2，テープ3のヘッド上の数字をx, yとする． 前回の桁上がりをcとする „ x+y+cのビット和を計算し，結果が0なら0を，1 なら1をテープ1に書込む． „ x+y+cの和が2以上なら，c=1にセット „テープ1, 2, 3のヘッドを左に1つ移動 5. 全ての桁について終了したら，受理状態で停 止し，計算終了（テープ1に計算結果が残る）． 10

非決定性チューリング機械

(NTM: Nondeterministic Turing Machine)

直感的には，「並列計算」ができるよう拡張した

TM

„

形式的な定義

ある状態qで文字xを読み込んだ時の遷移が複数あり，どれかを選択実行

決定性TM: δ(q, x)=(r,y,D)) Æ 動作は一つ（決定的） q, r∈Q，x, y ∈Γ, D ∈ {L,R} 非決定性TM: δ(q,x)= {(r1,y1 ,D1), ..., (rk,yk,Dk)} Æ 動作は複数から選択（非決定的） q, r1, ..., rk∈Q，x,yi∈Γ , Di∈ {L,R} „ 同じ入力wに対して，途中どの遷移を選ぶかで， 動作（様相の列）および結果（受理/非受理）が異なる． „ NTMの動作（様相の列）は木で表される． ¾計算木（computation tree）と呼ぶ

q

x/y1

r

1

r

_k

r

₂

:

x/y2 x/yk

NTMが受理する言語

„

NTM Mは入力wに対し計算木上の全てのパスを並列に実行し，以

下のように動作

¾

wを受理するパスがあれば，wを受理して停止する

¾

そうでなければ，wを受理しない（全てのパスがq

_reject

に到達する場合は停止し，

そうでない場合，永久に動作を継続する）

„以下の時，NTM Mは言語Lを受理する，と定義する．

¾

任意のw∈Lについて，Mの計算木の中に受理状態q

q

_acceptaccept

に到達するものが少

なくとも

1つ存在する．

¾

任意のw∉Lについて，Mの計算木のどのパスも拒否状態q

_reject

に到達する，も

しくは，停止しない．

12

NTMの例

„

例2.2: 言語a

*

_ab

*

_{bを受理するNTM Mを構成せよ．}

q0aab q₀ q₁ a/a, R □/□, R q2 a/a, R b/b, R b/b, R qaccept a/a, R b/b, R qreject b/b, R □/□, R a/a, R □/□, R _{Mにaabを入力した時の計算木} aq0ab aq1ab 受理！ aaq0b qreject aabqreject aaq1b aabq2 aab□qaccpet aabq1 aab□qreject aaqrejectb

定理

2.3: NTMと標準TMは等価

„

NTMでは計算木上の全パスを並列に計算するÆ標準TMで実行

するには？

．．． ．． ．． ．．． ．．． 初期様相C0 C1,1 C1,2 C1, k_1 C2,1 C2,2 C2, k_2

計算木（computation tree）

問：深さ優先 で探索すると どうなる？

アイデア：

幅優先探索による時分割処理

初期様相C

₀

から

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の証明

„

標準TMでNTMを模倣する

9深さiおよび深さi+1の全ての様相を記録する2本のテープ，NTM Mの遷移集合

を記録するテ プなどがあればNTMを模倣可能 多テ プTMで模倣可能

14

を記録するテープなどがあればNTMを模倣可能→多テープTMで模倣可能

9定理2.2より，標準TMでも模倣可能

9一方，NTMが標準TMを模倣可能であることは明らか

9以上の議論および定理2.2より，NTMと標準TMは等価である．

□

NTMによる推測

例2.3: 言語{ww | w

∈ {0,1}

*

_{}を受理する1テープNTMを構成せよ（ただし，入力アル}

ファベットΣ={0,1}である．抽象レベルで良い）．

（アイデア）

（アイデア）

„ ヘッドを入力記号列の中央に移動し，最初から中央の一つ手前までの記号列と，中央から 最後までの記号列を比較して一致したら受理する（次頁参照）． „ 中央を見つけるのは難しいので，非決定性を使ってあらゆるヘッド位置が計算木に出現する ようにする 0/0 R 入文wwの境目を非決定的に決める →計算木の中にヘッドがちょうど中央に移動し た後でq1に遷移するパターンが一つ含まれる

q

0

1010

q

0

q

1 0/0, R 1/1, R 0/0, R 1/1, R …

図2.1: ヘッド位置の

非決定的な選択

□/□, R

q

0

1010

1q

0

010

1q

1

010

10q

0

10

10q

1

10

101q

0

0

101q

1

0

1010q

0

1010q

1

1010□q

1

入力1010に対する計算木

例

2.3の解答例

(1)

入力がεの時はaccept

(2)

ヘッドの位置を非決定的に移動する（前頁の図

2.1参照）

文字を読 込

書き換える 左端 文字を調べ 読 込んだ文字と同じか

16

(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 Y Y Y X X X (5) (2) (3) (4) 比較

NTMで効率よく解ける問題

„

例

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

v

2

v

₃ 0 1 0 0 1 1

隣接行列

v1 v2v3 v4v5 v6 v1

v

1

v

6

v

5

v

4 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 符号化 vv23 v4 v5 v6

k=4のクリークを持つグラフ

18

例

2.4の解答例

2テープNTMを使う

(1)

頂点の部分集合を非決定的に推定し，テープ

2に書込む（

非決定性モード

）

(2)

各部分集合について頂点数=k ，かつ，どの頂点間にも辺があるかどうかを判定

する（

決定性モード

）

v1 選択 除外 v2 v2 vn vn vn (1) Vの部分集合を非決定的 に推定ÆO(n) ステップ必要 （nは頂点の数） _O(n2_{)ステップ} 選 _{除選 除} n n n ◎ × × × × × (2) 選択された部分集合 の頂点数がkかつ完全 グラフであるかどうか を隣接行列でチェック ÆO(n2_{)ステップ必要} 除 選 _除 決定性TMでは，全ての（あるいは_nC_k個の）部分集合に対してクリークを持つかどうかをしらみつぶ しに調べるため，部分集合の数＝2に比例したステップがかかるÆNTMだと多項式ステップ

練習問題

„

問

2.3: ブール論理式の充足可能性判定問題「論理関数f(x

₁

, x

₂

, ...,

x

_n

)に対し，f(x

₁

, ..., x

_n

)= 1 となる各変数への割り当て方は存在する

か

を決定す

多

プ も良

を構成 よ

か？」を決定するNTM（多テープでも良い）を構成せよ．

¾

論理関数の例 f(x

₁

, 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

)を計算するサブ

ルーチンを使用してよい．

20

TMの計算量について

¾

言語受理能力は同じでも，標準

TMは拡張されたTMより多くの処理ステップが必要

„

kテープTMのn個の遷移の実行

¾標準TMによりO(n2_{)ステップで模倣可能} ¾テープTMの1ステップの模倣→テープ上でヘッドが1往復（付録A参照）

„

計算機（メモリへのランダムアクセス機能含む）のn個の命令の実行

¾標準TMによりO(n6_{)ステップで模倣可能} 計算機/標準TMで入力サイズの多項式ステップ1_{で決定できる問題} Æこの問題のクラスを“P”と呼ぶ． 証明は付録B および参考書 2を参照

„

NTMのn個の遷移の実行

（同じ状態・同じ入力から実行可能な遷移が2つの場合） ¾標準TMによりO(2n_{)ステップで模倣可能} NTMで入力サイズの多項式ステップ数で決定できる問題 Æ計算機で決定するのに指数ステップ2_{かかるかも知れない} ¾この問題のクラスを“NP”と呼ぶ． ¾NP完全問題：クラスNPの中で最も難しい問題 1_{入力サイズmに対し，計算} ステップ数がmの多項式 （m3_やm6_{等）で表せるもの} 2_{入力サイズmに対し，計算} ステップ数が2m_や3m_などで 表されるもの

まとめ

„

TMの拡張

¾

多トラックテープ，多テープ，非決定性，ランダムアクセス（付録

B参照）

¾

上記の機能を拡張しても言語受理能力は標準TMと同じ

¾

拡張された

TMでは，問題を解くアルゴリズムの記述が容易

• 言語の決定性，半決定性を証明するのに拡張されたTMを使って良い

¾

拡張された

TMの計算量

• NTM以外：多項式ステップのアルゴリズム→標準TMでも多項式ステップで模倣可能 • NTM: 多項式ステップのアルゴリズム→標準TMによる模倣は指数ステップかかる

„

制限されたTM（本講義では扱わない）

„

制限されたTM（本講義では扱わない）

¾

2スタック機械，2計数機械はTMと等価（参考書2.参照）

¾

1スタック機械はPDAと等価（TMより能力は劣る．計算理論IIIで学ぶ）

„

Homework

¾

問2.1～2.3

22

付録

A: kテープTMと標準TMの計算時間比較

„

定理

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

₂

でM

₁

のn動作を実行するためのステップ数は

n×(4n+2k)=O(n

2

)

最大 4n+2kステップ必要

n×(4n+2k)=O(n

2

)

□

付録

B:

„

現代計算機のモデル

RAM

の標準

TMによる模倣実行

„

RAMと標準TMの計算時間の比較

„

現代の計算機による

TMの模倣実行

24

RAM （Random Access Machine）

„

TMにメモリへのランダムアクセス機能などを追加

¾ランダムアクセス可能なメモリとレジスタ（各要素へ1ステップでアクセス可能） ¾論理演算 算術演算 ¾論理演算，算術演算 ¾条件分岐，ジャンプ ¾など

„

RAMの構成要素

¾メモリ：T[0],T[1], T[2], … ¾有限個の汎用レジスタ：R1～Rk • メモリ，レジスタは，任意の整数を記憶可能 ¾プログラムカウンタ P C 命令セットの例 readj AC:=T[Rj] writej T[Rj]:=AC storej Rj:=AC loadj AC:= Rj loadCc AC:=c addj AC:=AC+ Rj addC c AC AC+c ¾プログラムカウンタ：PrC ¾アキュムレータ：AC（R₁としても使用） ¾RAMへの入力：有限個の命令からなるプログラム • メモリ上に配置

„

RAMは現代の計算機とほぼ同じ

addC c AC:=AC+c subj AC:=max{AC-Rj,0}

subCc AC:= max{AC-c,0}

half AC:= ⎣AC/2⎦

jumps PrC:=s

jposs if (AC>0) PrC:=s

jzeros if (AC=0) PrC:=s

RAMの構成例

PrC: プログラムカウンタ R1（AC）: アキュムレータ （算術演算等が可能）

PrC

AC(R

1

)

R

プログラム read 2 addC 10 sub 3 jpos L

:

制御ブロック （算術演算等が可能） R2, ..., Rk:汎用レジスタ レジスタ

R

2

R

k メモリ L: write 2

:

halt T[0] T[1] … T[n-1] T[n] T[n+1] … プログラムはメモリに記憶 R2=n+1ならここに R1の内容を書き込み 26

定理2.5: RAMと標準TMの言語受理能力は等価

（証明）RAM M1をTM M2で模倣する． „プログラム中の命令(write, addなど，およびそのオペランド)は全て整数として与えられる（仮定） „M₁に与えられるプログラム（整数の列）をM2の入力記号Σ2の列に対応づける必要がある ¾プログラム中に出現する整数がm種類だとすると（すなわち，Σ1={1,2,…,m}），M2の入力アルファベット はΣ2={a1,a2,…,am}とすれば良い． ¾1対1関数E: Σ2→{1,2,...,m}を使って，TMの記号Σ2とRAMの整数Σ1の間の対応関係を定義しておく．

RAMへの入力

1 2 1 2 3 2 1

TMへの入力

ababcba

1対1関数E „RAM M1をk+3テープTM M2で模倣（kはM1のレジスタ数） ¾第1のテープ： 入力の受け取りと結果の出力（∑1*の要素）． ¾第2のテープ： M1のメモリを模倣 ¾第3のテープ：補助的な作業用テープとして使用 ¾残りのk本のテープ：M1のレジスタを模倣(レジスタの値は2進で表現) zプログラムカウンタPrCの値はTM M2の有限制御部の状態で区別（プログラムの長さは有限）

メモリの実現

„

メモリの各セルをテープに

（アドレス，値）

の形式で記録

¾

アドレスと値は整数の

2進表記とする．

„

セル間は空白で区切る（セルの順番は任意）

„

メモリの末尾を表す記号

⊕

を追加

„

以上より，M

₂

のテープ記号はΓ

₂

=Σ

₂

∪{$, 0, 1, □,

(

,

,

,

)

, ⊕ }とする．

カッコやコンマも Γ2の要素

$

(0,3)

□

_(2,5)

□

_(1,0)

□

_(7,45)

□

_…

_⊕

実際には数字 は2進数で書き 込む 28

プログラムの

_{TM M}

₂

による実行

プログラムは

1対1関数Eを逆に使って，Σ

₂

の記号列a

₁

a

2

… a

n

として与えられると仮定

① 第1テープに置かれた入力a

₁

a

2

… a

n

を変換し，第2テープに(0, E(a

1

) ), (1, E(a

2

) ),

(n-1 E(a ) )として書き込む

…, (n 1, E(a

n

) )として書き込む．

②

PrC（初期値は0）の指す命令を実行し，PrCの値を1増やす(jump時は値を代入)．

③

halt

が実行されるまで②を繰り返す．

④ 第

2テープの内容を，

∑

₂∗

_{の要素に変換し，第1テープに書き込む．}

„プログラムα1,α2,...,αn (αiはM1の命令のいずれか)の模倣 add 3: R₁+R₃を計算しR₁に保存．例2.1の方法で実現可能 jump 10: PrCに10を代入し，次の命令としてα10を選択 jump 10: PrCに10を代入し，次の命令としてα10を選択 write 3: R1の内容(4とする)を，メモリのR3が指すアドレス(7とする)に保存 第2のテープを左端から読み込み，(7,xx)を探す．xxの位置に4を書き込む． 見つからない場合は， 「⊕」を「□(7,4) ⊕」に書き換える． 省略するが，他の命令も同様に模倣可能 以上により，k+3テープTMでRAMが模倣できることが分かる．定理2.2より標準TMでも模倣可能となる． 一方，RAMが標準TMを模倣できることは明らか．以上より，RAMと標準TMは等価である．□

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(n3_{)となる．}

„

以上より，標準TMによるRAMのn動作の模倣にかかるステップ数はO(n

6

_{)である．}

30

計算機で

TMを模倣できるか？

„

RAMは無限容量のメモリを持つ点で，現代の計算機とは異なる．

„

計算機単独では，メモリ容量，補助記憶装置の容量が限られている

装

ため，TMの無限長テープを模倣できない．

¾

実は，計算機は有限オートマトンと等価

„

補助記憶装置の入れ替えが可能（もしくは，ネットワーク経由でデータ

をいくらでも保存可能）と仮定すると，計算機によるTMの模倣が可能．