Timeline for Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2018 at 18:58 | answer | added | Nabhan Abdulla | timeline score: 2 | |
| Feb 25, 2018 at 11:18 | history | edited | Raphael |
edited tags
|
|
| Aug 21, 2017 at 4:38 | answer | added | Manu Thakur | timeline score: -2 | |
| Dec 22, 2013 at 10:30 | answer | added | Pétur Ingi Egilsson | timeline score: 0 | |
| May 15, 2013 at 3:00 | review | Community Evaluations | |||
| May 22, 2013 at 3:00 | |||||
| S Apr 3, 2013 at 7:03 | history | post merged (destination) | |||
| Apr 3, 2013 at 7:03 | history | edited | Raphael | CC BY-SA 3.0 |
adds proposition for sake of the merged question.
|
| Mar 30, 2013 at 13:54 | history | tweeted | twitter.com/#!/StackCompSci/status/317998334679859200 | ||
| Mar 30, 2013 at 12:15 | vote | accept | Mahdi | ||
| S Apr 3, 2013 at 7:03 | |||||
| Mar 30, 2013 at 11:25 | answer | added | Me. | timeline score: 10 | |
| Mar 30, 2013 at 10:46 | answer | added | Shaull | timeline score: 9 | |
| Mar 30, 2013 at 5:12 | answer | added | Yuval Filmus | timeline score: 6 | |
| Mar 29, 2013 at 20:59 | history | edited | Ran G. | CC BY-SA 3.0 |
added 23 characters in body; edited tags; edited title
|
| Mar 29, 2013 at 17:18 | history | edited | Shaull | CC BY-SA 3.0 |
added 9 characters in body
|
| Mar 29, 2013 at 17:14 | history | edited | Mahdi | CC BY-SA 3.0 |
added 82 characters in body
|
| Mar 29, 2013 at 17:11 | comment | added | Shaull | @mahdisaeedi: The latter is an entirely different question! You are asking if it is decidable to decide whether a given TM recognizes the empty language - and the answer is no, see Rice's Theorem | |
| Mar 29, 2013 at 17:05 | comment | added | Patrick87 | Sure. From the start state, move into the "halt reject" state, regardless of what's on the input tape. This explicitly accepts every string in the language and rejects every string not in the language. | |
| Mar 29, 2013 at 16:51 | history | edited | Juho | CC BY-SA 3.0 |
edited body; edited title
|
| Mar 29, 2013 at 16:34 | comment | added | Shaull | What have you tried? For example, can you think of a DFA for the empty language? Remember that DFAs can be thought of as very limited TMs. | |
| Mar 29, 2013 at 16:28 | history | asked | Mahdi | CC BY-SA 3.0 |