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

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?

-
After having received and understood answers to your other questions, you should be able to come with something more here. –  Raphael Aug 12 '12 at 13:57
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.
Not in the second linked question-I should have specified. It becomes a search over all paths of length $nk$ in the transition graph proceeding from the initial state. –  Kevin Carlson Aug 12 '12 at 10:18