World's most popular travel blog for travel bloggers.

# Turing Machines: decidability and bounds checking

, ,
Problem Detail:

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?

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.