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

  • $\begingroup$ By R do you mean Regular Languages? $\endgroup$ Jun 3, 2012 at 14:53
  • $\begingroup$ No, to recursive languages. Thank you for the clarification. $\endgroup$
    – Numerator
    Jun 3, 2012 at 14:58
  • 3
    $\begingroup$ See this question. $\endgroup$ Jun 3, 2012 at 15:02

1 Answer 1


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.

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.