$L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }

Question

Is $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input } decidable? What would the proof look like?

Intuitively, I would say it's undecidable: We cannot predict if a given TM ever reaches an accepting transition on a specific input, let alone predicting if it would reach some transition $\delta(q,a) = (p,b,-1)$ on ANY input.

This leads me to another question: Let $L' =$ { $\langle M, w \rangle$ | $M$ moves left on input $w$ }. Is L' decidable? Could two such "versions" of a language, where one version asks about any input and the other about a specific input, differ in decidability?

Answer 1

The language $L'$ is decidable. Consider the operation of a TM $M$ on an input $w$. If $M$ does not move its head to the left when it runs on $w$, then after $|w|-1$ steps, $M$'s head reaches the first blank tape cell and it enters some state $q_1$. When in $q_1$ and $M$ reads a blank, it moves to the right and enters a state $q_2$ (possibly equals $q_1$). Applying the latter considerations again, you get that from $q_2$, $M$ reads a blank symbol, moves its head to the right and enters a state $q_3$, etc. As we're only reading blanks and moving to the right, we will eventually repeat a state and get stuck in a loop of states, and that is guaranteed to happen within at most $|w|-1 + |Q|$ steps of the machine's. In total, we have the following. If $M$ does not move its head to the left upon reading the input $w$, then it enters a loop of states (where it only reads blanks and moves to the right) after at most $|w|-1+|Q|$ steps. Hence, the following algorithm decides $L'$. On input $\langle M, w \rangle$, simulate the run of $M$ on $w$ for at most $|w|-1 + |Q|$ steps, and accept only when $M$ moves its head to the left during the simulation.

Regarding the language $L$, it is also decidable! The idea is as follows. Given a machine $M$, check if there is a path (according to the definition of the transition function) from $q_0$ to a transition that moves the head of the machine to the left. We distinguish between two cases:

1- No such path exist: this case is easy, as it implies that there is no input on which the machine moves its head to the left.

2- Such a path exists: consider a minimal path $p$ from $q_0$ to a Left-transition. As $p$ is minimal, when the machine reads the input word $w$ that is induced by $p$'s transitions, it never moves to the left, and thus we can say for sure that $M$ moves its head to the left on at least one input.

Notes:

• I assumed that the machine moves only to the left or right.

• Your intuition is misleading. Checking if a machine accepts at least one input is undecidable since even if we detect that $q_{acc}$ is reachable, it can be reachable via transitions that can only be used upon reading a specific tape content that we can never reach because what we write on the tape right before moving to the left can change the tape's content in a way that makes it impossible to use some "reachable" transitions.

Answer 2

Concerning the general question Could two such “versions” of a language, where one version asks about any input and the other about a specific input, differ in decidability?:

They sure can. E.g., consider $L=\{\langle M\rangle:\text{$M$ halts}\}$ and $L'=\{\langle M,n\rangle:\text{$M$ halts in $n$ steps}\}$ (where $M$ is a TM with no input). Or, in the other direction: $L=\{w:\text{$w$ is accepted by some TM $M$}\}$ and $L'=\{\langle w,M\rangle:\text{$M$ accepts $w$}\}$.