Equivalence of 2-tape TM and 1-tape TM:

Theorem:

For any 2-tape TM T, there is a single-tape TM M that for any string a in Σ*:

-   if T stops on a with b on its tape, then M halts on a with b on its tape, and

-   if T does not stop on a, then M does not stop

How 1-tape TM does simulates 2-tape TM

• Marking position of each tape head in content of tape
• Encode content of 2 tapes on 1 tape
• When to convert 1-tape symbol into the 2-tape symbol

• Construct 1-tape TM simulating the transition in 2-tape TM
• Convert the encoding of 2-tape symbols returns back to 1-tape symbols

•  New alphabet contains:

- the old alphabet

- encoding of the symbol on tape 1 and the symbol on tape 2

- encoding of the symbol on tape 1 pointed by its tape h ead and the symbol on tape 2

- encoding of the symbol on tape 1 and a symbol on tape 2 po inted by its tape head

- encoding of the symbol on tape 1 pointed by its tape h ead and the symbol on tape 2 po inted by its tape head

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Equivalence of 2-tape TM and 1-tape TM in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.