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

  • 2
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Nov 10 '17 at 7:09
  • $\begingroup$ sure, see above $\endgroup$
    – 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.

  • $\begingroup$ excuse my ignorance, r.e. stand for? $\endgroup$
    – Joezer
    Nov 14 '17 at 10:38
  • 1
    $\begingroup$ @Joezer r.e. = RE = recursively enumerable, also known as c.e. = computably enumerable, also known as semi-decidable or recognizable (see en.wikipedia.org/wiki/Recursively_enumerable_language). Way too many names for the same concept. $\endgroup$
    – chi
    Nov 14 '17 at 13:14
  • $\begingroup$ how to you make sure that the Enumerator you depend on exists? (a friend argued the other way around, meaning that in fact Elba is r.e.) $\endgroup$
    – Joezer
    Nov 20 '17 at 14:55
  • $\begingroup$ @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. $\endgroup$
    – chi
    Nov 20 '17 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.