Multi-track Turing machine

In a standard n-tape Turing machine, n heads move independently along n tracks. In a 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.

Formal definition

A multitrack Turing machine with ${\displaystyle n}$-tapes can be formally defined as a 6-tuple${\displaystyle M=⟨Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F⟩}$, where

• ${\displaystyle Q}$ is a finite set of states;
• ${\displaystyle \mathrm{\Sigma }\subseteq \mathrm{\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 \mathrm{\Gamma }}$ is a finite set of tape alphabet symbols;
• ${\displaystyle q_0\in Q}$ is the initial state;
• ${\displaystyle F\subseteq Q}$ is the set of final or accepting states;
• ${\displaystyle \delta :\left(Q\mathrm{\setminus }F\times {\mathrm{\Gamma }}^n\right)\to \left(Q\times {\mathrm{\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)}$, where ${\displaystyle d\in \{L,R\}}$.

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