1
$\begingroup$

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?

$\endgroup$
  • $\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 '16 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$ – adrianN Jul 19 '16 at 15:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.