Multitape Turing machine

Turing machines
Machine
Variants
Science

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.[1]

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.[2] Thus, multi-tape machines cannot calculate any more functions than single-tape machines,[3] and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines.

  1. ^ Sipser, Michael (2005). Introduction to the Theory of Computation. Thomson Course Technology. p. 148. ISBN 0-534-95097-3.
  2. ^ Papadimitriou, Christos (1994). Computational Complexity. Addison-Wesley. p. 53. ISBN 0-201-53082-1.
  3. ^ Martin, John (2010). Introduction to Languages and the Theory of Computation. McGraw Hill. pp. 243–246. ISBN 978-0071289429.