基本的な機械を使って↓を実現した
- 複雑な文字列を認識する方法
- 正規表現にマッチさせる方法
- プログラミング言語をパースする方法 ただ、有限オートマトン、プッシュダウン・オートマトンには大きな制限があり、できないことが多い
自動機械 (automatic machine) の設計方法について
4章では有限オートマトンに、スタックを追加することで計算能力を高めた
-> 任意の情報を格納する必要のある問題を扱えるようになった
無限の長さの空白のテープにアクセスする機械のこと
チューリングマシンは計算をしながら、テープにある文字を読み、必要に応じて上書きすることができる
無限の長さのテープにアクスセスすることで、任意の量のデータを任意の場所に格納することができる
RAMの機能をどのように実現するか
テープ + テープヘッド
-> テープヘッドはテープ上の特定の位置を指す
-> 機械はその位置にある文字だけを読み書きする
-> 計算をするたびにテープヘッドを左右どちらかに１マス移動することができる
コンピュータによって実行される操作を、これ以上分解するのが困難な、基本的で「単純な操作」に分解する
計算のステップごとにある「単純な操作」
- 現在の位置にある文字を読む
- その位置に正しい文字を書く
- ヘッドを左右どちらかに移動する
- 状態を変更する
チューリングマシンにおける決定性
チューリングのとるべき次のアクションは、現在の状態と現在のテープヘッドの下にある文字によって決まる
矛盾がない -> 状態と文字の組み合わせに対して規則を１つだけ持つ
省略がない -> 可能な全ての状況に対して規則を必ず１つもつ 適用できる規則がない場合は、暗黙の行き詰まり状態になる
チューリングマシンのテープを実装する
テープを実装するエレガントな方法は、テープを３つに分解する
- テープヘッドの左側にある全ての文字
- テープヘッドの下にある文字
- テープヘッドの右にある全ての文字 それぞれを個別に格納する
無限に長く、空白で埋められたテープの実現
有限個の空白でない文字を超えてヘッドが動いた時に、その場所に新たな空白を配置する
-> テープヘッドがテープの未踏部分まで動いた時に、テープヘッドの下に空白を表す文字を出現させる
チューリングマシンにおける構成 -> 状態とテープの組み合わせ
チューリングマシンのの規則は、その構成を直接扱うようにして実装する
それぞれの規則は、現在の状態と現在のテープヘッドの下にある文字が期待しているものと一致したときのみ、適用する
規則が適用されたら、機械の構成を更新する
非決定性はチューリングマシンの能力を高めてくれるのか -> Noです
決定性チューリングマシンは、非決定性チューリングマシンをシュミレートする力を持っている
非決定性ユーリングマシンをシュミレートするために
- 構成をキューとしてテープに格納
- 先頭の構成を読んで新しい構成に更新
- キューの後ろに新しい構成を追加
チューリングマシンは小さく効率よくすることはできるが、新しい能力を与えることは不可能
テープヘッドの下にある文字を記憶する -> 特定のタスクの実行が簡単になる
これまで出来なかったことが可能になるわけではない
チューリングマシンの優れた内部ストレージ -> 現在の状態
上限数は予め決めておく必要がある
ステップごとに任意の情報を保持する -> 状態に前に読んだ文字も含めてしまうなど
規則を機械の一部に格納して、必要なときに呼び出す -> 規則集の設計が簡単になる
新しい能力が、加わるわけではない
サブルーチンで可能になること -> 小さなチューリングマシンを繋げて大きなチューリングマシンを構築する
問題 -> チューリングマシンはサブルーチンを実行した後、元の場所に戻ってこれない..
サーブルーチンの実現 -> 使う箇所ごとに規則を複製する
チューリングマシンは、複数のテープを１本にたたみこめる -> テープを追加しても能力は高まらない
畳み込みの実現
- 畳み込む文字と文字の間に空白もじをいれる
- テープヘッドの位置を示すためのマーカーを書いておく
テープを左右だけでなく、上下にも動かせるようにした状態
-> 内部ストレージの特定の場所にアクセスするときに役立つ
-> 文字の大きさを表現できる
２次元の格子は、１次元のテープを２本使うことで再現できる
-> 格子の各業をマーキングしながら１本めのテープに格納
-> マーキングまで来たら次の行までずらす
-> 上下に移動する場合は、行末か行頭までの数を２本目のテープに保存して、オフセット分移動させる
-> ヘッドがはみ出した場合は空行を作成する
２本のテープは１本のテープに畳み込めるため、新しい能力は追加されない
これまでの機械の重大な欠点 -> 規則がハードコードされていて、様々なタスクに適用できない
チューリングマシンは、マシンのシュミレートに必要な情報をテープから読む事が可能
-> その機械がやることをシュミレートすることができる
他の機械をシュミレート可能な機械を、万能チューリングマシン(UTM)という
UTMは任意のチューリングマシンの規則、受理状態、開始構成を読み込み、進行に合わせて構成を繰り返し更新する必要がある
課題 -> 格納できる有限個の状態と有限個の文字を持っており、規則集によって事前に決まっている
- 10種類の文字を扱うUTMは、11種類の文字を扱うチューリングマシンをシュミレートできない
- 特別な意味を持つ文字の衝突 -> エスケープする必要がある 実現するには -> テープ内容をエンコードするスキームを考案する
シュミレートするチューリングマシンの規則を表現するために
- 規則の各パーツをエンコードし、必要なところにセパレータ文字を入れながらテープ上でつなぎ合わせる