0
$\begingroup$

Let $M$ be a variant of Turing machine with no working tape but with several heads on input word. Prove that these machines accept exactly the languages in $L$.

Please hint me how to start.

$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 28 '17 at 23:01
1
$\begingroup$

Let $S$ denote the languages accepted by such machines. The question wants you to prove $S=L$.

When you have a complicated-looking task, it often helps to break it down into pieces. So, a first helpful hint on how to break it into pieces: try to prove $S \subseteq L$. Separately, try to prove $L \subseteq S$. (If you still can't solve it, then you're able to ask a more specific question about one or the other of those.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.