Automata-theory-multi-tape-turing-machine

マルチテープチューリングマシン

マルチテープチューリングマシンには複数のテープがあり、各テープには別々のヘッドでアクセスします。 各ヘッドは、他のヘッドとは独立して移動できます。 最初は入力はテープ1にあり、その他は空白です。 最初に、最初のテープは入力によって占有され、他のテープは空白のままになります。 次に、マシンはヘッドの下の連続したシンボルを読み取り、TMは各テープにシンボルを印刷し、ヘッドを移動します。

マルチテープチューリングマシン

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

• Q は状態の有限集合です
• X はテープのアルファベットです
• B は空白記号です
• δ*は状態とシンボルの関係です。 +δ：Q×X ^ k ^→Q×（X×\ {Left_shift、Right_shift、No_shift}）^ k ^ + *k 個のテープがある場合
• * q〜0〜*は初期状態です
• F は最終状態のセットです

注-すべてのマルチテープチューリングマシンには、同等のシングルテープチューリングマシンがあります。