Given a Turing machine $ M $ over input alphabet $ \Sigma $, a state $ q $ of $ M $, and a word $ w \in \Sigma^* $, does the computation of $ M $ on input $ w $ ever visit state $ q $?
First, observe that $ X $ is a decision problem: for every triple $ \langle M, q, w \rangle $, the answer is either yes (state $ q $ is visited during the computation of $ M $ on $ w $) or no (it is never visited). Hence, the claim that $ X $ is not a decision problem is incorrect.Next, consider whether $ X $ is decidable.
Suppose we try to construct a decider for $ X $. We can simulate $ M $ on input $ w $ step by step, keeping track of the current state. If at any point the current state equals $ q $, we accept. However, if $ M $ never enters $ q $ for example, if it loops forever in other states or halts without ever reaching $ q $—our simulation may run forever without halting. In the case where $ q $ is never visited and $ M $ does not halt, our procedure will not terminate. Therefore, we cannot guarantee halting on all inputs.
This shows that while we can recognize all yes-instances (by simulation), we cannot always recognize no-instances. Thus, $ X $ is not decidable. But as it halts for member its Recognizable ( semi decidable ) but not Recursive (decidable)
Method 2
Reduce the Halting Problem to $ X $.
Recall that the Halting Problem is:
$$
H_{\text{TM}} = \{ \langle M, w \rangle \mid M \text{ halts on input } w \}.
$$
$ H_{\text{TM}} $ is known to be undecidable.
Given an instance $ \langle M, w \rangle $ of the halting problem, construct a new Turing machine $ M' $ that behaves as follows on input $ w $:
- Simulate $ M $ on $ w $.
- If $ M $ halts, enter a distinguished new state $ q_{\text{halt}} $ and then halt.
Note that $ M' $ visits state $ q_{\text{halt}} $ during its computation on $ w $ if and only if $ M $ halts on $ w $.
Now, consider the instance $ \langle M', q_{\text{halt}}, w \rangle $ of problem $ X $. Then:
$$
\langle M, w \rangle \in H_{\text{TM}} \iff \langle M', q_{\text{halt}}, w \rangle \in X.
$$
Thus, a decider for $ X $ would yield a decider for $ H_{\text{TM}} $, contradicting the undecidability of the halting problem. Therefore, $ X $ is undecidable.
However, $ X $ is partially decidable (also called semi-decidable or recursively enumerable). As described earlier, we can simulate $ M $ on $ w $ and accept as soon as state $ q $ is entered. If the answer is yes, this procedure halts and accepts; if the answer is no, it may run forever. This satisfies the definition of a recursively enumerable language.
Hence, $ X $ belongs to the class of undecidable but partially decidable problems.
$$
\color{lime} \boxed{\text{B}}
$$
