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 = ⟨ Q, Σ, Γ, δ, q_{0}, F ⟩$ , where

$Q$ is a finite set of states;
$Σ \subseteq Γ ∖ {b}$ is a finite set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
$Γ$ 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;
$δ : (Q ∖ F \times Γ^{n}) \to (Q \times Γ^{n} \times {L, R})$ is a partial function called the transition function.

Sometimes also denoted as

δ (Q_{i}, [x_{1}, x_{2} ... x_{n}]) = (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 $δ$ by a transition relation $δ \subseteq (Q ∖ F \times Γ^{n}) \times (Q \times Γ^{n} \times {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 = ⟨ Q, Σ, Γ, δ, q_{0}, F ⟩$ 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 the second 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 = ⟨ Q, Σ \times B, Γ \times Γ, δ^{'}, q_{0}, F ⟩

with the transition function

δ (q_{i}, [x_{1}, x_{2}]) = δ^{'} (q_{i}, [x_{1}, x_{2}])

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