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

チューリングマシンは、タイプ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)