# Dual Turing Machine Simulation

(1) Define a Turing Machine that simulates a Dual Turing Machine (DTM)?.

A dual Turing Machine is defined as a Turing Machine with 2 heads and 2 tapes. At every step, the DTM can

• read from either tape
• write to one or both tapes
• move 0/1/2 heads

(2) If this simulator Turing Machine exists, how to prove that a language $L$ is decidable iff there exists a DTM halting on all inputs that accepts exactly those strings in $L$?

Note: So a normal Turing Machine is defined as $M=(Q,\Gamma,b,\Sigma,\delta,q_0,F)$ where

• $Q$ is a finite, non-empty set of states
• $\Gamma$ is a finite, non-empty set of tape alphabet symbols
• $b\in \Gamma$ is the blank symbol
• $\Sigma \in \Gamma\setminus \{b\}$ is the set of input symbols
• $q_0 \in Q$ is the initial state
• $F\subset Q$ is the set of final or accepting states.
• $\delta:(Q\setminus F)\times \Gamma \rightarrow Q\times\Gamma\times \{L,R\}$ is a partial function called the transition function, where L is left shift, R is right shift.

Any help is appreciated. Thank you.