Showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable

Question

How would you go about showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable?

Intuitively my thoughts are that you might be able to show that $\bar{L} = \{\langle M, w \rangle\ |\ M$ moves left at most twice while computing $w \}$ is undecidable as you wouldn't ever be able to definitively know if the machine will move left a third time so it would end up looping instead of rejecting. I don't know if that's on the right track though.

Thanks in advance!

Answer 1

I strongly believe it is decidable, but I found it quite convoluted. I'll give a sketch of proof.

Lemma: Every Turing Machine that doesn't terminate either moves left at some point or is very silly.

Let $M_\leftarrow$ be a TM that never moves left. If $M_\leftarrow$ never moves left, we don't care about what it writes on the tape, because it can only ever read the last symbol it wrote. In particular, we may see $M_\leftarrow$ as a finite transition system which set of states are the pairs $(q \in Q, \sigma \in \Sigma)$ where $q$ is the current state of $M_\leftarrow$ and $\sigma$ is either the last symbol written by $M_\leftarrow$ or the blank symbol if $M_\leftarrow$ just moved to the right. Therefore, checking if the graph of the transition system is cyclic decides whether or not $M_\leftarrow$ terminates, qed.

Theorem: $L$ is decidable.

Let $H$ be the problem of deciding whether or not a machine that never moves left terminates. By the lemma above, there exists a machine $M_H$ that takes as input another machine $M$, some input $x$ and:

• if $M$ never moves left on input $x$, returns $\textsf{YES}$ if $M$ terminates and $\textsf{NO}$ otherwise,
• if $M$ on input $x$ moves left at some point, returns $\textsf{YES}$.

We will show that we can use $M_H$ to construct a family of machines $M_k$ that decides whether or not a machine moves left at least $k$ times. Let $\langle M, x \rangle$ be the input.

First of all, we have $M_k$ construct a universal machine $U$, and use $U$ to compute $M_H$ on input $M$. If the result is $\textsf{NO}$, it means that $M$ never moves left on input $x$: we accept $\langle M, x \rangle$. If the result is $\textsf{YES}$, it means that either $M$ terminates on input $x$ or moves left at some point.

We use $U$ to simulate $M$ on input $x$. After finitely many steps, either $M$ terminates or moves left. In the first case simply accept. If a left move happens, we save the current state of the tape, and return the result of $M_{k-1}$ with the modified tape as input, which is by inductive hypothesis computable, qed.

Answer 2

It is decidable, and this is a sketch for an alternate proof (I leave out MANY details).

You can consider $\bar{ L } = \{ \langle M, w \rangle \mid$ $M$ moves left at most 2 times on $ w \}$, and prove that $\bar{L}$ is decidable.

To show that it is decidable, note that $M$ while scanning $w$ cannot go back and cross more than 2 symbols.

So while scanning symbol $a_i$ at position $i$ of $w$ in state $q_i$:

1. $M$ does more than 2 steps towards the left OR
2. $M$ after at most 5 steps moves right into position $i+1$ and enters a state that only depends on $a_i,a_{i-1},a_{i-2}$

So you can build a DFA $D$ that is equivalent to $M$:

• the state of $M$, the content of the previous 2 cells $a_{i-1}, a_{i-2}$ are stored using internal states: in other words, the state of $D$ is identified by a triple:

$\langle q_i, a_{i-1}, a_{i-2}\rangle \;$ ($q_i$ is a state of $M$)

• the transition table of $D$ is built in this way:

if the current symbol is $a_i$, and the state is $\langle q_i, a_{i-1}, a_{i-2} \rangle$ then simulate $M$ on string

$a_{i-2} a_{i-1} [a_i]$ with head position $i$ and state $q_i$

for at most 5 steps.

If $M$ moves left more than twice enter a special state of $D$ called $q_R$, otherwise if $M$ moves right to position $i+1$, writing symbols $a_{i-1}', a_{i}'$ at positions $i-1,i$, and enters state $q_j$, then the transition of $D$ will be:

$\delta(\langle q_i, a_{i-1}, a_{i-2} \rangle, a_i) \to \langle q_j, a_{i-1}', a_{i}' \rangle$

For the special state $q_R$ (which is the only non-acceptance state) simply set: $\delta( q_R, a ) \to q_R$

If for a pair $\langle q_i, a_{i-1}, a_{i-2} \rangle, a_i$ you find that $M$ halts, then the DFA can enter a special (accepting) state $q_A$ in which $D$ ignores the rest of the input.

Finally you should also consider what happens at the end of $w$, i.e. consider the blank symbol $b$ as a tape symbol for $D$.

In this way you prove that $M$ on $w$ move left more than twice if and only if the DFA $D$ rejects the string $w \; b^k$ (where $k$ is greater than the number of states of $D$) and thus is decidable.