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
$\begingroup$
$\endgroup$
2
-
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. ♦Commented Nov 10, 2017 at 7:09
-
$\begingroup$ sure, see above $\endgroup$– JoezerCommented Nov 12, 2017 at 12:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$– JoezerCommented Nov 14, 2017 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$– chiCommented Nov 14, 2017 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$– JoezerCommented Nov 20, 2017 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$– chiCommented Nov 20, 2017 at 15:18