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?

  • 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