チューリングマシンの紹介
チューリングマシンは、タイプ0の文法によって生成された言語（帰納的可算集合）を受け入れる受け入れデバイスです。それは1936年にアランチューリングによって発明されました。
定義
チューリングマシン（TM）は、入力が与えられるセルに分割された無限長のテープで構成される数学モデルです。入力テープを読み取るヘッドで構成されています。状態レジスタは、チューリングマシンの状態を格納します。入力シンボルを読み取った後、別のシンボルに置き換えられ、内部状態が変更され、1つのセルから右または左に移動します。TMが最終状態に達すると、入力文字列が受け入れられます。それ以外の場合は拒否されます。
TMは、正式には7タプル（Q、X、∑、δ、q 0、B、F）として記述できます。
Q 状態の有限集合です
X テープアルファベットです
∑ 入力アルファベットです
δ遷移関数です。δ：Q×X→Q×X×{Left_shift、Right_shift}。
q0 初期状態です
B 空白の記号です
F 最終状態のセットです
以前のオートマトンとの比較
次の表は、チューリングマシンが有限オートマトンおよびプッシュダウンオートマトンとどのように異なるかを比較したものです。
| 機械 | スタックデータ構造 | 決定論的？ |
|---|---|---|
| 有限オートマトン | NA | はい |
| プッシュダウンオートマトン | 後入れ先出し（LIFO） | 番号 |
| チューリングマシン | 無限テープ | はい |
チューリングマシンの例
チューリングマシン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 }
δは−で与えられます
| テープアルファベット記号 | 現在の状態 'q 0 ' | 現状 'q 1 ' | 現状 'q 2 ' |
|---|---|---|---|
| a | 1Rq 1 | 1Lq 0 | 1Lq f |
| b | 1Lq 2 | 1Rq 1 | 1Rq f |
ここで遷移1Rq 1は右テープ移動、書き込みシンボルが1であることを意味し、次の状態はqは1。同様に、遷移1Lq 2は、書き込み記号が1である、テープ移動は左に、そして次の状態はQであることを意味する2。
チューリングマシンの時間と空間の複雑さ
チューリングマシンの場合、時間計算量とは、マシンがいくつかの入力シンボルに対して初期化されたときにテープが移動する回数の尺度を指し、スペース計算量は書き込まれたテープのセルの数です。
時間計算量すべての合理的な関数-
T(n) = O(n log n)
TMのスペースの複雑さ-
S(n) = O(n)