Rahul Sharma (Editor)

Multitape Turing machine

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Covid-19

A multi-tape Turing machine is like an ordinary Turing machine with several tapes. Each tape has its own head for reading and writing. Initially the input appears on tape 1, and the others start out blank.

Contents

This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine, no matter how many tapes, can be simulated by a single-tape machine using only quadratically more computation time. Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines.

Formal definition

A k-tape Turing machine can be described as a 6-tuple M = Q , Γ , s , b , F , δ where:

  • Q is a finite set of states
  • Γ is a finite set of the tape alphabet
  • s Q is the initial state
  • b Γ is the blank symbol
  • F Q is the set of final or accepting states
  • δ : Q × Γ k Q × ( Γ × { L , R , S } ) k is a partial function called the transition function, where k is the number of tapes, L is left shift, R is right shift and S is no shift.
  • Two-stack Turing machine

    Two-stack Turing machines have a read-only input and two storage tapes. If a head moves left on either tape a blank is printed on that tape, but one symbol from a "library" can be printed.

    References

    Multitape Turing machine Wikipedia


    Similar Topics
    Zombie Honeymoon
    Morgan Matson
    Pastor Vega
    Topics
     
    B
    i
    Link
    H2
    L