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$.


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.