チューリングマシン

チューリングマシンとは、アラン・チューリングによって考え出された仮想上の機械である。仮想上とは言え、現在開発されているコンピュータは全てこのチューリングマシンの考えに則っていると言われる。

概要

基本的に、ある1つの問題を解くものである。入力に対してYesかNoかを返す。例えば、「入力された数は素数か?」「入力された目的地には1日で行けるか?」等。同じ問題でも解く手順は1つとは限らないので、チューリングマシンも手順の数だけ存在する。

チューリングマシンはテープとヘッドによって構成される。テープには予め入力情報が格納されており、ヘッドが順次読み取ることにより実行される。ただ順に読み取るだけでなく、書き込んだり逆方向に進むことも可能。テープは無限の長さを持っている。言うなれば、予定が書かれた手帳を順に読んで実行するようなものである。

定義

チューリングマシンは次のように定義される。

M = (Q,Γ,b,Σ,δ,q_init,q_acc)

記号だけ書かれても訳わからんという方が多いと思うので、テープを手帳、ヘッドを持ち主になぞらえて解説する。

状態

持ち主の状態。厳密にはヘッドの状態ではないが、チューリングマシンはこの「状態」を変化させながら実行される。Qは状態からなる有限集合である。

記号

手帳に読み書きする内容のこと。手帳1ページにつき1つ書かれている。それ自体に具体的な意味があるわけではないが、次の状態を決定する要因である。Γは記号からなる有限集合である。

空白記号

手帳で言えば、何も書かれてないページ。入力はテープの先頭から有限の長さで書かれるが、その終端より後に格納されている。bは空白記号である。

入力記号

予め手帳に書いてある記号。空白記号はこれに属さない。Σは入力記号からなる集合である。

状態遷移関数

現在の状態と読み取った記号から、次の状態を決める関数。何を書き込んで前後どちらに進むかについても決定される。δは状態遷移関数である。

初期状態

持ち主の最初の状態。q_initは初期状態である。

受理状態

問題が解け、Yesに至った状態。いわばグッドエンディング。q_accは受理状態である。ちなみにNoに至った状態を拒否状態という。こちらがバッドエンディングである。

関連動画

関連商品

関連項目

• アルゴリズム
• チューリング完全
• プログラミング関連用語の一覧
• 不完全性定理
• アラン・チューリング

関連リンク

• On Computable Numbers, with an Application to the Entscheidungsproblem - Turing - 1937 - Proceedings of the London Mathematical Society - Wiley Online Library