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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ @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. $\endgroup$– Sora.Jul 19, 2016 at 15:01
-
1$\begingroup$ 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. $\endgroup$– adrianNJul 19, 2016 at 15:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can start by considering this related problem:
$$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'\}.$$
should give you an idea about how to proceed.
