Oracles are used in complexity theory for lower and upper bounds in the decision tree model. Using oracles you can tell if the proof for certain problems (like P vs NP) relativizes or not. If it relativizes then you cannot use a proof based on diagonalization (like the halting problem) to solve it. Can also tell you about bad approaches to the problem. A good book to read about this is chapter 3 of Computational Complexity: A Modern Approach (here is the draft). A beautiful paper about oracles in complexity theory was written by Fortnow.

Some people like oracles and some don't. I particularly like them, because lower bounds are very hard to proof in a general Turing machine. Lower bounds in at least a restricted model is a step towards a real lower bound. I believe the best lower bounds we truly understand are AC0 circuits.

Oracles are used in complexity theory for lower and upper bounds in the decision tree model. Using oracles you can tell if the proof for certain problems (like P vs NP) relativizes or not. If it relativizes then you cannot use a proof based solely on diagonalization (like the halting problem) to solve it. Can also tell you about bad approaches to the problem. A good book to read about this is chapter 3 of Computational Complexity: A Modern Approach (here is the draft). A beautiful paper about oracles in complexity theory was written by Fortnow.

Some people like oracles and some don't. I particularly like them, because lower bounds are very hard to proof in a general Turing machine. Lower bounds in at least a restricted model is a step towards a real lower bound. I believe the best lower bounds we truly understand are AC0 circuits.

Oracles are used in complexity theory for lower and upper bounds in the decision tree model. Using oracles you can tell if the proof for certain problems (like P vs NP) relativizes or not. If it relativizes then you cannot use a proof based on diagonalization (like the halting problem) to solve it. I good book to read about this is chapter 3 of Computational Complexity: A Modern Approach (here is the draft).

Some people like oracles and some don't. I particularly like them, because lower bounds are very hard to proof in a general Turing machine. Lower bounds in at least a restricted model is a step towards a real lower bound. I believe the best lower bounds we truly understand are AC0 circuits.

Oracles are used in complexity theory for lower and upper bounds in the decision tree model. Using oracles you can tell if the proof for certain problems (like P vs NP) relativizes or not. If it relativizes then you cannot use a proof based on diagonalization (like the halting problem) to solve it. Can also tell you about bad approaches to the problem. A good book to read about this is chapter 3 of Computational Complexity: A Modern Approach (here is the draft). A beautiful paper about oracles in complexity theory was written by Fortnow.

Some people like oracles and some don't. I particularly like them, because lower bounds are very hard to proof in a general Turing machine. Lower bounds in at least a restricted model is a step towards a real lower bound. I believe the best lower bounds we truly understand are AC0 circuits.