1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ $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? $\endgroup$
    – Steven
    Apr 24 '20 at 10:51
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – jumpy123
    Apr 24 '20 at 12:34
  • $\begingroup$ I'm not sure what it means for a state to be rejected. $\endgroup$
    – Yuval Filmus
    Apr 24 '20 at 12:35
  • $\begingroup$ by rejected I mean that it will not be accepted on those states. $\endgroup$
    – jumpy123
    Apr 24 '20 at 12:41
  • $\begingroup$ 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$. $\endgroup$
    – Yuval Filmus
    Apr 24 '20 at 12:42

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.