Automata-theory-multi-track-turing-machine

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

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

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

• Q は状態の有限集合です
• X はテープのアルファベットです
• ∑ は入力アルファベットです
• *δ*は状態とシンボルの関係です。 +δ（Q〜i〜、[a〜1〜、a〜2〜、a〜3〜、…​.]）=（Q〜j〜、[b〜1〜、b〜2〜、b〜 3〜、…​.]、Left_shiftまたはRight_shift）
• * q〜0〜*は初期状態です
• F は最終状態のセットです

注-すべてのシングルトラックチューリングマシン S には、* L（S）= L（M）となる同等のマルチトラックチューリングマシン *M があります。