For a Turing machine $M$ can we decide whether there's an input which at $M(x)$ never moves left?

304 Views Asked by At

After Reading again the answer to this question and the answer to this question,

I am wondering if the language $L=\{\langle M \rangle | M $is a Turing machine and $\exists$ input $x$ such that in $M(x)$running $M$ doesn't move left $\}$ can be decide as well.

Maybe we can use the same method as in the last question above, and somehow locate a path which will lead us to this conclusion, by examining the transitions and etc.

What do you think?

1

There are 1 best solutions below

3
On

This is decidable in almost the same way as in the (second) linked question. The issue here is that the Turing machine is allowed to sit still for a while; but at worst on input of length $n$, if the machine has $k$ states, it must get past the initial input within $nk$ steps. Otherwise it would have to see the same symbol in the same cell twice, i.e. get into a loop.

After running past the input, we look again for a cycle in the transition graph, but now one which starts from a blank symbol, possible writes some symbols while sitting still, and then moves right-or writes a blank symbol without moving.