Timeline for Mapping reduction to show NeverHalt is undecidable
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2014 at 21:13 | comment | added | Raphael | That's true, and a ficklish issue. Usually, every course/book has its "toolbox" of undecidable, un-semi-decidable, NP-complete, ... problems that can be used for reduction. There are few generally present defaults (afaict) so we usually fall back to the Halting problem and its complement. (Your MP is fine in the context of material that establishes that the word problem is undecidable for type-0 grammars.) | |
| Feb 3, 2014 at 20:26 | comment | added | lea | If we want to prove it by a mapping reduction don't we have to have a known undecidable language first? since that was the question I considered it known... | |
| Feb 2, 2014 at 22:15 | comment | added | Raphael | This only proves that NeverHalt is undecidable if we assume that MP is undecidable -- is it? (Of course it is, but still.) | |
| Feb 2, 2014 at 22:14 | history | edited | Raphael | CC BY-SA 3.0 |
formatting
|
| Feb 2, 2014 at 20:25 | review | Late answers | |||
| Feb 3, 2014 at 2:11 | |||||
| Feb 2, 2014 at 20:06 | history | answered | lea | CC BY-SA 3.0 |