チューリングマシン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/11/04 05:34 UTC 版)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。
出典検索^?: "チューリングマシン" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2011年12月）

チューリングマシン

歴史

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

概要

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

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

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

がある。

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

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

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

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

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

現実の計算との関係

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

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

形式的な定義

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

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

Q は有限集合であり、その元を状態という。
Γ は Q に交わらない有限集合であり、字母とよばれる。その元を記号という。
b は Γ の元であり、空白記号とよばれる。
Σ は Γ - {b} の部分集合であり、入力字母とよばれる。その元を入力記号という。
δ は Q × Γ から Q × Γ × {left, 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} }xbb\cdots$ にこの写像を有限回施すことで状況 $q_{\mathrm {acc} }bb\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 の長さを表す。