An oracle is a way to allow Turing machines access to information they cannot necessarily calculate. It makes it possible to consider whether solving one problem would make it possible to solve another problem, and therefore to ask whether one problem is harder than another.
A Turing machine with an oracle has three special states , and . Whenever enters state it queries the oracle about , the series of non-blank symbols to the right of the tape head. If is a decision problem then the machine immediately changes to state if in and otherwise. If is a search problem then it switches to state if there is no such that and to state is there is such a . In the latter case the section of the tape containing is changed to contain .
In either case, the oracle allows the machine to behave as if it could solve , since each time it accesses the oracle, the result is the same as a machine which solves .
Alternate but equivalent definitions use a special tape to contain the query and response.
Clearly if then may not be equal to .
If is a complexity class then is a complexity class with . If is another complexity class then .
|Date of creation||2013-03-22 13:01:36|
|Last modified on||2013-03-22 13:01:36|
|Last modified by||Henry (455)|