0
$\begingroup$

given a turing machine M over the input alphabet $\Sigma $ , any state q of M and a word w $\epsilon\Sigma $* , does the computation of M on w visit the state q ?

Is this problem decidable ?

$\endgroup$
2
  • 1
    $\begingroup$ What do you have so far $\endgroup$
    – G. Bach
    Feb 13, 2014 at 17:03
  • $\begingroup$ Short version: if you could do this, you could solve the halting problem by running the algorithm for the halting state(s). $\endgroup$
    – Patrick87
    Feb 13, 2014 at 17:57

1 Answer 1

3
$\begingroup$

Let P(M,q,w) = "the computation of M on w visit q"

If we suppose P décidable, then the problem P' defined as :

P'(M,w) = w \in L(M)

is decidable.

Proof : This a decision procedure for P'. Let M be a machine and w a word. For each accepting state q of M, we run P(M,q,w). If the answer is "yes" for some q, we return "yes". Otherwise, we return "no".

Since it is well known that P' isn't decidable (Rice theorem), we conclude P isn't decidable.

$\endgroup$
2
  • $\begingroup$ Someone told me that it is semi decidable ! $\endgroup$ Feb 13, 2014 at 17:26
  • 1
    $\begingroup$ Yes, it is semi-decidable. You just need to run M on w with a universal turing machine and return "yes" if you reach state q. $\endgroup$
    – Nemo
    Feb 13, 2014 at 17:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.