# Is $L = \{\langle M, w \rangle: \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$ decidable?

I'm trying to find whether

$$L = \{\langle M, w \rangle: \exists q.\ \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$$

is decidable or not.

I don't know how to proceed here. I mean, I have the feeling that I have to know which state $q$ the machine $M$ 'skipped' in order to go ahead. For instance if $q = \text{Accept}$, it means that $M(w) = \text{Reject}$ and I guess that, in this case, $L$ can be shown to be a reduction from $L_{empty}$ (written also $E_{TM}$). So if we assumed that $L$ was decidable $\implies E_{TM}$ is decidable which is not true.

But what about the case where $q \neq \text{Accept}$ state?

• I don't understand the problem. How is $q$ quantified? Does $L$ consist of pairs $\langle M,w \rangle$ in which the machine $M$ doesn't pass through all states (i.e., misses some state) on input $w$? – Yuval Filmus Feb 27 '17 at 0:11
• @YuvalFilmus Yep. If we run the machine $M$ on $w$ then some state was missed. – Jazz Feb 27 '17 at 0:24
• In problems like this, it is usually the case that if you can't think of a way to decide the property, then it is undecidable. – Yuval Filmus Feb 27 '17 at 0:26
• I would try to see if it is possible to modify an arbitrary TM so that it visits almost all the states before starting its real computation. – chi Feb 27 '17 at 12:05

You can prove that $L$ is undecidable using a diagonal argument: Assume $M$ decides $L$. Then, define $\tilde{M}$ as follows: On input $x$, run $M$ on input $\langle x, x \rangle$. If it accepts, go through all states and then halt; otherwise halt without going to some dedicated state $q_0$.
If you now run $\tilde{M}$ on input $\tilde{M}$, it runs $M$ on input $\langle \tilde{M}, \tilde{M} \rangle$. Since $M$ decides $L$, it accepts if and only if $\tilde{M}$ on input $\tilde{M}$ does not go through some state. This contradicts the construction of $\tilde{M}$. Hence, $L$ is not decidable.