-
Consider the following problem X: Given a turing machine M over the input alphabet S, any state q of M and a word W ∈ S *, does the computation of M on W visit the state q? Which of the following statements about X is correct?
-
- X is decidable
- X is undecidable but partially decidable
- X is undecidable and not even partially decidable
- X is not a decision problem
- X is decidable
Correct Option: B
Option (d) is incorrect as the problem is a decision problem. Now, we need to check whether the problem is decidable or not.
The problem is not decidable since the word w ∈ S. Also, the problem is not completely undecidable since, the input and the state is given so after a certain point of time the probability of finding out the answer increases.
