チューリングマシン
テンプレート:出典の明記 チューリングマシン (テンプレート:Lang-en-short) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。
目次
歴史
1936年にイギリスの数学者アラン・チューリングの論文「計算可能数について──決定問題への応用」で発表された。同様の考え方は同年にエミール・ポスト (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。
概要
チューリングの仮想機械は、
- 無限に長いテープ
- その中に格納された情報を読み書きするヘッド
- 機械の内部状態を記憶するメモリ
で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。
- ヘッド位置のテープに情報を書き込む
- 機械の内部状態を変える
- ヘッドを右か左に一つ移動する
上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。
現実の計算との関係
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、算法あるいは算譜をチューリング機械と同一視する（チャーチ＝チューリングのテーゼ）。
数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない（停止性問題）。これはゲーデルの不完全性定理の別表現とみなすことができる。
形式的定義
チューリング機械とは次の<math>7</math>つ組<math>M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle</math>である。
- Q は有限集合であり、その元を状態という。
- Γ は Q に交わらない有限集合であり、字母とよばれる。その元を記号という。
- b は Γ の元であり、空白記号とよばれる。
- Σ は Γ - {b} の部分集合であり、入力字母とよばれる。その元を入力記号という。
- δ は Q × Γ から Q × Γ × {left, right} への写像であり、遷移函数とよばれる。δ(q, a) = (q', a', m) は、「現在の状態が q であり、着目位置にある記号が a であれば、状態を q' に移し、着目位置に記号 a' を書き込んでから、着目位置を m 方向に1つずらす」と読む。
- qinit は Q の元であり、初期状態とよばれる。
- qacc は Q の元であり、受理状態とよばれる。
M の状況とは、<math>\mathit\Gamma \cup Q</math>上の（片側）無限列のうち、Q の元がちょうど1度現れ、また b 以外の記号が有限回しか現れないものをいう。遷移函数 δ は、状況から状況への写像を自然に定める。M が文字列<math>x \in \Sigma ^*</math>を受理するとは、状況<math>q _{\mathrm{init}} x b b \cdots</math>にこの写像を有限回施すことで状況<math>q _{\mathrm{acc}} b b \cdots</math>が得られることをいう。その最小回数を M の x に対する実行時間とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する記憶領域量という。
M が言語<math>L \subseteq \mathit\Sigma ^*</math>を認識するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は帰納可枚挙（recursively enumerable）あるいは計算可枚挙（computably enumerable）であるという。L と<math>\mathit\Sigma ^* \setminus L</math>がともに帰納可枚挙であるとき、Lは帰納的（recursive）あるいは決定可能（decidable）であるという。
より精細に、自然数から自然数への写像 t に対し、M が L を時間計算量［ないし空間計算量］t で認識するとは、M が L を認識し、かつ各<math>x \in L</math>に対する<math>M</math>の実行時間［ないし記憶領域量］が<math>t (\left| x \right|)</math>以下であることをいう。ここで<math>\left| x \right|</math>は文字列 x の長さを表す。
変種
細かい相違
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
- 字母<math>\mathit\Gamma</math>の大きさ（それが<math>\mathit\Sigma</math>を含む有限集合であるかぎり）。
- 遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
- 文字列を受理するさい、テープ上の記号をすべて<math>b</math>にする必要があるか、受理状態へ移るだけでよいか。
- テープが両方向に無限であるか、片側に終端があるか。
- さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
- テープの本数。
空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数<math>\delta</math>を<math>Q \times \mathit\Gamma ^2</math>から<math>Q \times \mathit\Gamma \times \{\mathrm{left}, \mathrm{right}\} ^2</math>への写像とし、状況の定義も適切に変更する。
変換機
言語を認識するだけでなく、<math>\mathit\Sigma ^*</math>から<math>\mathit\Sigma ^*</math>への部分函数<math>f</math>を計算する機械を考えることもできる。すなわち機械<math>M</math>は、各<math>x \in \mathrm{dom} (f)</math>に対しては文字列<math>f (x)</math>をテープに書いてから初めて受理状態へ移り、<math>x \notin \mathrm{dom} (f)</math>に対しては決して受理状態へ移らない。このような<math>M</math>が存在するとき、<math>f</math>は部分帰納的あるいは計算可能（computable）であるという。
決定的と非決定的
遷移関数<math>\delta</math>において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値（すなわちその時にすべき動作）が、高々一つならば、そのチューリングマシンは「決定的」（deterministic）である。これに対し、動作が複数の場合は「非決定的」（non-deterministic）であり、受理の意味も再定義して、非決定性チューリングマシンや乱択チューリングマシンが定義される。
神託つき機械
テンプレート:Main 質問状態を加える。
万能チューリングマシン
遷移規則をうまく構成することで、驚くべきことに、いかなるチューリングマシンであろうとも、それを模倣することが可能なチューリングマシン（万能チューリングマシン）が可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。（エミュレータの原理）
