multi-track Turing machine

{{technical|date=June 2018}}

{{turing}}

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 , where

  • Q 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 \times \Gamma^n \right) \rightarrow \left( Q \times \Gamma^n \times \{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 \times \Gamma^n \right) \times \left( Q \times \Gamma^n \times \{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 {{mvar|M'}} is a two-track Turing machine. To prove {{tmath|1=M=M'}} it must be shown that M \subseteq M' and M' \subseteq M.

  • M \subseteq M'

If the second track is ignored then {{mvar|M}} and {{mvar|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 {{mvar|M'}} can be identified as an ordered pair {{tmath|[x,y]}} of Turing machine {{mvar|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

{{Reflist}}

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

Category:Turing machine