• 作成日時:
  • 更新日時:

計算理論(チューリング機械)

ついに有限オートマトンからチューリングマシンに入りました.アラン・チューリングはよく計算機のない時代にチューリングマシンなんて思いつきましたね.天才か?(天才です)

計算機で解ける問題はチューリングマシンで解ける.

チューリングマシンと有限オートマトンの違い

  • チューリングマシンはテープに対し書き込みと読み出しのどちらも可能
  • ヘッドは左右どちらにも動くことが出来る
  • テープの長さは無限である
  • チューリングマシンは,停止状態に入ると直ちに停止する

真面目に有限オートマトンとチューリングマシンを対比させて考えたことが無かったですが,そう言えば有限オートマトンの入力はチューリングマシンのテープとして考えることもできますね.

チューリングマシンのテープの記述が非常に面倒くさい.手書きだと前のテープのコピーを書けないので特に面倒くさいですね.チューリングマシンはテープの一部を変更するのに,紙に手書きだと他の変更されていないテープを一々全部書く必要があって面倒です.私の書き方がおかしい気がします.差分を書くだけで十分な記法を考えるべきですね…

今回のチューリングマシンは遷移関数が\(Q * Γ → Q * Γ * \{L, R\}\)で,ヘッダの移動命令を返り値の\(\{L, R\}\)で表します.なので,状態を変更するだけで,ヘッダを動かさないという命令がこのモデルのチューリングマシンでは無いことに気がつきました.