# Is $E_{LBA}$ turing-recognizable?

I have seen a proof that $E_{LBA}$ is not decidable. But is it at least turing recognizable? How to prove it?

NOTE: $E_{LBA}$ is defined as the emptiness problem for Linear bounded automaton

• Can you edit your question to provide a self-contained definition of $E_{LBA}$? Also, what are your thoughts? What have you tried so far? – D.W. Nov 10 '17 at 7:09
• sure, see above – Joezer Nov 12 '17 at 12:22

I just read the definitions, hence I am not an expert on LBAs, but I think that the non-emptiness problem $\overline{E_{LBA}}$ is r.e., so the emptiness problem $E_{LBA}$ can not be r.e., otherwise it would be decidable.
To see why $\overline{E_{LBA}}$ is r.e., notice that to certify that an $LBA$ has nonempty language it suffices to exhibit a word $w$ and a trace $t$ proving that $w$ is accepted by the $LBA$. So, a semidecider only has to enumerate all such pairs $(w,t)$, and (effectively) check for each pair if it proves the $LBA$'s language nonempty.
• @Joezer I describe above how to build a semidecider. It is a standard result that there is a semidecider iff there is an enumerator: any computability book should have that proof. Anyway, it suffices to enumerate all the triples $(LBA,w,t)$, and when $t$ proves that $w$ is accepted by $LBA$, output the $LBA$ description. – chi Nov 20 '17 at 15:18