Consider the following problem X “Given a Turing Machine M over the input…
2020
Consider the following problem X
“Given a Turing Machine M over the input alphabet Σ any state q of M and word Σ*, does the computation of M on w visit the state q”
Which of the following X is correct?
- A.
X is undecidable but partially decidable
- B.
X is not a decision problem
- C.
X is decidable
- D.
X is undecidable but not even partially decidable
Attempted by 33 students.
Show answer & explanation
Correct answer: A
The State-Entry Problem X asks if a Turing Machine M ever visits a specific state q on input w. It is undecidable because solving it would easily solve the Halting Problem (by making the halting state q). However, it is partially decidable (recursively enumerable) because we can simulate M on w; if it ever enters state q, we can halt and answer "yes". Thus, Option A is correct.