Contents

Multi-track Turing machine

This article may be too technical for most readers to understand. Please help improve ittomake it understandable to non-experts, without removing the technical details. (June 2018) (Learn how and when to remove this message)

Turing machines
Machine
Turing machine equivalents Turing machine examples Turing machine gallery
Variants
Alternating Turing machine Neural Turing machine Nondeterministic Turing machine Quantum Turing machine Post–Turing machine Probabilistic Turing machine Multitape Turing machine Multi-track Turing machine Symmetric Turing machine Total Turing machine Unambiguous Turing machine Universal Turing machine Zeno machine
Science
Alan Turing Category:Turing machine
v t e

AMultitrack 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[edit]

A multitrack Turing machine with ${\displaystyle n}$-tapes can be formally defined as a 6-tuple${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$, where

• ${\displaystyle Q}$ is a finite set of states;
• ${\displaystyle \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;
• ${\displaystyle \Gamma }$ is a finite set of tape alphabet symbols;
• ${\displaystyle q_{0}\in Q}$ is the initial state;
• ${\displaystyle F\subseteq Q}$ is the set of finaloraccepting states;
• ${\displaystyle \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 ${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}$, where ${\displaystyle d\in \{L,R\}}$.

A non-deterministic variant can be defined by replacing the transition function ${\displaystyle \delta }$ by a transition relation ${\displaystyle \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[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 ${\displaystyle 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 ${\displaystyle M=M'}$ it must be shown that ${\displaystyle M\subseteq M'}$ and ${\displaystyle M'\subseteq M}$.

• ${\displaystyle M\subseteq M'}$

If the second track is ignored then M and M' are clearly equivalent.

• ${\displaystyle 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 ${\displaystyle [x,y]}$ of Turing machine M. The one-track Turing machine is:

${\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$ with the transition function ${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}$

This machine also accepts L.

References[edit]

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