GATE CS 2001 Q2.7 — Undecidability

To determine the nature of problem $X$, let us analyze its decidability and partial decidability (recursive enumerability).

1. Undecidability of $X$

We can prove that $X$ is undecidable by reducing the Halting Problem ($HP$) to $X$. The Halting Problem asks whether a Turing machine $M$ halts on input $w$.

• Given any Turing machine $M$ and input $w$, we can construct a modified Turing machine $M'$ that behaves exactly like $M$, except that whenever $M$ is about to halt, $M'$ transitions to a specially designated state $q_{\text{halt}}$.
• Now, $M$ halts on $w$ if and only if $M'$ visits the state $q_{\text{halt}}$ on input $w$.
• If we had a decider for problem $X$, we could use it to decide whether $M'$ visits $q_{\text{halt}}$ on $w$, thereby deciding the Halting Problem.

Since the Halting Problem is undecidable, problem $X$ must also be undecidable.

2. Partial Decidability (Recursive Enumerability) of $X$

A problem is partially decidable if there exists a Turing machine (semi-decider) that halts and accepts when the answer is "Yes", but may run forever when the answer is "No".

• We can construct a Turing machine $T$ that simulates the computation of $M$ on input $w$ step-by-step.
• At each step of the simulation, $T$ checks if the current state of $M$ is $q$.
• If $M$ visits state $q$, $T$ halts and outputs "Yes".
• If $M$ never visits state $q$, the simulation may run forever, and $T$ will not halt.

Since we can always recognize the "Yes" instances in a finite number of steps, the problem $X$ is partially decidable.

Therefore, $X$ is undecidable but partially decidable.