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

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?

-
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

## 1 Answer

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.

-
Unlike the linked question, here input is not given. You seem to be ignoring that part. – Karolis Juodelė Aug 12 '12 at 10:11
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
You cannot check for any input. The $nk$ becomes infinite. And so your solution seems to be incorrect. – Beginner Jul 9 '14 at 18:33