マルチトラックチューリングマシン

マルチテープチューリングマシンの特定のタイプであるマルチトラックチューリングマシンには複数のトラックが含まれていますが、すべてのトラックで1つのテープヘッドが読み取りと書き込みを行います。ここでは、1つのテープヘッドがn個のシンボルをnワンステップで追跡します。通常のシングルトラックシングルテープチューリングマシンが受け入れるように、再帰的に列挙可能な言語を受け入れます。

マルチトラックチューリングマシンは、正式には6タプル（Q、X、∑、δ、q ₀、F）として記述できます。

• Q 状態の有限集合です

• X テープアルファベットです

• ∑ 入力アルファベットです

• δ 状態と記号の関係です。

  δ（Q _I、[ ₁、₂、₃、...）=（Qの_J、[B ₁、B ₂、B ₃、...]、Left_shiftまたはRight_shift）

• q₀ 初期状態です

• F 最終状態のセットです

Note −すべてのシングルトラックチューリングマシン用 S、同等のマルチトラックチューリングマシンがあります M そのような L(S) = L(M)。