Deciding on decidability of a problem and reducing it to halting problem if not decidable

Question

Given are two following languages:

$L_1 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$

$L_2 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$

Are the languages decidable/undecidable/semi-decidable?

The intuition tells me that both languages cannot be decidable, for the simple reason that if any of them ends up in a loop, it can never be decided whether all states were visited. Is my way of thinking correct in both cases?

I would also say that $L_1$ is semi-decidable - in case all states were visited after some finite number of steps, we could decide the language and if not, we still won't be able to say anything about it.

Is it possible to reduce the halting problem to this problem to prove that it's not decidable?

Thank you!

Answer 1

The first language is semidecidable while the second one is not semidecidable.

Claim 1: $L_1 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$ is semidecidable.
Proof: On input $w\#x$ Simply simulate $M_w$ on $x$ and count the number of visited states. If the counter reaches $|Q|$ then ACCEPT. This shows $L_1$ is semidecidable/RE.

Claim 2: $L_2 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$ is not semidecidable.
Proof: Let $L_2$ be semidecidable. Then since $\overline{L}_1 = L_2$, i.e., $L_1$ and $L_2$ are complement of each other, $L_1$ (and so $L_2$) is decidable. In this case we can reduce the Halting problem to $L_1$ as following. Let $M$ be a Turing machine deciding $L_1$. We construct a Turing machine that decides the Halting problem. On input $w\#x$ we modify $M_w$ so that when $M$ halts, it first traverses all other states and then halts. We could do it by changing the ACCEPT state to a normal state, introducing a new ACCEPT state, and adding the following new transitions $$\delta(q_1, a) = q_2, \dots, \delta(q_n, a) = q_{new-accept}$$ where $a$ is a new alphabet symbol and when the modified $M_w$ is at the state $q_{old-accept}$ it first writes $a$ on the tape and enters the state $q_1$ (without moving the head, i.e, the head always reads $a$). Similarly for the the REJECT state. Thus $M_w(x)$ halts if and only if $M_w$ visits all states, which is decidable by $M$.