3
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.