2
$\begingroup$

Calling all math buffs! ;)

A Turing machine has two states - one accepting and one non-accepting. Furthermore, the Turing machine cannot overwrite blank symbols. (Note: It's assumed that the blank symbol surrounds the input on the band and isn't itself part of any input string)

Show that the given Turing machine can only accept a regular language.

Could anyone please help me out? I can't come up with anything... (Which is unusual for me!)

Improve this question
$\endgroup$
4
  • $\begingroup$ A first idea can be thinking about that quantity of possible configurations that you can have in your restricted TM is finite. That is because the possible strings that you can have in the non-blank zone of the tape is finite. Think about building a set of states for an DFA/NFA starting from here $\endgroup$
    – ricardorr
    Nov 15 '21 at 21:13
  • $\begingroup$ When does your machine halt? In other words, can you explain the operational semantics of your Turing machine in full? $\endgroup$
    – Yuval Filmus
    Nov 16 '21 at 6:21
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. $\endgroup$
    – D.W. ♦
    Nov 16 '21 at 7:15
  • $\begingroup$ ricardorr - Interesting idea, but it seems like a dead end to me. As the input string gets larger, wouldn't the number of possible configurations increase as well? Yuval Filmus - Unfortunately, the question is deliberately vague. It is a restricted TM, if that helps. D.W. - I guess it's up to you if you want to help. If I knew where to start, then I wouldn't be here, would I? ;) $\endgroup$
    – Andrew Jackson
    Nov 16 '21 at 16:00

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.