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

Question

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!

Answer 1

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.

Answer 2

The problem is actually decidable. The fault in your solution is that $M'$ can accept $<M>, <w>$ without moving left and $M'$ may never halt simulation $<M>$ on $<w>$ but it might move left. You've missed these 2 cases in your solution.

Now coming to the algorithm to solve this problem.
Case 1) If $M$ halts on $w$ and it never moved left, reject it.
Case 2) If $M$ ever moves left, halt and accept.
Case 3) If $M$ stays on the same location for more than $|Q|.|Γ|$ moves, then it means that a configuration gets repeated again which means $M$ stays on this location forever. So, reject it.
Case 4) Otherwise, in this case, $M$ doesn't get stuck at a location, so it actively moves right. So, after a finite number of steps($< |Q|.|Γ|.|w|$) $M$ crosses the input $w$. So, now it encounters a blank symbol. Suppose it is on a blank symbol with state $q$. In a finite number of steps, it moves right and changes the state to $q'$. If $q' = q$, then that means it is on an infinite loop(and moves right forever). One can easily check that after $|Q|^2.|Γ|$ computations, the state gets repeated for sure. If the tape head crosses w and even after $|Q|^2.|Γ|$ computations, tape head doesn't move left, then it'll never move left. So, reject it.
So, in a finite amount of computation one can determine whether a TM on an input ever moves left or not. So, this is decidable