Question

Given a TM \(M\), a state \(q\), and input \(w\), determine whether computation of \(M\) on \(w\) ever visits state \(q\).

• A. Problem is decidable
• B. Problem is undecidable but partially decidable
• C. Problem is undecidable and not even partially decidable
• D. Problem is not a decision problem

Hint:

If YES instances can be recognized but NO instances may loop forever, the problem is recursively enumerable (partially decidable).

Answer 1

The Correct Option is B

Concept: This is known as a reachability problem for Turing machine configurations.

Step 1: Observe the YES cases.
If state \(q\) is visited, we can simulate \(M\). Eventually we observe the visit and accept.

Step 2: Observe the NO cases.
If state \(q\) is never visited and the machine loops forever, we may never know. Thus no algorithm can always halt and answer NO.

Step 3: Classification.
Hence the problem is \[ \text{Undecidable} \] but \[ \text{Partially Decidable}. \]