前のページ 1/1 次のページ

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

◆ 歴史

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

◆ 概要

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

#無限に長いテープ

#その中に格納された情報を読み書きするヘッド

#機械の内部状態を記憶するメモリ

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

・ヘッドの位置の情報を読みとる

・ヘッドの位置に情報を書き込む

・機械の内部状態を変える

・ヘッドを右か左に一つ移動する

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

◆ 現実の計算との関係

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

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

◆ 形式的定義

チューリング機械とは次の$7$つ組である。

・ Q は有限集合であり、その元を状態という。

・ Γ は Q に交わらない有限集合であり、字母とよばれる。その元を記号という。

・ b は Γ の元であり、空白記号とよばれる。

・ Σ は Γ - の部分集合であり、入力字母とよばれる。その元を入力記号という。

・ δ は Q × Γ から Q × Γ × への写像であり、遷移函数とよばれる。δ(q, a) = (q', a', m) は、「現在の状態が q であり、着目位置にある記号が a であれば、状態を q' に移し、着目位置に記号 a' を書き込んでから、着目位置を m 方向に1つずらす」と読む。

・ q_init は Q の元であり、初期状態とよばれる。

・ q_acc は Q の元であり、受理状態とよばれる。

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

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

より精細に、自然数から自然数への写像 t に対し、M が L を時間計算量[外部リンク] style="color:#5555ff;">空間計算量t で認識するとは、M が L を認識し、かつ各$x\; \backslash in\; L$に対する$M$の実行時間[外部リンク]ないし記憶領域量が$t\; (\backslash left|\; x\; \backslash right|)$以下であることをいう。ここで$\backslash left|\; x\; \backslash right|$は文字列 x の長さを表す。

◆ 変種

◇ 細かい相違

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

・ 字母$\backslash mathit\backslash Gamma$の大きさ(それが$\backslash mathit\backslash Sigma$を含む有限集合であるかぎり)。

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

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

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

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

・ テープの本数。

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

◇ 変換機

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

◇ 決定性と非決定性

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

◇ 神託つき機械

質問状態を加える。

◆ 万能機械

遷移規則をうまく構成することで、驚くべきことにすべてのチューリング機械の動作を再現するチューリング機械(万能チューリング機械)を組み立てることが可能である。万能チューリング機械は与えられた別のチューリング機械の入力記号列を読みこみ、それに従って動く。

また全てのチューリングマシンは万能チューリングマシンであることも証明されている。すなわち究極的にはひとつのコンピュータアーキテクチャだけで事足りるということである。

万能チューリングマシンとはコンピュータで別のコンピュータをシミュレートできる原理であって、ノイマンコンピュータの原理とは無関係である。

ノイマンコンピュータとは本来のチューリングマシンのあらゆる計算を可能にする能力を生かすために、あらゆるコンピュータプログラムを入れ替え可能なストアードプログラムとして次々にメモリに入れ替えて実行させ、実際に、あらゆる計算可能性に近づける工夫である。

◆関連項目

・ コルモゴロフ複雑性

・ ライフゲーム

・ 停止性問題

◆ 外部リンク

◇ 解説

・

・

◇ その他

・ [外部リンク] 「ウルフラム氏のチューリングマシン」を20歳の学生が証明

前のページ 1/1 次のページ

・チューリングマシン page1