計算理論(チューリング機械)
ついに有限オートマトンからチューリングマシンに入りました. アラン･チューリングはよく計算機のない時代にチューリングマシンなんて思いつきましたね. 天才か?(天才です)
計算機で解ける問題はチューリングマシンで解ける.
チューリングマシンと有限オートマトンの違い
- チューリングマシンはテープに対し書き込みと読み出しのどちらも可能
- ヘッドは左右どちらにも動くことが出来る
- テープの長さは無限である
- チューリングマシンは, 停止状態に入ると直ちに停止する
真面目に有限オートマトンとチューリングマシンを対比させて考えたことが無かったですが, そう言えば有限オートマトンの入力はチューリングマシンのテープとして考えることもできますね.
チューリングマシンのテープの記述が非常に面倒くさい. 手書きだと前のテープのコピーを書けないので特に面倒くさいですね. チューリングマシンはテープの一部を変更するのに, 紙に手書きだと他の変更されていないテープを一々全部書く必要があって面倒です. 私の書き方がおかしい気がします. 差分を書くだけで十分な記法を考えるべきですね…
今回のチューリングマシンは遷移関数がで, ヘッダの移動命令を返り値ので表します. なので, 状態を変更するだけで, ヘッダを動かさないという命令がこのモデルのチューリングマシンでは無いことに気がつきました.
hatena-bookmark