Multi-track Turing machine

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A Multitrack 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[edit]

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
  • \Sigma 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[edit]

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 then 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.


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