I know that $E_{LBA} = \{\langle M \rangle ~ \mid ~ L(M) = \emptyset \}$ is an undecidable language, but is it recognizable (recursively enumerable)? It seems that it's complement is recognizable since we could construct a Turing machine that enumerates all strings and checks if any belong to the language. If both $E_{LBA}$ and its complement were recognizable, then $E_{LBA}$ would be decidable, but it isn't, which leads me to think it isn't recognizable. Is this true?


closed as unclear what you're asking by Yuval Filmus, David Richerby, Evil, hengxin, Gilles Dec 19 '16 at 10:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ That reasoning sounds good! $\endgroup$ – templatetypedef Dec 14 '16 at 14:54
  • 1
    $\begingroup$ Your question already contains the answer. $\endgroup$ – Yuval Filmus Dec 14 '16 at 23:05