チューリングマシン

チューリングマシン $M$ は入力用テープ,テープからデータを読み出す場所を示すヘッド,状態制御部から構成されます.

$a_{1}$$a_{2}$$\cdots$$\cdots$$a_{n}$$\cdots$
ヘッド
状態制御部

$Q$ を状態の空ではない有限集合,$\Gamma$ をチューリングマシン $M$ が計算をする過程において作業用に用いる記号(テープ記号)とします.

ここで,チューリングマシン $M$ が状態 $p \in K$ でヘッドがテープ記号 $a \in \Gamma$ を読み込んで,テープ記号 $a \in \Gamma$ をテープ記号 $b \in \Gamma$ に書き換えて,ヘッドを右に一コマ動かして状態を $q$ に変更するとき,これを,\[\delta(p,a) = (q,b,R)\]と表現します.

同様にして,ヘッドを左に一コマ動かすという場合は,\[\delta(p,a) = (q,b,L)\]と表現します.

$\delta$ は状態遷移関数といい,$K \times \Gamma$ から $K \times \Gamma \times \{L,R\}$ への部分関数となります.

テープの枡目に何も書かれていないことを示す空テープ記号を $\sqcup$(空テープ記号を $B$ で表す場合もあります),$q_{0} \in Q$ を初期状態,$F \subset Q$ は受理状態の集合とすると,チューリングマシン $M$ は,\[M = (Q,\Sigma,\Gamma,\delta,q_{0},\sqcup,F)\]と表されます.

有限オートマトンを,テープの先頭からテープ記号 $\Gamma$ を読み込み,処理と遷移を繰り返す仮想的な機械とみなしたものがチューリングマシンということになります.

チューリングマシンと有限オートマトンの違い

チューリングマシンは,

という点が有限オートマトンやプッシュダウンオートマトンとは相違する点となります.

チューリングマシンとコンピュータ

チューリングマシンは,有限オートマトンやプッシュダウンオートマトンでは認識できなかった言語 $\mathcal{L}$ の認識が可能です.

また,テープと記憶装置を備えているチューリングマシンは,CPUとメモリを備えているコンピュータと計算能力が等しく,コンピュータの基本モデルでもあります.

Vita brevis, ars longa. Omnia vincit Amor.





















エネルギーの原理 状態遷移関数 有限オートマトン 還元可能性 reducibility オートマトン 言語