Encyclopedia

Multitape Turing machine

Hypothetical computing device

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated August 4, 2026

A multi-tape Turing machine is a variant of the Turing machine that uses several tapes. Each tape has its own head for reading and writing. Initially, the input appears on tape 1, and the others start out blank.

This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine, no matter how many tapes, can be simulated by a single-tape machine using only quadratically more computation time. That is, any language that be decided in O(t(n)) time by a multitape TM(with t tapes) can be decided in O(t²(n)) by a single-tape TM.

Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines.

01Formal definition

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

$\Gamma$ is a finite, non-empty set of tape alphabet symbols;
$b\in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
$\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;
$Q$ is a finite, non-empty set of states;
$q_{0}\in Q$ is the initial state;
$F\subseteq Q$ is the set of final states or accepting states. The initial tape contents is said to be accepted by $M$ if it eventually halts in a state from $F$ .
$\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 $k$ -tape Turing machine $M$ , where $k$ is the number of tapes assigned, computes as follows. $M$ starts in its initial state $q_{0}$ . This is defined by all tapes having one head starting at the leftmost position, along with an input $w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}$ on the leftmost $n$ positions of the first tape, all other symbols of every tape being the blank symbol defined by $b$ . A step for the machine is done by evaluating the transition function. This is done by taking in the current state $q_{i}\in Q$ and the set of alphabetic symbols that the heads reside over notated as $\Gamma ^{k}$ . The transition function takes both of these parameters and outputs the three things necessary for a transition: the new state $q_{j}\in Q$ that $M$ transitions into, a new set of alphabet symbols $\Gamma ^{k}$ that each of the $k$ heads will write to their respective cells, and a set of shift instructions $\{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 $M$ enters a final state belonging to the set $F$ , at which point it halts.

02Two-stack Turing machine

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.

Watch videos about Multitape Turing machineExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Multitape Turing machine”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Multitape Turing machine

01Formal definition

02Two-stack Turing machine

Sources and credits

Related topics

Turing machine

Universal Turing machine

Alternating Turing machine