Multi-track Turing machine

A Multitrack Turing machine is a specific type of multi-tape Turing machine.

In a standard n-tape Turing machine, n heads move independently along n tracks. In an n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in an n-track Turing Machine contains n symbols from the tape alphabet. It is equivalent to the standard Turing machine and therefore accepts precisely the recursively enumerable languages.

A multitrack Turing machine with ${\displaystyle n}${\displaystyle n}-tapes can be formally defined as a 6-tuple${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }, where

• ${\displaystyle Q}${\displaystyle Q} is a finite set of states;
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}} is a finite set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
• ${\displaystyle \Gamma }${\displaystyle \Gamma } is a finite set of tape alphabet symbols;
• ${\displaystyle q_{0}\in Q}${\displaystyle q_{0}\in Q} is the initial state;
• ${\displaystyle F\subseteq Q}${\displaystyle F\subseteq Q} is the set of final or accepting states;
• ${\displaystyle \delta :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}${\displaystyle \delta :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)} is a partial function called the transition function.

Sometimes also denoted as ${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}, where ${\displaystyle d\in \{L,R\}}${\displaystyle d\in \{L,R\}}.

A non-deterministic variant can be defined by replacing the transition function ${\displaystyle \delta }${\displaystyle \delta } by a transition relation ${\displaystyle \delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}${\displaystyle \delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)}.

This will prove that a two-track Turing machine is equivalent to a standard Turing machine. This can be generalized to a n-track Turing machine. Let L be a recursively enumerable language. Let ${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle } be standard Turing machine that accepts L. Let M' is a two-track Turing machine. To prove ⁠${\displaystyle M=M'}${\displaystyle M=M'}⁠ it must be shown that ${\displaystyle M\subseteq M'}${\displaystyle M\subseteq M'} and ${\displaystyle M'\subseteq M}${\displaystyle M'\subseteq M}.

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

If the second track is ignored then M and M' are clearly equivalent.

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

The tape alphabet of a one-track Turing machine equivalent to a two-track Turing machine consists of an ordered pair. The input symbol a of a Turing machine M' can be identified as an ordered pair ⁠${\displaystyle [x,y]}${\displaystyle [x,y]}⁠ of Turing machine M. The one-track Turing machine is:

${\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }${\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle } with the transition function ${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}

This machine also accepts L.

• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269–271

• Turing machine

• Wikipedia articles that are too technical from June 2018
• All articles that are too technical