oracle

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.

If $T$ is a Turing machine and $\pi$ is a problem (either a search problem or a decision problem) with appropriate alphabet then $T^{\pi }$ denotes the machine which runs $T$ using $\pi$ as an oracle.

A Turing machine with an oracle has three special states $\mathrm{?}$, $y$ and $n$. Whenever $T^{\pi }$ enters state $\mathrm{?}$ it queries the oracle about $x$, the series of non-blank symbols to the right of the tape head. If $\pi$ is a decision problem then the machine immediately changes to state $y$ if in $x\in \pi$ and $n$ otherwise. If $\pi$ is a search problem then it switches to state $n$ if there is no $z$ such that $\pi (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 $\pi$, since each time it accesses the oracle, the result is the same as a machine which solves $\pi$.

Alternate but equivalent definitions use a special tape to contain the query and response.

Clearly if $L\ne L^{\prime }$ then $L(T^L)$ may not be equal to $L(T^{L^{\prime }})$.

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

If $𝒞$ is a complexity class then $T^{𝒞}$ is a complexity class with $T^{𝒞}=\{L\mid L=L(T^C)\wedge C\in 𝒞\}$. If $𝒟$ is another complexity class then ${𝒟}^{𝒞}=\{L\mid L\in T^{𝒞}\wedge L(T^{\mathrm{\varnothing }})\in 𝒟\}$.

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