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

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

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

• Q 状態の有限集合です

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

• B 空白の記号です

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

  δ：Q×X ^k →Q×（X×{Left_shift、Right_shift、No_shift}）^k

  どこにあり k テープの数

• q₀ 初期状態です

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

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