計算の理論 II Turing機械 月曜4校時 大月美佳.

Slides:



Advertisements
Similar presentations
計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
Advertisements

コンパイラ 2011年10月17日
「Postの対応問題」 の決定不能性の証明
チューリングマシン 2011/6/6.
計算の理論 II 帰納的関数(つづき) 月曜4校時 大月美佳.
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 II NP完全 月曜4校時 大月美佳.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
授業展開#11 コンピュータは 何ができるか、できないか.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
データ構造と アルゴリズム 知能情報学部 新田直也.
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
スタック長の 特徴付けによる 言語の非DCFL性 証明
コンパイラ 2012年10月15日
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
第2章 「有限オートマトン」.
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
形式言語とオートマトン2008 ー有限オートマトンー
計算の理論 II NP完全 月曜5校時 大月美佳 平成17年1月17日 佐賀大学理工学部知能情報システム学科.
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 II 帰納的関数 月曜4校時 大月美佳.
計算の理論 II 帰納的関数2 月曜4校時 大月美佳.
計算の理論 I 正則表現 火曜3校時 大月 美佳 平成16年6月8日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現(今度こそ) ー 月曜3校時 大月 美佳.
計算の理論 I 正則表現 月曜3校時 大月 美佳 平成15年6月9日 佐賀大学知能情報システム学科.
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
オートマトンとチューリング機械.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
計算の理論 II 言語とクラス 月曜4校時 大月美佳.
計算の理論 II 時間量と領域量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
計算の理論 II 計算量 月曜5校時 大月美佳 2019/4/10 佐賀大学理工学部知能情報システム学科.
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 文脈自由文法の標準形 月曜3校時 大月美佳.
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳 平成15年6月2日 佐賀大学知能情報システム学科.
計算の理論 I 正則表現とFAとの等価性 月曜3校時 大月 美佳 平成15年6月16日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I ー正則表現とFAの等価性 その1ー
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
計算の理論 I 非決定性有限オートマトン(NFA)
5.チューリングマシンと計算.
計算の理論 I -プッシュダウンオートマトン-
計算の理論 I ー正則表現とFAの等価性ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
計算の理論 I -講義について+αー 月曜3校時 大月美佳 平成31年5月18日 佐賀大学理工学部知能情報システム学科.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
Copyright 2002 守屋悦朗 オートマトンって? (Turing machine) (アニメーションで実行のこと)
計算の理論 I ー 正則表現 ー 月曜3校時 大月 美佳.
オートマトンって? (Turing machine).
計算の理論 I ε-動作を含むNFAと等価なDFA
計算の理論 I ε-動作を含むNFA 火曜3校時 大月 美佳 平成16年5月25日 佐賀大学知能情報システム学科.
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
計算の理論 I -講義について+αー 火曜3校時 大月美佳 平成31年8月23日 佐賀大学理工学部知能情報システム学科.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
計算の理論 II 時間量と領域量 月曜4校時 大月美佳 2019/9/13 佐賀大学理工学部知能情報システム学科.
Presentation transcript:

計算の理論 II Turing機械 月曜4校時 大月美佳

今日の講義 Turing機械の基礎 Turing機械の合成 各種定義(形式的定義、動作、etc.) 計算、計算可能、計算の例 ミニテスト

Turing機械 (Turing Machine) 最も能力の高いオートマトン 英国の数学者A. M. Turing 人間の知的行為の分析 ノイマン型計算機の論理的なモデル

Turing機械の形式的定義 Turing機械 M=(Q, Σ, δ, q0, F) Q: 状態の有限集合。 Σ: 可能なテープ記号のアルファベット(空白記号Bを含む) δ: 遷移関係=遷移の集合 (Q-F)×ΣからΣ×{L, R, N}×Qの有限部分集合。 q0: 初期状態、q0∈Q F: 最終状態の集合、 F⊆Q

Turing機械の模式図 テープ=左右に無限に追加可能 入力 B B B B B B B 0 0 1 1 0 0 B B B B B 有限 制御部 空白記号 遷移関数δ 0, 1, BΣ 有限状態系 qx アルファベット F q0, qx, qf Q 停止状態 の集合 qf q0 初期状態 状態の集合

Turing機械の基本的動作 状態pで入力aを読んだとき、 →遷移関数:δ(p, a)=(b, m, q) →5つ組: pabmq 方向mに移動する。(m=L|R|N) 次の状態qに遷移する。 →遷移関数:δ(p, a)=(b, m, q) →5つ組: pabmq 遷移関数の替わりに書くことができる Turing機械 M=(Q, Σ, K, q0, F) K={pabmq| δ(p, a)=(b, m, q)}

動作の例 p01Rq q11Lr r10Np δ(p, 0)=(1, R, q) δ(q, 1)=(1, L, r) 1 1 B B B 0 0 1 1 0 0 B B B 有限 制御部 有限 制御部 p→q→r

計算状況 a1…ai-1pai…an Turing機械 Mが以下のような状態なとき B B B a1…ai-1ai …an B B B p テープ上の記号列の状態 B B B a1…ai-1ai …an B B B 有限 制御部 空白記号のみ 空白記号のみ p

計算状況の例 0. 初期状態 p01Rq q11Lr r10Np 0p01100 01q1100 0r11100 0. 初期状態 0p01100 p01Rq 01q1100 q11Lr 0r11100 r10Np p→q→r B B B 0 0 1 1 0 0 B B B 有限 制御部 1

├M α├M β(α├ β(M), α├ β ) の定義 次のいずれかが成立する β=a1…ai-1qai´…an, paiai´Nq∈K β=a1…ai-1ai´qai+1…an, paiai´Rq∈K ただし、i=nのときは、 β=a1…ai-1ai´qB β=a1…ai-2qai-1ai´…an, paiai´Lq∈K ただし、i=1のときは、 β=qBa1´…ai-1an

停止 (halt) 定義 計算状況αに対して、 α├M βとなるβが 存在しないとき、Turing機械は計算状態αで 停止している。

├Mの反射的推移閉包 ├Mまたは├ ├Mの繰り返し 0p01100├M 01q1100 ├M 0r11100 ↓ 0p01100├M 0r11100 * * *

計算 (computation) α0 に始まりαr に終わるMによる計算 Turing機械M 計算状態の列α0,α1,…,αr 各i(0≦i<r)に対してαi ├M αi+1 であり、 αr=uqhv (u, v∈Σ*, qh∈F)

数の符号化 数値計算 符号化の例 数や数の組を符号化する必要がある Σ∋1とする 数xに対して、 x=11…1=1x+1 n個の数の組(x1, x2,…, xn)に対して、 (x1, x2,…, xn)= x1Bx2B…Bxn

部分的に計算可能 (partially computable) 関数f(x1,…, xn)が部分的に計算可能 =次のようなTuring機械 M=(Q, Σ, K, q0, F)が存在する。 任意の(x1, …, xn)∈D(f)に対して、 (x1, …, xn) q0B├M (x1, …, xn ,f(x1, …, xn)) qhB となるqh∈Fが存在する。 (x1, …, xn)∈D(f)であれば、 (x1, …, xn) q0Bに始まるMによる計算が存在しない。 *

計算可能 (partially computable) 関数fがMにより部分的に計算可能 →Mはfを部分的に計算する。 関数fが全域的かつ部分的に計算可能 →計算可能 →Mはfを計算する。

Turing機械の例 S(x) Turing機械 M =(Q, Σ, K, q0, F) Q={q0, q1, q2, q3, q4, q5, q6, q7, q8} Σ={B, 1} F={q8} K={q0BBLq1, q11BRq2, q1BBRq6, q211Rq2, q2BBRq3, q311Rq3, q3B1Lq4, q411Lq4, q4BBLq5, q511Lq5, q5B1Lq1, q611Rq6, q6BBRq7, q711Rq7, q7B1Rq8 } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

S(2)の計算 * 111q0B├ B111B1111q8B=B2BS(2)q8B

ミニテスト 15:40まで 15:40になったら誰かと交換 採点 最後に回収

Turing機械の作り方 Turing機械を合成して作る 単純なTuring機械 基本的なTuring機械 初期関数とTuring機械 B, 1, r, l, <a> 基本的なTuring機械 R, L, R, T, S, C, Kn 初期関数とTuring機械 Z(x), S(x), Uni(x1,…, xn)

Turing機械 B ヘッドが置かれてい ます目に空白記号Bを 書き込む。 B=({q0, qh}, {B, 1}, K, q0, {qh}) K= { q01BNqh, q0BBNqh } B B B 1 B B B B 有限 制御部 有限 制御部 q0→qh q0→qh

Turing機械 1 ヘッドが置かれてい ます目に1を書き込む。 B=({q0, qh}, {B, 1}, K, q0, {qh}) K= { q011Nqh, q0B1Nqh } 1 1 B 1 B B B B 有限 制御部 有限 制御部 q0→qh q0→qh

Turing機械 r ヘッドを1こま右へ移す。 B=({q0, qh}, {B, 1}, K, q0, {qh}) K= { q011Rqh, q0BBRqh } 1 B B 1 B B B B 有限 制御部 有限 制御部 有限 制御部 有限 制御部 q0→qh q0→qh

Turing機械 l ヘッドを1こま左へ移す。 B=({q0, qh}, {B, 1}, K, q0, {qh}) K= { q011Lqh, q0BBLqh } 1 B B 1 B B B B 有限 制御部 有限 制御部 有限 制御部 有限 制御部 q0→qh q0→qh

Turing機械 <a> 読み取られた記号がaで あるか否かを判定する。 aであればqhで停止し、 aでなければq1で停止する。 B=({q0, q1, qh}, {B, 1}, K, q0, {q1 , qh}) K= { q0aaNqh, q0bbNq1 } ここで、a≠b a b B a B B b B 有限 制御部 有限 制御部 q0→qh q0→q1

合成 2つのTuring機械 M1=(Q1, Σ, K1, q01, F1), M2=(Q2, Σ, K2, q02, F2) Q1∩Q2 =Φと仮定できる。 (できない場合は状態の名前を付け替える) q∈F1 とq02 ∈Q2 を同一視して得られる 以下のTuring機械 M1ーq→M2 =(Q1∪Q2, Σ, K, q01, F1∪F2 -{q}) K=K1∪K2∪{qaaNq02 | a∈Σ} をqにおけるM1とM2 の結合と呼ぶ。

結合のバリエーション Turing機械M, M1, M2 M M1 M2 M p q q (Q, Σ, K, q0, F-{q}) K=K∪{qaaNq0 | a∈Σ} M M1 M2 p q M q (Q∪Q1∪Q2, Σ, K, q0, F∪F1 ∪F2 -{p, q}) K=K∪K1∪K2∪{paaNq01, qbbNq02 | a, b∈Σ}

簡易表記 F1={q}であるとき、 Mが<a>のとき、 M2 M1 M1 M2 <a> M1 M2 qh q1 qh, q1をyes, noのように書ける。 M2 M1 q M1 M2 → <a> M1 M2 qh q1 <a> M1 M2 yes no →

Turing機械 R r<B> ヘッドの右側にある最初の Bを探し、そこで止まる。 no Turing機械rと<B>から合成。 r=({q0, qh}, {B, 1}, K1, q0, {qh}) K1={q0BBRqh, q011Rqh} <B>=({p0, p1, ph}, {B, 1}, K2, p0, {p1, ph}) K2={p0BBNph, p011Np1} r<B> no

Turing機械 R つづき R=(Q, {B, 1}, K, q0, F) Q={q0, qh}∪{p0, p1, ph}={q0, qh, p0, p1, ph} K=K1∪K2∪{qhBBNp0, qh11Np0, p111Nq0} = {q0BBRqh, q011Rqh, p0BBNph, p011Np1, qhBBNp0, qh11Np0, p111Nq0} F= {qh}∪ {p1, ph}-{qh}-{p1}={ph}

Turing機械 L l<B> ヘッドの左側にある最初の Bを探し、そこで止まる。 no Turing機械lと<B>から合成。 l=({q0, qh}, {B, 1}, K1, q0, {qh}) K1={q0BBLqh, q011Lqh} <B>=({p0, p1, ph}, {B, 1}, K2, p0, {p1, ph}) K2={p0BBNph, p011Np1} l<B> no

Turing機械 L つづき R=(Q, {B, 1}, K, q0, F) Q={q0, qh}∪{p0, p1, ph}={q0, qh, p0, p1, ph} K=K1∪K2∪{qhBBNp0, qh11Np0, p111Nq0} = {q0BBLqh, q011Lqh, p0BBNph, p011Np1, qhBBNp0, qh11Np0, p111Nq0} F= {qh}∪ {p1, ph}-{qh}-{p1}={ph}

Turing機械 R Rr<B> l ヘッドの右側にある最初の 連続したBBを探し、 その左側のBの位置で止まる。 Turing機械Rとrと<B>から合成。 r=({q0, qh}, {B, 1}, K1, q0, {qh}) K1={q0BBRqh, q011Rqh} <B>=({p0, p1, ph}, {B, 1}, K2, p0, {p1, ph}) K2={p0BBNph, p011Np1} R=(Q, {B, 1}, K, q0, F) Rr<B> no l yes

Turing機械 T rr<B> l Bl1 1の連続したかたまりを1こまづつ左へ移す。 ~BWB├T ~WBB ここで、 * ~:任意の記号 W:1の連続したかたまり  (下線):ヘッドの位置 ~BWB=q0~BWB ~WBB=~WqhBB * rr<B> no yes l Bl1

Tの計算例 rr<B> l Bl1 ~B11B ├* ~B11B (rr<B>) ├* ~1B1B (Bl1) no yes l Bl1

Turing機械 S Ll<B> T BT 1のかたまりW1, W2に対して以下の処理を 行う。 BW1BW2B├S BW2BB…B ここで、 W1, W2:1の連続したかたまり  (下線):ヘッドの位置 * Ll<B> no yes T BT

Sの計算例 Ll<B> T BT B11B111B ├* B11B111B (Ll<B>) ├* B1B111BB (BT) ├* B1B111BB (Ll<B>) ├* BB111BBB (BT) ├* BB111BBB (Ll<B>) ├* B111BBBB (T) Ll<B> no yes T BT

Turing機械 C Ll<B> TLlT rRS 1のかたまりW1, W2, …, Wn, Wに対して 以下の処理を行う。 ~BBW1BW2B…BWnBWB ├c ~BWBB…B * Ll<B> no yes TLlT rRS

Cの計算例 Ll<B> TLlT rRS ~BB11B1B111B ├* ~BB11B1B111B (Ll<B>) ├* ~BB11B111BBB (rRS) ├* ~BB11B111BBB (Ll<B>) ├* ~BB111BBBBBB (rRS) ├* ~BB111BBBBBB (Ll<B>) ├* ~111BBBBBBBB (TLlT) Ll<B> no yes TLlT rRS

Turing機械 Kn Lnr<B> BRn+1lLn+11 Rn n個の1のかたまりW1, W2, …, Wnに対して 以下の処理を行う。 BW1BW2B…BWnB ├kn BW1BW2B…BWnBW1B * no Lnr<B> BRn+1lLn+11 yes Rn

Knの計算例 (n=2の場合) B11B111B ├* B11B111B (L2r<B>) ├* BB1B111B1 (BR31) ├* B11B111B1 (L31) ├* B11B111B1 (r<B>) ├* B1BB111B11 (BR31) ├* B11B111B11 (L31) ├* B11B111B11 (r<B>) ├* B11B111B11B (R2)

初期関数のTuring機械 Z(x) S(x) Uni (x1, …, xn) →r1r BWB├* BWB1B →K11r BWB├* BWBW1B Uni (x1, …, xn) →Kn-i+1 BW1B…BWiB…BWnB├* BW1B…BWiB…BWnBWiB

最後に 開始 ミニテストを提出してから帰ること 次回は、 Turing機械と帰納的関数が同じであるという話 …をできるといいな。