Decidable? If a Turing Machine M, on input w, will M ever move its read/write head to the left?

Question

1. If a Turing Machine M, on input w, will M ever move its read/write head to the left?
2. Determine if this violates Rice's Theorem.

1. I think the answer for Q1 is decidable because we can make a Turing Machine that decides the problem as follows:

Step 1: If M halts on w and it never moved left, reject it.

Step 2: If M ever moves left, halt and accept.

Step 3: If M loops forever (some configuration repeats) then reject it

Step 4: Otherwise, reject (M moves right, eventually encounters a blank symbol, and moves right forever, which means that M will never move left. So, reject it.)

2. We proved that for some language L L(M) is decidable. So, we can say that L(M) is Turing-recognizable. The property 'L(M) is Turing-recognizable' is trivial because there does not exist a Turing-recognizable L2 such that L2 does not belong to L. Thus, our problem is decidable with the following decider:

"Step 2: If M ever moves left, halt and accept."

, and this does not violate Rice's Theorem.

Answer 1

I'm afraid that your logic doesn't make sense, since you can't implement Step 1. In order to implement it, you'll have to run $M$ and see if it every halts, but this is impossible, since it's the halting problem.

Nevertheless, the problem is decidable. The details of this argument depend on the exact Turing machine model, but in order to illustrate the basic idea, it suffices to consider the simplest possible model, in which there is only one head, and at each step, it has to move (either one step to the left, or one step to the right). We simulate $M$ for $|w|$ steps. Either it has moved to the left (in which case we know the answer), or otherwise, it has gone past the input.

In the latter case, suppose that the Turing machine is at some state $q$ after $|w|$ steps. Let's say that a state is bad if when $M$ reaches it, if the input under the head is blank, then it moves left. Construct a directed graph in which there is an arrow from $q$ to $p$ if $M$ transitions from $q$ to $p$ when the input under the head is blank. There are three cases:

• The path starting at $q$ reaches a bad state. In this case the head of $M$ will eventually move left.
• The path starting at $q$ reaches a halting state or closes a cycle, in both cases not going through a bad state. In this case the head of $M$ will never move left.

This shows how to decide whether $M$ every moves left upon reading $w$.

---

This might seem to contradict Rice's theorem, but it doesn't. The reason is not what you state — the problem is not trivial: there are pairs $(M,w)$ for which $M$ does move left when running on $w$, and there are other pairs when this doesn't happen. Rather, the property of never moving left is a syntactic property rather than a semantic property: it depends on the Turing machine $M$ instead of on its language $L(M)$.