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$
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$
    – adrianN
    Jul 19, 2016 at 15:04

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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