in Theory of Computation edited by
13,340 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
in Theory of Computation edited by
13.3k views

3 Comments

4
4
0
0
State entry problem.
0
0

1 Answer

79 votes
79 votes
Best answer
$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
by

4 Comments

0
0
Why is this not undecidable ? From what I understand there is still a possibility that M' goes into loop before reaching state q, so we can't even be sure that M' will accept even if w belongs to M'.
1
1

I have a intuition, it is possible that for a particular string we might pass through the state q, as the question just says “visit the state of q”, in the case where we set q state as final, we might ignore cases where we passed through state q to a different state (which was non final state).

So, we might be not considering some cases, whats your opinion sir @Arjun?

0
0
Answer:

Related questions