Timeline for A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 28, 2015 at 16:53 | vote | accept | templatetypedef | ||
| Dec 27, 2015 at 11:28 | answer | added | Andrej Bauer | timeline score: 2 | |
| Nov 25, 2015 at 20:41 | history | tweeted | twitter.com/StackCompSci/status/669616899848855554 | ||
| Nov 25, 2015 at 15:49 | comment | added | vzn | sounds like there could be an interesting question but am finding it hard to identify. it sounds like the proof that every decidable TM's language can be enumerated in lexicographic order. but its the same language! not sure what you mean by "infinite decidable subset". could you point to this proof somewhere? if it is as famous as you say, it ought to be on wikipedia, or some online place. | |
| Nov 25, 2015 at 10:00 | history | edited | Raphael |
edited tags
|
|
| Nov 25, 2015 at 8:58 | answer | added | advocateofnone | timeline score: 0 | |
| Nov 25, 2015 at 8:33 | comment | added | advocateofnone | Sorry as even I am interested in the answer to the question, I would laslty like to ask, say you are able to obtain a decidable subset $D$ in some other way than described by you. But if there still exists an enumerated, on which the basic rule about lexicological order when used gives you $D$, would you be still interested in it ? | |
| Nov 25, 2015 at 6:14 | comment | added | templatetypedef | @sasha While that works, it's basically the same construction as before, and the strings we end up with don't have any particular rhyme or reason to them. I guess I'm hoping for something with a cleaner presentation. | |
| Nov 25, 2015 at 6:10 | comment | added | advocateofnone | What if we start by building an enumerator given the recognizer, by dovetailing ? | |
| Nov 25, 2015 at 6:05 | comment | added | templatetypedef | @sasha That's a good point. Let me rephrase that - right now, we start with an enumerator and extract from it a subsequence that's tough to describe and whose decidability only follows from an auxiliary theorem about enumerators and lexicographical order. It would be nice if there was a more direct and less roundabout way to extract a decidable subset. | |
| Nov 25, 2015 at 1:58 | comment | added | advocateofnone | Sorry I am a bit confused. "A method that does not depend on particulars a specific enumerator's running ", but while only given that a language is Turing recognizable, the only thing we can use is that we can enumerate the strings of the languages it recognizes. So are we not suppose to use the fact that we can enumerate the strings ? Am I missing something ? | |
| Nov 25, 2015 at 0:03 | history | asked | templatetypedef | CC BY-SA 3.0 |