チューリングマシンとは、アラン・チューリングによって考え出された仮想上の機械である。仮想上とは言え、現在開発されているコンピュータは全てこのチューリングマシンの考えに則っていると言われる。
概要
基本的に、ある1つの問題を解くものである。入力に対してYesかNoかを返す。例えば、「入力された数は素数か?」「入力された目的地には1日で行けるか?」等。同じ問題でも解く手順は1つとは限らないので、チューリングマシンも手順の数だけ存在する。
チューリングマシンはテープとヘッドによって構成される。テープには予め入力情報が格納されており、ヘッドが順次読み取ることにより実行される。ただ順に読み取るだけでなく、書き込んだり逆方向に進むことも可能。テープは無限の長さを持っている。言うなれば、予定が書かれた手帳を順に読んで実行するようなものである。
定義
チューリングマシンは次のように定義される。
記号だけ書かれても訳わからんという方が多いと思うので、テープを手帳、ヘッドを持ち主になぞらえて解説する。
状態
持ち主の状態。厳密にはヘッドの状態ではないが、チューリングマシンはこの「状態」を変化させながら実行される。Qは状態からなる有限集合である。
記号
手帳に読み書きする内容のこと。手帳1ページにつき1つ書かれている。それ自体に具体的な意味があるわけではないが、次の状態を決定する要因である。Γは記号からなる有限集合である。
空白記号
手帳で言えば、何も書かれてないページ。入力はテープの先頭から有限の長さで書かれるが、その終端より後に格納されている。bは空白記号である。
入力記号
予め手帳に書いてある記号。空白記号はこれに属さない。Σは入力記号からなる集合である。
状態遷移関数
現在の状態と読み取った記号から、次の状態を決める関数。何を書き込んで前後どちらに進むかについても決定される。δは状態遷移関数である。
初期状態
受理状態
問題が解け、Yesに至った状態。いわばグッドエンディング。qaccは受理状態である。ちなみにNoに至った状態を拒否状態という。こちらがバッドエンディングである。
関連動画
関連商品
関連項目
関連リンク
- 2
- 0pt
- ページ番号: 4907926
- リビジョン番号: 2668716
- 編集内容についての説明/コメント: