multi-track Turing machine

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 an 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-tuple$M= \langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle$, where

* $Q$ is a finite set of states;
* $\Sigma \subseteq \Gamma \setminus\$ 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 \times \Gamma^n \right) \rightarrow \left( Q \times \Gamma^n \times \ \right)$ is a partial function called the ''transition function''.
: Sometimes also denoted as \delta \left(Q_i, _1,x_2...x_nright)=(Q_j, _1,y_2...y_nd), where $d \in \$.

A non-deterministic variant can be defined by replacing the transition function $\delta$ by a ''transition relation'' $\delta \subseteq \left(Q \backslash F \times \Gamma^n \right) \times \left( Q \times \Gamma^n \times \ \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 \times , \Gamma \times \Gamma, \delta ', q_0, F \rangle$ with the transition function \delta \left(q_i, _1,x_2right)=\delta ' \left(q_i, _1,x_2right)

This machine also accepts L.

References

*Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. {{isbn, 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269–271

Turing machine