Neha Patil (Editor)

Multi track Turing machine

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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 a 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.

Contents

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
  • Σ is a finite set of symbols called the tape alphabet
  • Γ ∈ Q
  • q 0 ∈ Q is the initial state
  • F ⊆ Q is the set of final or accepting states.
  • δ : ( Q ∖ F × Σ n ) → ( Q × Σ n × { 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 ∈ { L , R } .

    A non-deterministic variant can be defined by replacing the transition function δ by a transition relation δ ⊆ ( Q ∖ F × Σ n ) × ( Q × Σ n × { 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 ⊆ M' and M' ⊆ M

  • M ⊆ M ′

    • If all but the first track is ignored then M and M' are clearly equivalent.

  • M ′ ⊆ 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 , Σ × B , Γ × Γ , δ ′ , 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

    Multi-track Turing machine Wikipedia
    (Text) CC BY-SA