アンダースタンディングコンピューテーション――単純な機械から不可能なプログラムまで_読書メモ5章

5章 究極の機械

書籍の中に書かれているコードとか、より詳しい説明は極力載せません。
基本的には本の中に出てくる用語の解説等をかいつまんだ感じ・・・
興味を持っていただけたら実際に購入して読んでみることをオススメします。

※自分用メモなので内容は適当なのと、理解が進んでいくうちに追記していく可能性があります
(この記事に限らずこのブログに含まれる内容全てそうですがw)


概要

3章,4章では単純な計算モデル(DFA,NFA,PDA)の能力について調べて、
それらが実用的な計算モデルとしては、まだまだ有用性を損う、大きな制限が
あることを確認した。

1930年代にアラン・チューリングが提唱した、これらの問題に対する
アイディアの設計方法につてい検証していく。


決定性チューリングマシン

スタックの欠点として、格納した後のデータの利用方法に制限があったことが挙げられる。
そうした制限を取り外すことで、機械の能力を高めることができる。

機械に無限の長さの空白のテープを持たせて、機械はテープの任意の場所に
文字を読み書きできるようにする。このテープが入力とストレージの両方の役割を果たす。

この無限の長さのテープにアクセスする有限状態機械を
チューリングマシン(TM: Turing Machine)と呼ぶ。

TMは通常、決定的な規則を持つ機械を指すが、ここではこの機械のことを
決定性チューリングマシン(DTM: Deterministic Turing Machine)と呼ぶ

伝統的なTMではテープヘッド(tape head)を使い、テープ上の特定の
位置を指し、その位置にある文字だけを読み書きすることができる。

計算を1ステップ実行するごとに、テープヘッドを右か左に移動することができる。

テープを入出力とすることで、TMは従来のオートマトン(DFA,NFA,PDA)の
『文字列を受理、もしくは拒否する』という問題を超えた、新しい問題を解決することが可能になる
(例えば入力の2進数をインクリメントする、等)


非決定性チューリングマシンと等価性

DTMと非透過性チューリングマシン(NTM:Nondeterministic Turing Machine)は
等価であることがわかっており、NTMはDTMの能力を超えることはない。

つまりはDTMでNTMをシミュレートすることが可能。


最大の能力

結論からいうと、(現在では)DTMの能力を高める方法はない。
これはDTMがどんな拡張もシミュレートできる能力があるため。

※例として、内部ストレージ、サブルーチン、複数のテープ、多次元のテープを
与えた場合でも能力が変わらないことが説明されています。


汎用機械

この章でシミュレートしてきたTMは、DFA,NFA,PDAに比べて
確かに能力は上がったが、現実世界における大部分のコンピュータの
振る舞いとは異なるように感じるかもしれない。
現代のコンピュータは特定の仕事に特化せず汎用に設計されている。

しかし、TMにはそれだけの能力がある。
テープから機械の記述を読み込んで、シミュレーションさせることが可能。
(特定のタスクを処理するテープを用意して読み込ませるだけ = これは現代の汎用コンピュータに
プログラムを実行させるのと同じ)

TMとテープを用いてTM自身をシミュレートすることも可能。
この機械はTMの規則のインタプリタとして動作し、このような機械のことを
万能チューリングマシン(UTM: Universal Turing Machine)と呼ぶ

※この章の最後にはUTMを構築する際のポイントが記載されています。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です