Timeline for If Halting problem is decidable, are all RE languages decidable?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 22, 2014 at 11:04 | history | edited | Peter | CC BY-SA 3.0 |
added 288 characters in body
|
| Jul 22, 2014 at 11:00 | comment | added | Peter | @DavidRicherby, that's true. I tried to simplify my answer so that the OP could understand it. That's why I phrased it in terms of a "magical machine". I'll add a note to avoid any confusion. | |
| Jul 22, 2014 at 8:11 | comment | added | David Richerby | Good answer! Although context makes it clear that, by "oracle-enriched Turing machine", you mean "a Turing machine with an oracle for some undecidable problem", it's best not to use phrases like that. It's common to consider Turing machines with oracles for much weaker problems, specifically, computable ones: for example, the $n$th level of the polynomial hierarchy is the set of polynomial time Turing machines with oracles for level $n-1$. None of those machines can decide undecidable problems. The power comes from the oracle being undecidable, not just from it being an oracle. | |
| Jul 21, 2014 at 22:02 | history | edited | Peter | CC BY-SA 3.0 |
added 2 characters in body
|
| Jul 21, 2014 at 16:50 | vote | accept | umang | ||
| Jul 21, 2014 at 16:46 | history | edited | Peter | CC BY-SA 3.0 |
added 835 characters in body
|
| Jul 21, 2014 at 16:35 | history | answered | Peter | CC BY-SA 3.0 |