チューリングマシン

チューリングマシン

チューリングマシン (テンプレート:Lang-en-short) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である。

歴史

チューリングの「計算可能数について──決定問題への応用」（1936年）において提示された。同様なものを同年にエミール・ポスト (Emil Post) も独立に発表している。構想の理由、動機についてはポストの論文が明確だが、機械自体に関する記述はチューリングの論文が詳細である。次いで、同時代に提示された他の計算モデルも計算可能性の理論からは同等であることが確認され、チューリング＝チャーチのテーゼはそれらを「計算可能」の定義とすることを提唱した。

概要

ここでは非形式的（直感的）に述べる。理論的には形式的に述べる必要がある。

チューリングマシンには、いわゆるハードウェアに相当するものとして、

1. その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる）とする
2. テープに記号を読み書きするヘッド
3. ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン

がある。

また、ソフトウェアに相当するものとして、以下がある。

1. テープに読み書きされる有限個の種類の記号
2. 最初から（初期状態において）テープにあらかじめ書かれている記号列
3. 有限オートマトンの状態遷移規則群。詳細は次で述べる

この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」（内部状態）と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。

• テープの「現在の場所」に新しい記号を書き込む（あるいは、現在の記号をそのままにしてもよい）
• ヘッドを右か左に一つシークする（あるいは、移動しなくてもよい）
• 有限オートマトンを次の状態に状態遷移させる（同じ状態に遷移してもよい）

さらに、この有限オートマトンには（一般的な有限オートマトンの「受理状態」と同様な）「受理状態」がある。計算可能性理論的には、決定問題の2種類の答えに対応する、2種類の受理状態が必要である。

現実の計算との関係

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

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

形式的な定義

この節では、チューリングマシンを形式的（formal）に記述する。

チューリングマシン

チューリングマシン テンプレート:Mvar は次の7つ組で定義される：

$$M=⟨Q,\mathrm{\Gamma },b,\mathrm{\Sigma },\delta ,q_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}},q_{\mathrm{a}\mathrm{c}\mathrm{c}}⟩.$$

状態

有限集合 テンプレート:Mvar の元 テンプレート:Math2 を状態 (テンプレート:En) という。

字母・記号・文字列

状態集合 テンプレート:Mvar と交わらない有限集合 テンプレート:Mvar を字母（テンプレート:En）といい、字母の元 テンプレート:Math2 を記号 (テンプレート:En) という。重複を許した有限個の記号の列全体からなる集合を テンプレート:Math と表し、その元 テンプレート:Math2 を字母 テンプレート:Mvar の文字列（テンプレート:En）または文（テンプレート:En）という。

空白記号

字母 テンプレート:Mvar のある元を空白記号 (テンプレート:En) と定め、テンプレート:Mvar で表す。

入力字母・入力記号

字母から空白文字を除いた テンプレート:Math2 の部分集合 テンプレート:Mvar を入力字母（テンプレート:En）といい、入力字母の元を入力記号（テンプレート:En）という。

遷移函数

写像 テンプレート:Math2 を遷移函数という。テンプレート:Math2 は、「現在の状態が テンプレート:Mvar であり、着目位置の記号が テンプレート:Mvar であれば、状態を テンプレート:Mvar に移し、着目位置に記号 テンプレート:Mvar を書き込んでから、着目位置を テンプレート:Math2 方向に1つずらす」と読む。

初期状態

状態集合 テンプレート:Mvar のある元 テンプレート:Math を初期状態（テンプレート:En）と定める。

受理状態

状態集合 テンプレート:Mvar のある元 テンプレート:Math を受理状態（テンプレート:En）と定める。

状況

$\mathrm{\Gamma }\cup Q$ 上の（片側）無限列のうち、状態集合 テンプレート:Mvar の元がちょうど1度現れ、また空白 テンプレート:Mvar 以外の記号が有限回しか現れないものをチューリングマシン テンプレート:Mvar の状況（テンプレート:En）という。遷移函数 テンプレート:Mvar は、状況から状況への写像を自然に定める。

受理

「チューリングマシン テンプレート:Mvar が入力文字列 $x\in {\mathrm{\Sigma }}^{*}$ を受理（テンプレート:En）する」とは、チューリングマシン テンプレート:Mvar が初期状態 テンプレート:Math で入力文字列 テンプレート:Mvar が与えられた状況 $q_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}xbb\cdots$ に対し、遷移函数 テンプレート:Mvar を有限回作用させ受理状態 テンプレート:Math へ遷移した状況 $q_{\mathrm{a}\mathrm{c}\mathrm{c}}bb\cdots$ が得られることをいう。

実行時間・記憶領域量

チューリングマシン テンプレート:Mvar が入力文字列 テンプレート:Math2 を受理するまで遷移函数を作用させる最小の回数をチューリングマシン テンプレート:Mvar の入力文字列 テンプレート:Mvar に対する実行時間とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する記憶領域量という。

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

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

変種

細かい相違

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

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

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

変換機

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

決定的と非決定的

遷移関数$\delta$において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値（すなわちその時にすべき動作）が、高々一つならば、そのチューリングマシンは「決定的」（deterministic）である。これに対し、動作が複数の場合は「非決定的」（non-deterministic）であり、受理の意味も再定義して、非決定的チューリングマシンや乱択チューリングマシンが定義される。また、未来と過去を逆にしても決定的であるのが可逆チューリングマシンである。

神託つき機械

テンプレート:Main 質問状態を加える。

万能チューリングマシン

遷移規則をうまく構成することで、「いかなるチューリングマシンであろうとも、それを模倣することが可能なチューリングマシン（万能チューリングマシン）」が可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。（エミュレータの原理）

関連項目

• チューリング完全
• 非決定性チューリングマシン
• コルモゴロフ複雑性
• ライフゲーム
• 停止性問題
• 可逆チューリングマシン
• オートマトン
• ラングトンのアリ

外部リンク

解説

• テンプレート:Wayback - スカラーペディア百科事典「チューリングマシン」の項目。

• テンプレート:MathWorld

その他

• 「ウルフラム氏のチューリングマシン」を20歳の学生が証明