# Why is "Turing machine makes no left move" decidable?

We know that every RE language is accepted by Turing machine. And emptiness, finiteness of every RE language is undecidable. My question is how I check decidability "the Turing machine makes move left or not" among the infinite strings. I have found internet contents but very difficult to understand. I want to understand just intuition which is brief, not the concrete proof.

• At first glance, turing machines making no left move cannot be very complicated since they always read a blank (assuming that we start , as usual , with an emty tape). This might be wrong. If such a machine can be complicated, it is clear that the decision whether the machine makes a left-move is difficult as well. Which references do you have abouth this ? Commented Oct 16, 2021 at 12:50
• @Peter When the machine makes a left-move is difficult as well? Commented Oct 16, 2021 at 12:53
• Of course the machine can jump between many states, but I am not sure whether this can be made complicated enough to lead to "undecidable". If the problem is actually undecidable, it must be possible to make such a machine "arbitary complicated" , otherwise we could decide whether there is a left-move. Commented Oct 16, 2021 at 12:59
• I am not able to imagine a complicated enough machine that does NOT make a left-move, so I wonder how the problem can be undecidable. Commented Oct 16, 2021 at 13:01
• A Turing machine that can only move right is essentially a finite state automaton. Sure it can write to the tape, but that isn't any more powerful than just keeping track of a bit of extra data in the state. Commented Oct 16, 2021 at 13:08

(Note: To avoid complications, my Turing machines always have to move either to the left or to the right; they cannot remain in place. Not using this convention makes the proofs a bit more cumbersome, but doesnt change anything meaningful.)

Theorem: The problem "Given a TM $$T$$ and an input $$w \in \Sigma^*$$, will $$T$$ when run on $$w$$ ever move to the left on the tape?" is decidable.

Proof: A decision procedure starts as follows: We simulate what $$T$$ does on input $$w$$. If we ever see $$T$$ moving to the left, we answer "yes". If we see it halt instead, we answer "no". If neither of these happen, then $$T$$ will eventually have read all of $$w$$ and move on to the blank part of the tape to the right of $$w$$.

From then on, the tape has no impact on what $$T$$ does anymore (as there is always a blank there anyway). We keep simulating $$T$$ for as many further steps as $$T$$ has states. Again, if we see $$T$$ moving to the left, we can answer "yes". If we don't see $$T$$ moving to the left within these extra steps, $$T$$ will never do so - because $$T$$ has already completed the loop it will now follow forever. Thus, we can answer "no" at the end.

Theorem: The problem "Given a TM $$T$$, does there exist an input $$w \in \Sigma^*$$ such that $$T$$ ever moves left when run on $$w$$?" is decidable.

Proof: We inspect the control mechanism of $$T$$, and see whether there is any path from the starting state to transition involving a move to the left at all. If there is no such path, then obviously $$T$$ can never move to the left regardless of the input, and we answer "no". If there is such a path, we can answer "yes". To see this, consider a shortest such path. As $$T$$ would move left for the first time on the end of that path, every symbol it reads is a fresh symbol from the input word. Thus, by letting $$w$$ be whatever $$T$$ needs to read to go along this path, we can make $$T$$ move to the left.

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Oct 18, 2021 at 15:39