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

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

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

正式な定義

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

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

と表記されることもあります( ) 。

\delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)

d\in \{L,R\}

非決定論的なバリアントは、遷移関数を遷移関係に置き換えることによって定義できます。 $\delta$ $\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トラック・チューリングマシンとします。⁠ ⁠ を証明するには、およびであることを示す必要があります。 $M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle$ $M=M'$ $M\subseteq M'$ $M'\subseteq M$

$M\subseteq M'$

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

$M'\subseteq M$

2トラックチューリングマシンと等価な1トラックチューリングマシンのテープアルファベットは、順序付きペア ⁠ ⁠で構成される。チューリングマシン $M'$ の入力シンボル a は、チューリングマシン $Mの順序付きペア$ ⁠ ⁠ $[x,y]$ として識別できる。1トラックチューリングマシンは以下の通りである。

M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle

遷移機能付き

\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