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.
1
-
$\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. ♦Commented Mar 28, 2017 at 23:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.)
