2
$\begingroup$

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?

  • 0
    After having received and understood answers to your other questions, you should be able to come with something more here.2012-08-12

1 Answers 1

1

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.

  • 0
    You cannot check for any input. The $nk$ becomes infinite. And so your solution seems to be incorrect.2014-07-09