チューリングマシン

チューリングマシン  は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である。

1. 歴史
-----

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

2. 概要
-----

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

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

その表面に記号を読み書きできるテープ。長さは無制限とする
テープに記号を読み書きするヘッド
ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトンがある。

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

テープに読み書きされる有限個の種類の記号
最初からテープにあらかじめ書かれている記号列
有限オートマトンの状態遷移規則群。詳細は次で述べるこの有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。

テープの「現在の場所」に新しい記号を書き込む
ヘッドを右か左に一つシークする
有限オートマトンを次の状態に状態遷移させるさらに、この有限オートマトンには「受理状態」がある。計算可能性理論的には、決定問題の2種類の答えに対応する、2種類の受理状態が必要である。

3. 現実の計算との関係
------------

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

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

4. 形式的な定義
---------

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

チューリングマシン チューリングマシン M}} は次の7つ組で定義される： 状態 有限集合 Q}} の元 1=//q// ∈ //Q//}} を状態  という。 字母・記号・文字列 状態集合 Q}} と交わらない有限集合 Γ}} を字母といい、字母の元 1=//a// ∈ //Γ//}} を記号  という。重複を許した有限個の記号の列全体からなる集合を //Γ//sup と表し、その元 1=//x// ∈ //Γ//sup を字母 Γ}} の文字列または文という。 空白記号 字母 Γ}} のある元を空白記号  と定め、b}} で表す。 入力字母・入力記号 字母から空白文字を除いた 1=//Γ// − mset の部分集合 Σ}} を入力字母といい、入力字母の元を入力記号という。 遷移函数 写像 1=//δ//: //Q// × //Γ// → //Q// × //Γ// × mset を遷移函数という。1=//δ// = }} は、「現在の状態が q}} であり、着目位置の記号が a}} であれば、状態を q′}} に移し、着目位置に記号 a′}} を書き込んでから、着目位置を 1=//m// ∈ mset 方向に1つずらす」と読む。 初期状態 状態集合 Q}} のある元 1=//q//init}} を初期状態と定める。 受理状態 状態集合 Q}} のある元 1=//q//acc}} を受理状態と定める。 状況 上の無限列のうち、状態集合 Q}} の元がちょうど1度現れ、また空白 b}} 以外の記号が有限回しか現れないものをチューリングマシン M}} の状況という。遷移函数 δ}} は、状況から状況への写像を自然に定める。 受理 「チューリングマシン M}} が入力文字列 を受理する」とは、チューリングマシン M}} が初期状態 //q//sub で入力文字列 x}} が与えられた状況 に対し、遷移函数 δ}} を有限回作用させ受理状態 //q//sub へ遷移した状況 が得られることをいう。 実行時間・記憶領域量 チューリングマシン
M}} が入力文字列 1=//x// ∈ //Σ//*}} を受理するまで遷移函数を作用させる最小の回数をチューリングマシン M}} の入力文字列 x}} に対する実行時間とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する記憶領域量という。M が言語 を認識するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は帰納可枚挙あるいは計算可枚挙であるという。L と がともに帰納可枚挙であるとき、Lは帰納的あるいは決定可能であるという。

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

5. 変種
-----

5.1. 細かい相違
----------

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

字母の大きさ。
遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
文字列を受理するさい、テープ上の記号をすべてにする必要があるか、受理状態へ移るだけでよいか。
テープが両方向に無限であるか、片側に終端があるか。
さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
テープの本数。空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数をからへの写像とし、状況の定義も適切に変更する。

5.2. 変換機
--------

言語を認識するだけでなく、からへの部分函数を計算する機械を考えることもできる。すなわち機械は、各に対しては文字列をテープに書いてから初めて受理状態へ移り、に対しては決して受理状態へ移らない。このようなが存在するとき、は部分帰納的あるいは計算可能であるという。

5.3. 決定的と非決定的
-------------

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

5.4. 神託つき機械
-----------

質問状態を加える。

6. 万能チューリングマシン
--------------

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

7. 脚注
-----

7.1. 注釈
-------

7.2. 出典
-------

8. 関連項目
-------

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

9. 外部リンク
--------

解説

その他

[1]