Timeline for Is $E_{LBA}$ turing-recognizable?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 20, 2017 at 16:20 | vote | accept | Joezer | ||
| Nov 20, 2017 at 15:18 | comment | added | chi | @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. | |
| Nov 20, 2017 at 14:55 | comment | added | Joezer | 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.) | |
| Nov 14, 2017 at 13:14 | comment | added | chi | @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. | |
| Nov 14, 2017 at 10:38 | comment | added | Joezer | excuse my ignorance, r.e. stand for? | |
| Nov 12, 2017 at 15:58 | history | answered | chi | CC BY-SA 3.0 |