チューリングマシン

出典: フリー百科事典『ウィキペディア（Wikipedia）』

チューリングマシン (Turing Machine) は計算模型のひとつ。すなわち、計算機を数学的に議論するための、単純化・理想化された仮想機械である。

[編集] 歴史

1936年にイギリスの数学者アラン・チューリングの論文「計算可能数について──決定問題への応用」で発表された。同様の考え方はチューリングと同年にエミール・ポスト（Emil Post）もチューリングと独立に発表している。なぜそういうことを考えたかについてはポストの論文の方が明確だが、仮想機械自体に関する記述はチューリングの論文の方が詳しい。

[編集] 概要

チューリングマシンの模式図 無限に長い節からできたテープと、テープの節を読み書きするヘッドから構成されている。ヘッドは読み取った節の内容を記憶できる。

チューリングの仮想機械は、

無限に長いテープ
その中に格納された情報を読み書きするヘッド
機械の内部状態を記憶するメモリ

で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。

ヘッドの位置の情報を読みとる
ヘッドの位置に情報を書き込む
機械の内部状態を変える
ヘッドを右か左に一つ移動する

上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。

[編集] 現実の計算との関係

実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、算法あるいは算譜をチューリング機械と同一視する（チャーチ＝チューリングのテーゼ）。

数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない（停止問題）。これはゲーデルの不完全性定理の別表現とみなすことができる。

[編集] 形式的定義

チューリング機械とは次の $7$ つ組 $M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle$ である。

$Q$ は有限集合であり、その元を状態という。
$Γ$ は $Q$ に交わらない有限集合であり、字母とよばれる。その元を記号という。
$b$ は $Γ$ の元であり、空白記号とよばれる。
$Σ$ は $\mathit\Gamma \setminus \{b\}$ の部分集合であり、入力字母とよばれる。その元を入力記号という。
$δ$ は $Q \times \mathit\Gamma$ から $Q \times \mathit\Gamma \times \{\mathrm{left}, \mathrm{right}\}$ への写像であり、遷移函数とよばれる。 $δ(q, a) = (q', a', m)$ は、「現在の状態が $q$ であり、着目位置にある記号が $a$ であれば、状態を $q'$ に移し、着目位置に記号 $a'$ を書き込んでから、着目位置を $m$ 方向に $1$ つずらす」と読む。
$q init$ は $Q$ の元であり、初期状態とよばれる。
$q acc$ は $Q$ の元であり、受理状態とよばれる。

$M$ の状況とは、 $\mathit\Gamma \cup Q$ 上の（片側）無限列のうち、 $Q$ の元がちょうど $1$ 度現れ、また $b$ 以外の記号が有限回しか現れないものをいう。遷移函数 $δ$ は、状況から状況への写像を自然に定める。 $M$ が文字列 $x \in \Sigma ^*$ を受理するとは、状況 $q _{\mathrm{init}} x b b \cdots$ にこの写像を有限回施すことで状況 $q _{\mathrm{acc}} b b \cdots$ が得られることをいう。その最小回数を $M$ の $x$ に対する実行時間とよぶ。その過程における状況中の $q$ の最右位置を、 $M$ が $x$ に対して使用する記憶領域量という。

$M$ が言語 $L \subseteq \mathit\Sigma ^*$ を認識するとは、 $M$ が $L$ の元のみをみな受理することをいう。そのようなチューリング機械 $M$ が存在するとき、 $L$ は帰納可枚挙（recursively enumerable）あるいは計算可枚挙（computably enumerable）であるという。 $L$ と $\mathit\Sigma ^* \setminus L$ がともに帰納可枚挙であるとき、 $L$ は帰納的（recursive）あるいは決定可能（decidable）であるという。

より精細に、自然数から自然数への写像 $t$ に対し、 $M$ が $L$ を時間計算量［ないし空間計算量］ $t$ で認識するとは、 $M$ が $L$ を認識し、かつ各 $x \in L$ に対する $M$ の実行時間［ないし記憶領域量］が $t (\left| x \right|)$ 以下であることをいう。ここで $\left| x \right|$ は文字列 $x$ の長さを表す。

[編集] 変種

[編集] 細かい相違

次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。

字母 $Γ$ の大きさ（それが $Σ$ を含む有限集合であるかぎり）。
遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
文字列を受理するさい、テープ上の記号をすべて $b$ にする必要があるか、受理状態へ移るだけでよいか。
テープが両方向に無限であるか、片側に終端があるか。
さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
テープの本数。

空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数 $δ$ を $Q \times \mathit\Gamma ^2$ から $Q \times \mathit\Gamma \times \{\mathrm{left}, \mathrm{right}\} ^2$ への写像とし、状況の定義も適切に変更する。

[編集] 変換機

言語を認識するだけでなく、 $Σ *$ から $Σ *$ への部分函数 $f$ を計算する機械を考えることもできる。すなわち機械 $M$ は、各 $x \in \mathrm{dom} (f)$ に対しては文字列 $f (x)$ をテープに書いてから初めて受理状態へ移り、 $x \notin \mathrm{dom} (f)$ に対しては決して受理状態へ移らない。このような $M$ が存在するとき、 $f$ は部分帰納的あるいは計算可能（computable）であるという。

[編集] 決定性と非決定性

$δ$ の定義を変えて非決定的にする。さらに受理の意味を変えて、非決定性チューリング機械や乱択チューリング機械が定義される。

[編集] 神託つき機械

質問状態を加える。

[編集] 万能機械

遷移規則をうまく構成することで、驚くべきことにすべてのチューリング機械の動作を再現するチューリング機械（万能チューリング機械）を組み立てることが可能である。万能チューリング機械は入力として与えられたチューリング機械を読みこみ、それに従って動く。この基本設計は現在主流であるノイマン型計算機と変わらない。

[編集] 関連項目

コルモゴロフ複雑性

この項目「チューリングマシン」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（ポータル数学／ウィキプロジェクト数学）

"http://ja.wikipedia.org../../../%E3%83%81/%E3%83%A5/%E3%83%BC/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3.html" より作成