Automata-theory-turing-machine-introduction

チューリングマシンの紹介

チューリングマシンは、タイプ0の文法によって生成された言語（再帰的に列挙可能なセット）を受け入れる受け入れデバイスです。 1936年にアランチューリングによって発明されました。

定義

チューリングマシン（TM）は、入力が与えられるセルに分割された無限長のテープで構成される数学モデルです。 入力テープを読み取るヘッドで構成されています。 状態レジスタは、チューリングマシンの状態を格納します。 入力シンボルを読み取った後、別のシンボルに置き換えられ、その内部状態が変更され、1つのセルから右または左に移動します。 TMが最終状態に達すると、入力文字列が受け入れられ、そうでなければ拒否されます。

TMは、正式には7タプル（Q、X、∑、δ、q〜0〜、B、F）として記述できます。

• Q は状態の有限集合です
• X はテープのアルファベットです
• ∑ は入力アルファベットです
• *δ*は遷移関数です。 δ：Q×X→Q×X×\ {左シフト、右シフト}。
• * q〜0〜*は初期状態です
• B は空白記号です
• F は最終状態のセットです

以前のオートマトンとの比較

次の表は、チューリングマシンが有限オートマトンおよびプッシュダウンオートマトンとどのように異なるかを比較したものです。

Machine	Stack Data Structure	Deterministic?
Finite Automaton	N.A	Yes
Pushdown Automaton	Last In First Out(LIFO)	No
Turing Machine	Infinite tape	Yes

チューリングマシンの例

チューリング機械M =（Q、X、∑、δ、q〜0〜、B、F）と

• Q = \ {q〜0〜、q〜1〜、q〜2〜、q〜f〜}
• X = \ {a、b}
• ∑ = \ {1}
• q〜0〜= \ {q〜0〜}
• B =空白記号
• F = \ {q〜f〜}

δは-

Tape alphabet symbol	Present State ‘q0’	Present State ‘q1’	Present State ‘q2’
a	1Rq1	1Lq0	1Lqf
b	1Lq2	1Rq1	1Rqf

ここで、遷移1Rq〜1〜は、書き込みシンボルが1、テープが右に移動し、次の状態がq〜1〜であることを意味します。 同様に、遷移1Lq〜2〜は、書き込みシンボルが1、テープが左に移動し、次の状態がq〜2〜であることを意味します。

チューリングマシンの時間と空間の複雑さ

チューリングマシンの場合、時間の複雑さは、一部の入力シンボルに対してマシンが初期化されたときにテープが移動する回数の測定値を指し、スペースの複雑さは書き込まれたテープのセルの数です。

時間の複雑さすべての合理的な機能-

• T（n）= O（n log n）*

TMのスペースの複雑さ-

• S（n）= O（n）*