シンプルなturing machineの定義

チューリングマシンMの定義:(Γ, Q, δ)をざっくりまとめた。

• Γ:チューリングマシンが持てるシンボルの集合、アルファベットと呼ぶ。blankシンボル□とstartシンボル▷を含む。
• Q:チューリングマシンの状態の集合。開始状態q_startと終了状態q_haltを含む
• δ:状態遷移関数の集合。Q×Γ^k→Q×Γ^k-1×{L,S,R}^k
  • 各ステップの繊維規則を記述する
  • ある状態Qのときに読んだアルファベットΓから別の状態Qに遷移する
  • L,S,RはLeft Stay Rightの略

状態遷移関数の例

出典

Computational Complexity: A Modern Approach Draftのp16あたり

theory.cs.princeton.edu

Computational Complexity: A Modern Approach