Timeline for Why cannot we reduce the Emptiness problem of LBA to the Acceptance problem of LBA?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2017 at 8:30 | vote | accept | O.S. | ||
| Mar 14, 2017 at 8:04 | comment | added | O.S. | I am new to the concept of the reducibility. Your first answer has helped me to rephrase my question in a better way. Thanks | |
| Mar 14, 2017 at 7:59 | comment | added | Yuval Filmus | I don't see how you would do that. Perhaps you should ask a different question in which you explain your real question instead of hiding it. | |
| Mar 14, 2017 at 7:58 | comment | added | O.S. | Thanks again. Does this mean that we can use the acceptance problem of LBA (which is decidable) to show that the emptiness problem of LBA is undecidable? Any general view of how we can do this? | |
| Mar 14, 2017 at 7:53 | comment | added | Yuval Filmus | Since the acceptance problem is decidable and the emptiness problem is non-trivial, you can reduce the acceptance problem to the emptiness problem. | |
| Mar 14, 2017 at 7:51 | comment | added | O.S. | Thanks for the feedback. But what if we reduce the acceptance problem to the emptiness problem assuming that we have no idea that the emptiness problem of LBA is decidable or not and the only info that we have is the acceptance problem of LBA is decidable. | |
| Mar 14, 2017 at 7:41 | history | answered | Yuval Filmus | CC BY-SA 3.0 |