HOME

TheInfoList



OR:

A multi-tape Turing machine is a variant of the Turing machine that utilizes 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. Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust
complexity Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generall ...
classes (such as
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
) are affected by a change between single-tape and multi-tape machines.


Formal definition

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\ 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 computes as follows. Initially, M receives its input w=w_1w_2...w_n \in \Sigma^* on the leftmost 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 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 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.


See also

* Turing machine * Universal Turing machine *
Alternating Turing machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. ...
* Probabilistic Turing machine * Turing machine equivalents


References

Turing machine