$ E_ {LBA} $是图灵可识别的语言吗？

Question

我知道$ E_ {LBA} $ = {<M> | L（M）= \ emptyset} $是一种不可判定的语言，但它是否也可识别？似乎它的补码是可识别的，因为它可以枚举所有字符串并查看是否属于该语言。如果两者都是可识别的，则$ E_ {LBA} $将是可判定的，但事实并非如此，这使我认为它无法识别。这是真的？

Answer 1

实际上，接受空语言的所有图灵机器编码的语言是：

• 不可判定的，因为没有TM对语言中的字符串回答是，而对于不在语言中的字符串则没有;
• 共同递归 - 可枚举，因为有一个TM对不在语言中的字符串回答否（使用dovetailing，尝试所有TM上的所有字符串，你最终会对不在语言中的任何字符串回答no）
• 不是递归可枚举（或可识别），因为如果它是，它将是可判定的，因为我们知道它是共同递归可枚举的。