An oracle is an abstract device that returns the answer to a specified decision problem in a single computational step. An oracle Turing
machine has a special query tape and states that permit it to ask whether a word
belongs to a fixed formal language 
. The languages decidable by such machines describe computation
relative to 
,
and the resulting reducibility is called Turing reducibility.
Oracles need not be computable. They are used to compare the information content of problems and to define relativized complexity classes.
