# Turing machines moving left at least once

Is the following language decidable? $$L = \{ \langle M,w \rangle \mid \text{M moves its head left at least once when run on w}\}.$$

I feel like this is a decidable language. But I don't know the algorithm to prove that it is decidable. Any help would be appreciated.

• $L$ is clearly acceptable. Suppose that $\langle M, w \rangle$ never moves its head left, how many different configurations $<q_0, s>$, where $q_0$ is a state, and $s$ is the suffix of the tape starting at the current head position, can $M$ be in? Apr 24 '20 at 10:51

## 1 Answer

Let's assume for simplicity that at each step, the head moves either left or right (but doesn't stay in place).

Suppose that $$M$$ never moves its head left when run on $$w$$. After the machine traverses the length of $$w$$, it reaches a blank cell, and from this point on, will always fall on a blank cell. Therefore the only information that changes from step to step is the current state of the machine. After at most $$|Q|$$ steps (where $$Q$$ is the set of states), the machine will either halt or repeat a state, in which case it enters an infinite loop.

This gives a simple algorithm for deciding your language, that I'll let you spell out.

If the head is also allowed to stay put, the argument becomes a bit more complicated, but the conclusion is identical.

• It means that all the possible states of the turing machine M on which it is reading the blank symbol after w will be rejected as none of these involve moving to the left and rest are accepted. am I correct? Apr 24 '20 at 12:34
• I'm not sure what it means for a state to be rejected. Apr 24 '20 at 12:35
• by rejected I mean that it will not be accepted on those states. Apr 24 '20 at 12:41
• I don't see why. The machine $M$ can perfectly choose to halt, accepting or rejecting, at a fixed number of steps after finishing scanning $w$. Apr 24 '20 at 12:42