0
$\begingroup$

I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above.

I've got the problem: $$A_{\mathrm{right}} = \{ \left< M\right> | M \text{ never moves on blank input} \}$$

and I have to prove what it is. I know that it is decidable, because if given an input where there is a blank, then it will enter a halt and will loop there forever and not move, thus it is rejected. Everything else can be accepted. I just don't know how to go about proving this with quantifiers.

Any help would be greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ It can't halt and loop for ever. It could do either, but not both at once. The details of what conditions it does not move on depend on the exact definition of a Turing Machine you are using. Nonetheless you're on the right track, however I'm not clear what you mean by "proving this with quantifiers". $\endgroup$ – Luke Mathieson Feb 6 '15 at 3:16
  • $\begingroup$ Hint: pidgeon-hole principle; what do you know after $q+1$ steps, $q$ the number of states? $\endgroup$ – Raphael Feb 6 '15 at 7:56
  • $\begingroup$ I think we have a case of a user who is not careful with words, i.e., a student. I read "proving with quantifiers" as "prove it so that my teacher will think it's a proof" (versus "I believe it's correct, therefore I have proved it."). Regarding "halt and loop, the OP thinks that once a machine enters the halting state it "keeps going and looping forever" in that state (as opposed to actually not working anymore). That at least is my interpretation. $\endgroup$ – Andrej Bauer Feb 6 '15 at 14:16
1
$\begingroup$

In order to understand what $M$ does on a blank input, one needs only examine its transition function $\delta$. As mentioned in the question, assume the starting state is $q_0$, then there are two options: either $\delta(q_0,\text{blank})$ moves the head (and then we can reject) or it doesn't move the head, which brings us to two other options: either it remains in state $q_0$ (then we can accept, right?) or it moves to another state, say $q_1$.

But, with $q_1$ the same reasoning applies, and as Raphael suggested, we can't go on with this logic forever since the number of states is bounded by $|Q|$. So after $|Q|$ "steps" of the above reasoning we will have a conclusive answer to the question of whether the head moves or not, and we can accept or reject accordingly. Since we were successful at constructing a decider, this question (and hence the induced language $Aright$) is decidable.

$\endgroup$

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.