# Decidability Problem [closed]

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 ?

• What do you have so far Feb 13, 2014 at 17:03
• Short version: if you could do this, you could solve the halting problem by running the algorithm for the halting state(s). Feb 13, 2014 at 17:57

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.

• Someone told me that it is semi decidable ! Feb 13, 2014 at 17:26
• 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.
– Nemo
Feb 13, 2014 at 17:30