Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.