Home / Engineering / Theory of Computation / Question


Mr. Dubey • 51.17K Points

Q.) Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?

(A) X is decidable
(B) X is undecidable but partially decidable
(C) X is undecidable and not even partially decidable
(D) X is not a decision problem
Correct answer : Option (A) - X is decidable



Login to discuss.