Consider the following problem X. Given a Turing machine M over input alphabet…
2001
Consider the following problem X.
Given a Turing machine M over input alphabet Σ, a state q of M, and a word w over Σ, does the computation of M on w visit 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
Attempted by 7 students.
Show answer & explanation
Correct answer: B
The problem asks a yes/no question, so it is a decision problem.
It is partially decidable: simulate M on input w step by step. If the computation ever enters state q, halt and answer yes.
However, if q is never visited, M may either halt without visiting q or run forever. In the running-forever case, the simulation gives no finite certificate for the answer no.
The problem is undecidable because the halting problem can be reduced to it. Given a machine N and input x, construct a machine M that simulates N on x and enters a special state q exactly when N halts. If we could decide whether M visits q, we could decide whether N halts on x, which is impossible.
Therefore, X is undecidable but partially decidable. Hence, option B is correct.