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