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

Question

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.

Answer 1

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.