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

Slides:



Advertisements
Similar presentations
©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
Advertisements

0章 数学基礎.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
正規表現からのDFA直接構成.
コンパイラ 2011年10月17日
チューリングマシン 2011/6/6.
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
5.チューリングマシンと計算.
5.チューリングマシンと計算.
計算の理論 II NP完全 月曜4校時 大月美佳.
計算の理論 I ー DFAとNFAの等価性 ー 月曜3校時 大月 美佳.
授業展開#11 コンピュータは 何ができるか、できないか.
8.クラスNPと多項式時間帰着.
東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 文脈自由文法と プッシュダウンオートマトン
9.NP完全問題とNP困難問題.
データ構造と アルゴリズム 知能情報学部 新田直也.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
プログラミング言語論 第1回 導入 情報工学科 篠埜 功.
コンパイラ 2012年10月15日
10.通信路符号化手法2 (誤り検出と誤り訂正符号)
東京工科大学 コンピュータサイエンス学部 亀田弘之
7.時間限定チューリングマシンと   クラスP.
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
形式言語とオートマトン2013 ー有限オートマトンー 第5日目
形式言語とオートマトン2008 ー有限オートマトンー
計算の理論 II NP完全 月曜5校時 大月美佳 平成17年1月17日 佐賀大学理工学部知能情報システム学科.
形式言語の理論 5. 文脈依存言語.
東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン Formal Languages and Automata 第4日目
オートマトンとチューリング機械.
計算の理論 II 言語とクラス 月曜4校時 大月美佳.
計算機構成 第3回 データパス:計算をするところ テキスト14‐19、29‐35
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 II 前期の復習 -有限オートマトン-
計算の理論 I ε-動作を含むNFA 月曜3校時 大月 美佳.
様々な情報源(4章).
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
2007年度 情報数理学.
コンパイラ 2011年10月20日
東京工科大学 コンピュータサイエンス学部 亀田弘之
チューリングマシン 0n1nを受理するチューリングマシン 入力テープ b b b b 状態遷移機械.
平成26年4月22日(火) 東京工科大学 コンピュータサイエンス学部 亀田弘之
計算の理論 I 決定性有限オートマトン(DFA) と 非決定性有限オートマトン(NFA)
第6章-2 計算のモデル オートマトン Turing 機械 計算可能性 1.
文法と言語 ー文脈自由文法とLR構文解析ー
計算の理論 I 非決定性有限オートマトン(NFA)
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
計算の理論 I ー正則表現とFAの等価性ー 月曜3校時 大月 美佳.
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
形式言語とオートマトン 第14回 プッシュダウンオートマトンと全体のまとめ
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
計算の理論 I NFAとDFAの等価性 火曜3校時 大月 美佳 平成16年5月18日 佐賀大学理工学部知能情報システム学科.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
Copyright 2002 守屋悦朗 オートマトンって? (Turing machine) (アニメーションで実行のこと)
コンパイラ 2012年10月11日
オートマトンって? (Turing machine).
非決定性有限オートマトン 状態の有限集合 入力記号の有限集合 注意 動作関数 初期状態 受理状態の有限集合.
参考:大きい要素の処理.
形式言語とオートマトン Formal Languages and Automata 第5日目
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
計算の理論 I ー ε-動作を含むNFA ー 月曜3校時 大月 美佳.
線形符号(10章).
計算の理論 I プッシュダウンオートマトン 月曜3校時 大月 美佳 平成15年7月7日 佐賀大学知能情報システム学科.
計算の理論 II 多テープTuring機械 月曜4校時 大月美佳 平成16年11月29日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
Presentation transcript:

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

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

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

TMの数学的定義 TMは、 の7項組で与えられる。 ここで、 1. は有限集合で、状態を表す。 は有限集合で、入力アルファベットを表す。 1. は有限集合で、状態を表す。   は有限集合で、入力アルファベットを表す。   は有限集合で、テープアルファベットを表す。  は   から        への写像    (         )で、 状態遷移を表す。 を状態遷移関数という。     は、初期状態を表す。     は空白記号を表す。 5. は受理状態の集合を表す。 である。 ここで、

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

TMの様相 TMでは、複数の対象が同時に変更される。 すなわち、一回の遷移で、 ○状態 ○テープ内容、 ○ヘッド位置 の3つが同時に変化する。 これらの3つによってTMの様相が定義される。 また、下のようなTMの様相は、 と記述できる。

TMの状態遷移図例 言語 を受理するTM  を示す。

TMの形式的定義例

TMの計算例 ここでは、TM   が0011を受理する計算を示す。 なお、TMの計算は、TMの様相の列として表される。

TMの例2 言語 を受理するTM   を示す。

TMの計算例2 ここでは、TM   が0000を受理する計算を示す。

練習 言語 について考える。 は文脈自由文法では生成できなかった。 よって、 を認識するDFAおよびPDAは存在しない。 言語                 について考える。 は文脈自由文法では生成できなかった。 よって、   を認識するDFAおよびPDAは存在しない。 しかし、  はTMでは認識可能である。    を認識するTM を作成せよ。

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

多テープTMの状態遷移関数 多テープTMの形式的定義では、 状態遷移関数 を次のように定めればよい。 状態と ヘッドの 遷移後の状態と 状態遷移関数  を次のように定めればよい。 状態と  ヘッドの 読み取り値が決まると、 遷移後の状態と   ヘッドの書き込み値 および移動方向が 定まる。

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

テープ1 テープ2 テープ3 テープ区切りを表す 特別な記号

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

RAMとTMの等価性 多テープを用いてRAMをシミュレートすることができる。 ここでは、厳密な証明はおこなわない。 直感的に、シミュレートが可能であると認識できればよい。 ○アイディア 機能ごとにテープを用意して模倣する。 メモリテープ MAR ワークテープ

5-5.非決定性TM 状態の遷移を非決定的にできるTMを 非決定性チューリングマシン (Non-deterministic Turing Machine,NTM) という。(なお、これまでのTMは、 決定性チューリングマシン (Deterministic Turing Machine,DTM) といわれる。 同一様相から、 2つ以上の状態 遷移が可能なTM

NTMの状態遷移関数 NTMの形式的定義では、 状態遷移関数 を次のように定めればよい。 いくつかの遷移の 状態とヘッドの 可能性のなかで 状態遷移関数  を次のように定めればよい。 いくつかの遷移の 可能性のなかで 都合の良いものに 遷移する。 状態とヘッドの 読み取り値が決まると、

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

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

非決定性TMとTMの等価性 すべてのNTM Nに対して、 それと等価なDTM Dが存在する。 テープ3 証明 入力テープ D シミュレーションテープ アドレステープ

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

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

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

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