# 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

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.
• 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