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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.