# Is this language semi-decidable?

Let $M_w$ be the DTM encoded by the binary string $w$ and let $$L=\{w\#x\,|\,\text{all states are reached when running }M_w\text{ on }x\}.$$ I've already proved that this language is undecidable (the halting problem can be reduced to this), but is this language semi-decidable? I.e., is there an enumeration of $L$ or a reduction of $L$ to a semi-decidable language?

• @adrianN I have tried somehow relating $L$ to the semi-decidable languages I know (complement of the diagonal language, universal language, halting problem, halting problem on empty tape, special halting problem) fir proving semi-decidability or to the only non-semi-decidable language I know so far (diagonal language) for proving non-semi-decidability. The problem is, I have yet to get a grasp of the concept of reductions... currently I'm getting nowhere with my ideas. Jul 19, 2016 at 15:01
• To prove that it's semi-decidable you can provide a program that always halts if the answer is yes and says no or loops if the answer is no. Jul 19, 2016 at 15:04

$$L'=\{w\#x\#n\,|\,\text{all states are reached when running }M_w\text{ on }x\text{ within |n| steps}\}.$$
Argue that $L'$ is decidable. Then, noting that
$$L=\{w\#x\,|\,\exists n.\ w\#x\#n \in L'\}.$$