1
$\begingroup$

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

$\endgroup$

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.