Is $E_{LBA}$ a Turing recognizable language?

Question

I know that $E_{LBA}$ = {< M > | L(M) = \emptyset }$ is an undecidable language, but is it also recognizable? It seems that it's complement is recognizable since it could enumerate all strings and see if any belong to the language. If both were recognizable, then $E_{LBA}$ would be decidable, but it isn't, which leads me to think it isn't recognizable. Is this true?

Answer 1

Indeed, the language of all Turing-machine encodings which accept the empty language is:

• undecidable, since there is no TM which answers yes for strings in the language and no for strings not in the language;
• co-recursively-enumerable in that there is a TM which answers no for strings not in the language (using dovetailing, try all strings on all TMs and you will eventually answer no for any string not in the language)
• not recursively enumerable (or recognizable) because if it were, it would be decidable given that we know it's co-recursively-enumerable.