I am trying to prove that

$\qquad L=\{\langle M\rangle \mid M \text{ is a TM }, \exists w. \text{ in } M(w) \text{ the head moves only right and } M(w)\!\uparrow \}$

is decidable.

I thought about the following solution:
Lets build $\hat{M}$, a TM that will decide L:
M on input $\langle N \rangle$:
1. $\Sigma^{Q+1} $ is decidable so it has an enumerator f.
2. for every word $ w\in\Sigma^{Q+1} $ simulate parallel N on w for |Q|+1 steps:
$\space \space \space$ - if N got to a blank then N moved only right and is stuck in a loop.
3. if all of those words stopped the simulation at a blank accept. else reject.

I am quite sure I am missing something here. Can you help please?

  • $\begingroup$ a quick (incomplete) response: If you are trying to prove $L\in R$, you need to show how to construct a decider for it. It is not clear from your solution if you do that or you assume it exists (which will lead you nowhere). [also, you overload the letter "M", can you edit the question, for better clarity?] $\endgroup$
    – Ran G.
    Jun 24 '15 at 15:37
  • $\begingroup$ edited. I am trying to describe a decider. Not assuming it exists. $\endgroup$
    – BK Tomer
    Jun 24 '15 at 15:53

Your approach is on the right track. It should follow the next ideas:

  1. If there exists such $w$, then, when $M$ reaches the first "blank" after reading $w$ it will be in a state $\tilde q$ that goes right (and then keep going right, no matter the state changes). Finding this $\tilde q$ that satisfied this property (if such exists) can easily be verified for by checking all the states in $Q$ (of the given $M$).

  2. If such $\tilde q$ exists, we need to see if it is reachable after reading some input $w \in \Sigma^*$. The idea you already noticed is that if this happen, then $\tilde q$ will be reachable after processing the end of some word in $\Sigma^{Q+1}$ (or the like). This is simply a pigeonhole argument..

Therefore it is enough to only examine all the words in $\Sigma^{Q+1}$ and check if $M$ on any of them goes only right, and reaches $\tilde q$ when hitting the first blank. Since the number of words in $\Sigma^{Q+1}$ is finite, this is doable in a finite time.

You just need to properly formalize the above ideas as a decider $\hat M$.


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