Timeline for Aren't "oracle machines" unsound concepts?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2010 at 13:05 | comment | added | Stefan Geschke | Yes, but this is simply because complexity theory is only concerned with solvable problems. For all practical purposes it is not relevant whether a certain unsolvable (undecidable) problem is, say, logspace reducible to the halting problem. | |
| Jul 23, 2010 at 8:49 | comment | added | Marcos Villagra | Yes, but to my knowledge in complexity only decidable languages are used as oracles. | |
| Jul 23, 2010 at 8:45 | comment | added | MRA | If I understand correctly, there is no problem with using undecidable languages like the halting problem H as oracles. Using an H oracle introduces a new halting problem, i.e., a halting problem for TMs using an H oracle. This eventually leads to the notion of the arithmetical hierarchy. | |
| Jul 23, 2010 at 8:29 | history | edited | Marcos Villagra | CC BY-SA 2.5 |
added 7 characters in body
|
| Jul 23, 2010 at 8:17 | history | edited | Marcos Villagra | CC BY-SA 2.5 |
edited body; added 209 characters in body
|
| Jul 23, 2010 at 8:17 | comment | added | Marcos Villagra | I forgot to mention that oracles need to be a decidable language. And to answer your question consider a P machine M (machine with polynomially-bounded resources) with an oracle to another P machine N. Then $L(M^N) \in P$, and in general $P^O=P$ for any given $O$. So here there is no contradiction. | |
| Jul 23, 2010 at 8:06 | history | answered | Marcos Villagra | CC BY-SA 2.5 |