1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – Yuval Filmus Feb 27 '17 at 0:11
  • 1
    $\begingroup$ @YuvalFilmus Yep. If we run the machine $M$ on $w$ then some state was missed. $\endgroup$ – Jazz Feb 27 '17 at 0:24
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 27 '17 at 0:26
  • $\begingroup$ 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. $\endgroup$ – chi Feb 27 '17 at 12:05
2
$\begingroup$

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.

$\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.