0
$\begingroup$

I am wanting to show that it is decidable that a Turing machine M, on input w, ever attempts to move its head past the right end of the input string w.

I'm assuming I construct a TM which shifts the input on the tape on cell to the left, write the cell at the right-hand end with a new symbol (like "!") that's not in the alphabet for input w. Then add a transition for the head to move left on e cell on reading the extra symbol?

Thoughts?

$\endgroup$
4
$\begingroup$

I can construct a machine $D$ which on input $\langle M,w\rangle$ tells if $M$ moves its head past the right end on input $w$, $D$ accepts if the head does not move past the right end of input, and rejects otherwise. As configurations of length $|w|$ are finite if $M$ ever enters same configuration of length $ \le |w|$ accept. Or if it does not repeat such configuration at some point $M$'s head will move past $|w|$ tape cells. So yes your problem is decidable.

$\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.