Multitape Turing machine

${\displaystyle k}$-tape Turing machine can be formally defined as a 7-tuple ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$, following the notation of a Turing machine:

• ${\displaystyle \Gamma }$ is a finite, non-empty set of tape alphabet symbols;
• ${\displaystyle b\in \Gamma }$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$ is the set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
• ${\displaystyle Q}$ is a finite, non-empty set of states;
• ${\displaystyle q_{0}\in Q}$ is the initial state;
• ${\displaystyle F\subseteq Q}$ is the set of final states or accepting states. The initial tape contents is said to be accepted by ${\displaystyle M}$ if it eventually halts in a state from ${\displaystyle F}$.
• ${\displaystyle \delta$ :(Q\setminus F)\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}} is a partial function called the transition function, where L is left shift, R is right shift.

A ${\displaystyle k}$-tape Turing machine ${\displaystyle M}$, where ${\displaystyle k}$ is the number of tapes assigned, computes as follows. ${\displaystyle M}$ starts in its initial state ${\displaystyle q_{0}}$. This is defined by all tapes having one head starting at the leftmost position, along with an input ${\displaystyle w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}}$ on the leftmost ${\displaystyle n}$ positions of the first tape, all other symbols of every tape being the blank symbol defined by ${\displaystyle b}$. A step for the machine is done by evaluating the transition function. This is done by taking in the current state ${\displaystyle q_{i}\in Q}$ and the set of alphabetic symbols that the heads reside over notated as ${\displaystyle \Gamma ^{k}}$. The transition function takes both of these parameters and outputs the three things necessary for a transition: the new state ${\displaystyle q_{j}\in Q}$ that ${\displaystyle M}$ transitions into, a new set of alphabet symbols ${\displaystyle \Gamma ^{k}}$ that each of the ${\displaystyle k}$ heads will write to their respective cells, and a set of shift instructions ${\displaystyle \{L,R\}^{k}}$ that will instruct each of the heads which direction to move to (left or right one cell) after the new symbols are written. The transition function iterates until ${\displaystyle M}$ enters a final state belonging to the set ${\displaystyle F}$, at which point it halts.

Two-stack Turing machines have a read-only input and two storage tapes. If a head moves left on either tape a blank is printed on that tape, but one symbol from a "library" can be printed.

• Turing machine
• Universal Turing machine
• Alternating Turing machine
• Probabilistic Turing machine
• Turing machine equivalents