# Proving that it's decidable whether a TM ever moves on the blank input

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.

• 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". – Luke Mathieson Feb 6 '15 at 3:16
• Hint: pidgeon-hole principle; what do you know after $q+1$ steps, $q$ the number of states? – Raphael Feb 6 '15 at 7:56
• 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. – Andrej Bauer Feb 6 '15 at 14:16

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.