Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$L=\{<\!M,x\!>\, \mid M's \text{ transition function can only move right and } M\text{ halts on } x \}$. I need to show that $L$ is recursive/decidable.

I thought of checking the encoding of $M$ first and determine whether its transition function moves only right (Can I do that?). If so then try to simulate $M$ on $x$ for $|Q|+1$ steps, if it stops then $<\!M,x\!>\, \in L$ otherwise it is not.

Is this correct?

share|cite|improve this question
By R do you mean Regular Languages? – Dave Clarke Jun 3 '12 at 14:53
No, to recursive languages. Thank you for the clarification. – Numerator Jun 3 '12 at 14:58
See this question. – Dave Clarke Jun 3 '12 at 15:02
up vote 6 down vote accepted

I assume $Q$ is state set of $M$. If so, this runtime bound does not make much sense; in particular, a Turing machine with three states can move to the end of the input and check whether $x$ is an even number; it is clearly not enough to wait three steps.

The next question is whether there is a computable bound on the runtime of halting one-pass machines. Unfortunately, there is not: $M$ might be nondeterministic and halt after an arbitrary amount of steps.

So we determinise $M$ while simulating (that is computable) and look for a bound for all paths. Now we are getting somewhere: after having consumed the input, there are two cases. Either $M$ halts or it enters a loop. As it only moves right (into empty tape), such loops can be detected.

Putting things together, we simulate a determinisation of $M$. We run every branch until $x$ is consumed¹ and then for another $|Q|\cdot|\Sigma_T|$ steps, $Q$ the set of states and $\Sigma_T$ the tape alphabet of $M$. At this point $M$ has either stopped or loops (in this branch), which we detect by a pair of current state and tape symbol occuring for the second time. We only have to check finitely many branches up to a computable bound, therefore $L$ is recursive.

  1. $M$ might loop here already if not moving the head is allowed, but that can be detected, too.
share|cite|improve this answer
See this question. – Dave Clarke Jun 3 '12 at 15:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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