[Math] Determine if a Turing Machine M, on input w, will move its head to the left, at least once

formal-languages

Here is a problem from my formal languages class

Consider the following problem: Determine if a Turing Machine M, on input w, will move its head to the left, at least once.

  1. Is this problem decidable?
  2. Can Rice's theorem be applied on this case?

and here is my attempt to answer (1):

Define M' as a turing machine that takes a pair (M,w) as input, where M is a turing machine encoded in some form recognized by M' and w is the input to M.

M' stops and accepts (M,w) whenever the head of the simulated machine M moves to the left while processing input w

For a particular input to M' (M,w), construct the turing machine P as follows:

  • P executes M' on (M,w)
  • P stops and accepts any input if M' accepts (M,w)

We have reduced the Universal Turing Machine U to P. Since we know that L(U) is not decidable, we conclude that L(P) is not decidable. Consequently, M' is not decidable

As to the applicability of Rice's theorem, I'm not sure…

"Any nontrivial property about the language recognized by a Turing machine is undecidable"

moving the head of the machine is not a property of the language itself, it is a property of the machine…

thoughts, please?

Thanks!

Best Answer

Your idea that Rice's theorem is inapplicable is correct. For the theorem to hold, we want to have whenever $L(M_1)=L(M_2)$, $M_1$ satisfies the property iff $M_2%$ does. This is evidently not true of the property presently under consideration. Think of two machines identifying a regular language (i.e. recognizable in a single pass), but one machine backs up all the way to the left, while the other does not.

But your reduction does not make sense. At a very high level, the point of a reduction is something like: "I know problem $P_1$ is hard. If I could solve problem $P_2$, voila! Here is a method to solve problem $P_1$. But this should not be possible. Therefore, $P_2$ has to be hard." Typically, $P_1$ is the halting problem, and you want $P_2$ to be the "left-mover" problem. So, given an instance of the halting problem, you manufacture an instance of the left-mover problem. If I read your reduction correctly, you're doing it in the opposite direction.

Now, something else is wrong with your solution. The problem is decidable! Here is the algorithm sketch: observe that if $M$ never moves left on $w$, it is making a single pass on the string. Eventually, $M$ finishes reading $w$ (which is of finite length), and starts reading spaces. Now, you simply look at which state $q$ $M$ is in when it finishes reading $w$, and look at the subgraph of states it visits on reading spaces. None of these should ever involve moving to the left.

Related Question