edited by
13,374 views
53 votes
53 votes

Consider the following problem $X$.

Given a Turing machine $M$ over the input alphabet $\Sigma$, any state $q$ of $M$ and a word $w \in \Sigma^*$, does the computation of $M$ on $w$ visit the state of $q$?

Which of the following statements about $X$ is correct?

  1. $X$ is decidable
  2. $X$ is undecidable but partially decidable
  3. $X$ is undecidable and not even  partially decidable
  4. $X$ is not a decision problem
edited by

1 Answer

Best answer
79 votes
79 votes
$X$ is undecidable but partially decidable.

We have the TM $M$. Just make the state $q$ the final state and make all other final states non-final and get a new TM $M'$. Give input $w$ to $M'$. If $w$ would have taken $M$ to state $q$ (yes case of the problem), our new TM $M'$ would accept it. So, the given problem is partially decidable.

If $M$ goes for an infinite loop and never reaches state $q$ (no case for the problem), $M'$ cannot output anything. This problem is the state entry problem, which like word accepting problem and halting problem is undecidable.
edited by
Answer:

Related questions

21 votes
21 votes
5 answers
2
18 votes
18 votes
2 answers
3
Kathleen asked Sep 14, 2014
5,032 views
Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.
36 votes
36 votes
2 answers
4
Kathleen asked Sep 14, 2014
5,265 views
Construct DFA's for the following languages:$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$$L=\left\{w \mid w \in \{a,b\}^*, \text{ w has ...