チューリングマシン 形式的な定義

ウィキペディア

チューリングマシン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/30 02:39 UTC 版)

形式的な定義

この節では、チューリングマシンを形式的（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}$ 上の（片側）無限列のうち、状態集合 Q の元がちょうど1度現れ、また空白 b 以外の記号が有限回しか現れないものをチューリングマシン M の状況（configuration）という。遷移函数 δ は、状況から状況への写像を自然に定める。

受理

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

実行時間・記憶領域量

チューリングマシン M が入力文字列 x ∈ Σ^* を受理するまで遷移函数を作用させる最小の回数をチューリングマシン 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 の長さを表す。