チューリングマシン

チューリングマシン

チューリングマシン (英: Turing machine) は、アラン・チューリングが﹁計算可能性﹂に関する議論のために提示した抽象機械である。

歴史

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

概要

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

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

(一)その表面に記号を読み書きできるテープ。長さは無制限︵必要になれば順番にいくらでも先にシークできる︶とする

(二)テープに記号を読み書きするヘッド

(三)ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン

がある。

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

(一)テープに読み書きされる有限個の種類の記号

(二)最初から︵初期状態において︶テープにあらかじめ書かれている記号列

(三)有限オートマトンの状態遷移規則群。詳細は次で述べる

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

●テープの﹁現在の場所﹂に新しい記号を書き込む︵あるいは、現在の記号をそのままにしてもよい︶

●ヘッドを右か左に一つシークする︵あるいは、移動しなくてもよい︶

●有限オートマトンを次の状態に状態遷移させる︵同じ状態に遷移してもよい︶

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

現実の計算との関係

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

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

形式的な定義

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

チューリングマシン

チューリングマシン M は次の7つ組で定義される：

$$M=\langle Q,{\mathit {\Gamma }},b,{\mathit {\Sigma }},\delta ,q_{\mathrm {init} },q_{\mathrm {acc} }\rangle \,.$$

状態

有限集合 Qの元 q∈ Qを状態 (state) という。

字母・記号・文字列

状態集合 Qと交わらない有限集合 Γ を字母︵alphabet︶といい、字母の元 a∈ Γ を記号 (symbol) という。重複を許した有限個の記号の列全体からなる集合を Γ^* と表し、その元 x∈ Γ^* を字母 Γ の文字列︵string︶または文︵statement︶という。

空白記号

字母 Γ のある元を空白記号 (blank) と定め、b で表す。

入力字母・入力記号

字母から空白文字を除いた Γ − {b} の部分集合 Σ を入力字母︵input alphabet︶といい、入力字母の元を入力記号︵input symbol︶という。

遷移函数

写像 δ: Q× Γ → Q× Γ × {left, right} を遷移函数という。δ(q, a) = (q′, a′, m) は、﹁現在の状態が qであり、着目位置の記号が aであれば、状態を q′ に移し、着目位置に記号 a′ を書き込んでから、着目位置を m∈ {left, right} 方向に1つずらす﹂と読む。

初期状態

状態集合 Qのある元 q_init を初期状態︵initial state︶と定める。

受理状態

状態集合 Qのある元 q_acc を受理状態︵accepting state︶と定める。

状況

${\textstyle {\mathit {\Gamma }}\cup Q}$${\textstyle {\mathit {\Gamma }}\cup Q}$ 上の︵片側︶無限列のうち、状態集合 Qの元がちょうど1度現れ、また空白 b以外の記号が有限回しか現れないものをチューリングマシン Mの状況︵configuration︶という。遷移函数 δ は、状況から状況への写像を自然に定める。

受理

﹁チューリングマシン Mが入力文字列 ${\textstyle x\in \Sigma ^{*}}$${\textstyle x\in \Sigma ^{*}}$を受理︵accept︶する﹂とは、チューリングマシン Mが初期状態 q_init で入力文字列 xが与えられた状況 ${\textstyle q_{\mathrm {init} }xbb\cdots }$${\textstyle q_{\mathrm {init} }xbb\cdots }$に対し、遷移函数 δ を有限回作用させ受理状態 q_acc へ遷移した状況 ${\textstyle q_{\mathrm {acc} }bb\cdots }$${\textstyle q_{\mathrm {acc} }bb\cdots }$が得られることをいう。

実行時間・記憶領域量

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

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

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

変種

細かい相違

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

●字母${\mathit {\Gamma }}$${\mathit {\Gamma }}$の大きさ︵それが${\mathit {\Sigma }}$${\mathit {\Sigma }}$を含む有限集合であるかぎり︶。

●遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。

●文字列を受理するさい、テープ上の記号をすべて$b$$b$にする必要があるか、受理状態へ移るだけでよいか。

●テープが両方向に無限であるか、片側に終端があるか。

●さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。

●テープの本数。

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

変換機

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

決定的と非決定的

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

神託つき機械

詳細は「神託機械」を参照

質問状態を加える。

万能チューリングマシン

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

脚注

注釈

出典

関連項目

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

外部リンク

解説

• Turing machine （英語） - スカラーペディア百科事典「チューリングマシン」の項目。
• Turing Machines （英語） - スタンフォード哲学百科事典「チューリングマシン」の項目。
• Weisstein, Eric W. "Turing Machine". mathworld.wolfram.com (英語).

その他

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