Multi-track Turing machine

Multi-track Turing machine
Turing machine(s)
Machina
Science
This box: view · Turing machine is a specific type of Multi-tape Turing machine. In a standard n-tape Turing machine, n heads move independently along n tracks. In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in a n-track Turing Machine contains n symbols from the tape alphabet. It is equivalent to the standard Turing machine and therefore accepts precisely the recursively enumerable languages.

Formal definition

A multitape Turing machine can be formally defined as a 6-tuple M= \langle Q, \Sigma, \Gamma,  \delta, q_0, F \rangle , where

  • Q is a finite set of states
  • Σ is a finite set of symbols called the tape alphabet
  • \Gamma \in Q
  • q_0 \in Q is the initial state
  • F \subseteq Q is the set of final or accepting states.
  • \delta \subseteq \left(Q \backslash A \times \Sigma\right) \times \left( Q \times \Sigma \times d \right) is a relation on states and symbols called the transition relation.
  • \delta \left(Q_i,[x_1,x_2...x_n]\right)=(Q_j,[y_1,y_2...y_n],d)

where d \in {L,R}

Proof of equivalency to standard Turing machine

This will prove that a two-track Turing machine is equivalent to a standard Turing machine. This can be generalized to a n-track Turing machine. Let L be a recursively enumerable language. Let M= \langle Q, \Sigma, \Gamma,  \delta, q_0, F \rangle be standard Turing machine that accepts L. Let M' is a two-track Turing machine. To prove M=M' it must be shown that M  \subseteq M' and M'  \subseteq M.

  •  M  \subseteq  M'

If all but the first track is ignored than M and M' are clearly equivalent.

  •  M'  \subseteq  M

The tape alphabet of a one-track Turing machine equivalent to a two-track Turing machine consists of an ordered pair. The input symbol a of a Turing machine M' can be identified as an ordered pair [x,y] of Turing machine M. The one-track Turing machine is:

M= \langle Q, \Sigma \times {B}, \Gamma \times \Gamma,  \delta ', q_0, F \rangle with the transition function \delta \left(q_i,[x_1,x_2]\right)=\delta ' \left(q_i,[x_1,x_2]\right)

This machine also accepts L.

References

Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269-271


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Probabilistic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Квантовая машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Неде …   Википедия

  • Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер …   Википедия

  • Вероятностная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Не …   Википедия

  • History of computing hardware — Computing hardware is a platform for information processing (block diagram) The history of computing hardware is the record of the ongoing effort to make computer hardware faster, cheaper, and capable of storing more data. Computing hardware… …   Wikipedia

  • Conway's Game of Life — Conway game , which redirects to here, can also refer to games as defined by surreal numbers, which John Conway also developed …   Wikipedia

  • Computer — For other uses, see Computer (disambiguation). Computer technology redirects here. For the company, see Computer Technology Limited. Computer …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”