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

マルチトラック チューリング マシンは、特定の種類のマルチテープ チューリング マシンです。

標準的な n テープ チューリング マシンでは、n 個のヘッドが n 本のトラックに沿って独立して移動します。n トラック チューリング マシンでは、1 つのヘッドがすべてのトラックを同時に読み書きします。n トラック チューリング マシンのテープ位置には、テープ アルファベットの n 個のシンボルが含まれます。これは標準的なチューリング マシンと同等であり、したがって再帰的に列挙可能な言語を正確に受け入れます。

テープを持つマルチトラックチューリングマシンは、6組の として正式に定義することができ、ここで ${\displaystyle n}$${\displaystyle M=\langle Q,\シグマ ,\ガンマ ,\デルタ ,q_{0},F\rangle }$

• ${\displaystyle Q}$有限の状態集合である。
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$は入力シンボルの有限集合、つまり初期テープ内容に現れることが許可されたシンボルの集合である。
• ${\displaystyle \ガンマ}$テープアルファベット記号の有限集合です。
• ${\displaystyle q_{0}\in Q}$初期状態です。
• ${\displaystyle F\subseteq Q}$最終状態または受け入れ状態の集合です。
• ${\displaystyle \delta :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}$は遷移関数と呼ばれる部分関数です。

と表記されることもあります。${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}$${\displaystyle d\in \{L,R\}}$

非決定論的なバリアントは、遷移関数を遷移関係に置き換えることによって定義できます。 ${\displaystyle \delta}$ ${\displaystyle \delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}$

これは、2 トラック チューリング マシンが標準チューリング マシンと同等であることを証明します。これは、n トラック チューリング マシンに一般化できます。L を再帰的に列挙可能な言語とします。L を受け入れる標準チューリング マシンとします。M ' は2 トラック チューリング マシンとします。⁠​​ ⁠ を証明するには、およびを示さなければなりません。 ${\displaystyle M=\langle Q,\シグマ ,\ガンマ ,\デルタ ,q_{0},F\rangle }$${\displaystyle M=M'}$${\displaystyle M\subseteq M'}$${\displaystyle M'\subseteq M}$

• ${\displaystyle M\subseteq M'}$

2 番目のトラックを無視すると、MとM' は明らかに同等になります。

• ${\displaystyle M'\subseteq M}$

2 トラック チューリング マシンと同等の 1 トラック チューリング マシンのテープ アルファベットは、順序付きペアで構成されます。チューリング マシンM'の入力シンボル a は、チューリング マシンMの順序付きペア⁠ ⁠${\displaystyle [x,y]}$として識別できます。1 トラック チューリング マシンは次のとおりです。

${\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$遷移機能付き${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}$

このマシンはLも受け入れます。

• Thomas A. Sudkamp ( 2006)。言語とマシン、第 3 版。Addison-Wesley。ISBN 0-321-32221-5 。第 8.6 章: マルチテープ マシン: pp 269–271