Multi-track Turing machine explained

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 an 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 multitrack Turing machine with

n -tapes can be formally defined as a 6-tupleM = \langle Q, \Sigma, \Gamma, \delta, q _{0,} F \rangle , whereQ is a finite set of states;\Sigma \subseteq \Gamma \setminus\{b\} is a finite set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;\Gamma is a finite set of tape alphabet symbols;q _{0} \in Q is the initial state;F \subseteq Q is the set of final or accepting states;\delta: \left(Q \backslash F x \Gamma ^{n} \right) → \left( Q x \Gamma ^{n} x \{L,R\} \right) is a partial function called the transition function.

Sometimes also denoted as

\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\} .

A non-deterministic variant can be defined by replacing the transition function

\delta by a transition relation \delta \subseteq \left(Q \backslash F x \Gamma ^{n} \right) x \left( Q x \Gamma ^{n} x \{L,R\} \right) .

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 is a two-track Turing machine. To prove it must be shown that M \subseteq M' and M' \subseteq M .M \subseteq M' If the second track is ignored then and 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 can be identified as an ordered pair of Turing machine . The one-track Turing machine is:M = \langle Q, \Sigma x {B}, \Gamma x \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. Addison-Wesley. . Chapter 8.6: Multitape Machines: pp 269–271