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}$ computes as follows. Initially, ${\displaystyle M}$ receives its input ${\displaystyle w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}}$ on the leftmost ${\displaystyle n}$ positions of the first tape, the rest of the first tape as well as other tapes is blank (i.e., filled with blank symbols). All the heads start on the leftmost position of the tapes. Once ${\displaystyle M}$ has started, the computation proceeds according to the rules described by the transition function. The computation continues until it enters the accept states, 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