計算理論の基礎(チューリング機械)

[計算理論]チューリング機械

チューリング機械の特徴

・チューリング機械はテープに大使、書き出しも読み出しもどちらもできる。
・読み書きヘッドは左右どちらでも動く。
・テープは無限長である。
・チューリング機械は拒否や受理に対応する状態に入るとすぐに停止する。

チューリング機械の正式な定義

Turing機械は7個組(Q, Σ, Γ, δ, q0, q_accept, q_reject)である。
\[ 1. Qは状態の集合 \]
\[2. Σは空白文字を含まない入力アルファベット\]
\[3. Γは_(空白)\in ΓかつΣ \subseteq Γであるようなテープアルファベット\]
\[4.δ：q \times Γ \rightarrow Q \times Γ \times \{L,R\}は遷移関数 \]
\[ (L:ヘッドを左へ, R:ヘッドを右へ) \]
\[5. q_0 \in Q は開始状態 \]
\[6. q_{accept} \in Q は受理状態 \]
\[7. q_{rejec t} \in Q はq_{rejec t} \neq q_{accept}であるような拒否状態\]
とする。

\[1.M のテープは左端からnます目まで入力 ω = ω_1,ω_2,...,ω_n \in Σ^* \]
\[2.遷移関数によって記述された規則に従って進行(左端にヘッドがいたとき、Lを示しても動かない) \]
\[3.受理or拒否に入って停止するまで、Mは永遠に動き続ける。\]