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

マルチテープチューリングマシンは、複数のテープを使用するチューリングマシンのバリエーションです。各テープには、読み取りと書き込み用の独自のヘッドがあります。最初は、入力がテープ 1 に表示され、他のテープは空白から始まります。^[1]

このモデルは直感的には単一テープモデルよりもはるかに強力に思えますが、テープ数に関係なく、マルチテープマシンは単一テープマシンでシミュレートでき、計算時間は2乗だけかかります。^[2]したがって、マルチテープマシンは単一テープマシンよりも多くの関数を計算することはできません。 ^[3]また、堅牢な複雑性クラス（多項式時間など）は、単一テープマシンとマルチテープマシンの変更によって影響を受けません。

${\displaystyle k}$テープチューリングマシンは、チューリングマシンの表記法に従って、7タプル として正式に定義できます。 ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$

• ${\displaystyle \Gamma }$テープアルファベット記号の有限の空でない集合です。
• ${\displaystyle b\in \Gamma }$空白のシンボルです（計算中のどのステップでもテープ上で無限に出現することが許される唯一のシンボルです）。
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$は入力シンボルの集合、つまり初期のテープ内容に現れることが許可されているシンボルの集合である。
• ${\displaystyle Q}$有限で空でない状態の集合です。
• ${\displaystyle q_{0}\in Q}$初期状態です。
• ${\displaystyle F\subseteq Q}$は、最終状態または受け入れ状態の集合です。テープの初期内容は、最終的に の状態で停止した場合、によって受け入れられたと言われます。${\displaystyle M}$${\displaystyle F}$
• ${\displaystyle \delta :(Q\setminus F)\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}}$は遷移関数と呼ばれる部分関数で、L は左シフト、R は右シフトです。

テープチューリング マシンは次のように計算します。最初に、は最初のテープの左端の位置で入力を受け取ります。最初のテープの残りの部分と他のテープは空白です (つまり、空白のシンボルで埋められています)。すべてのヘッドはテープの左端の位置から開始します。計算が開始されると、遷移関数で記述された規則に従って計算が進行します。計算は受け入れ状態になるまで継続され、その時点で停止します。 ${\displaystyle k}$${\displaystyle M}$${\displaystyle M}$${\displaystyle w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}}$${\displaystyle n}$${\displaystyle M}$

2 スタック チューリング マシンには、読み取り専用入力と 2 つのストレージ テープがあります。いずれかのテープ上でヘッドが左に移動すると、そのテープには空白が印刷されますが、「ライブラリ」からの 1 つのシンボルを印刷できます。

• チューリングマシン
• ユニバーサルチューリングマシン
• 交代チューリングマシン
• 確率的チューリングマシン
• チューリングマシンの同等物