Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Multi-track Turing machine
open-in-new
<h2 id="formal-definition">Formal definition</h2> <p>A multitrack Turing machine with n {\displaystyle n} -tapes can be formally defined as a 6-tuple M = ⟨ Q , Σ , Γ , δ , q 0 , F ⟩ {\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle } , where </p> <ul><li> Q {\displaystyle Q} is a finite set of states;</li> <li> Σ ⊆ Γ ∖ { b } {\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}} is a finite set of <i>input symbols</i>, that is, the set of symbols allowed to appear in the initial tape contents;</li> <li> Γ {\displaystyle \Gamma } is a finite set of <i>tape alphabet symbols</i>;</li> <li> q 0 ∈ Q {\displaystyle q_{0}\in Q} is the <i>initial state</i>;</li> <li> F ⊆ Q {\displaystyle F\subseteq Q} is the set of <i>final</i> or <i>accepting states</i>;</li> <li> δ : ( Q ∖ F × Γ n ) → ( Q × Γ n × { L , R } ) {\displaystyle \delta :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)} is a <a href="/facts/Partial_function/0vJMw0Nm">partial function</a> called the <i>transition function</i>.</li></ul> Sometimes also denoted as δ ( Q i , [ x 1 , x 2 . . . x n ] ) = ( Q j , [ y 1 , y 2 . . . y n ] , d ) {\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)} , where d ∈ { L , R } {\displaystyle d\in \{L,R\}} . <p>A non-deterministic variant can be defined by replacing the transition function δ {\displaystyle \delta } by a <i>transition relation</i> δ ⊆ ( Q ∖ F × Γ n ) × ( Q × Γ n × { L , R } ) {\displaystyle \delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)} . </p> <h2 id="proof-of-equivalency-to-standard-turing-machine">Proof of equivalency to standard Turing machine</h2> <p>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 ⟩ {\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 M = M ′ {\displaystyle M=M'} it must be shown that M ⊆ M ′ {\displaystyle M\subseteq M'} and M ′ ⊆ M {\displaystyle M'\subseteq M} . </p> <ul><li> M ⊆ M ′ {\displaystyle M\subseteq M'} </li></ul> <p>If the second track is ignored then M and M' are clearly equivalent. </p> <ul><li> M ′ ⊆ M {\displaystyle M'\subseteq M} </li></ul> <p>The tape alphabet of a one-track Turing machine equivalent to a two-track Turing machine consists of an <a href="/facts/Ordered_pair/EInLVI0r">ordered pair</a>. The input symbol a of a Turing machine M' can be identified as an ordered pair [ x , y ] {\displaystyle [x,y]} of Turing machine M. The one-track Turing machine is: </p> M = ⟨ Q , Σ × B , Γ × Γ , δ ′ , q 0 , F ⟩ {\displaystyle M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle } with the transition function δ ( q i , [ x 1 , x 2 ] ) = δ ′ ( q i , [ x 1 , x 2 ] ) {\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)} <p>This machine also accepts L. </p> <ul><li>Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269–271</li></ul>