An oracle is a way to allow Turing machinesMathworldPlanetmath 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.

If T is a Turing machine and π is a problem (either a search problem or a decision problemMathworldPlanetmath) with appropriate alphabetMathworldPlanetmath then Tπ denotes the machine which runs T using π as an oracle.

A Turing machine with an oracle has three special states ?, y and n. Whenever Tπ enters state ? it queries the oracle about x, 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 y if in xπ and n otherwise. If π is a search problem then it switches to state n if there is no z such that π(x,z) and to state y is there is such a z. In the latter case the section of the tape containing x is changed to contain z.

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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath definitions use a special tape to contain the query and response.

Clearly if LL then L(TL) may not be equal to L(TL).

By definition, if T is a Turing machine appropriate for a complexity classPlanetmathPlanetmath 𝒞 then TL is a 𝒞 Cook reduction of L(TL) to L.

If 𝒞 is a complexity class then T𝒞 is a complexity class with T𝒞={LL=L(TC)C𝒞}. If 𝒟 is another complexity class then 𝒟𝒞={LLT𝒞L(T)𝒟}.

Title oracle
Canonical name Oracle
Date of creation 2013-03-22 13:01:36
Last modified on 2013-03-22 13:01:36
Owner Henry (455)
Last modified by Henry (455)
Numerical id 6
Author Henry (455)
Entry type Definition
Classification msc 68Q05
Defines query