= Oracle Turing machine
An <oracle Turing machine> is a <Turing machine> with an additional query operation for a fixed <formal language> $A$. It writes a finite query $x$ on a designated tape and receives the membership answer $x\in A$ in one oracle step. Writing the query still takes ordinary machine work. The oracle's internal solution procedure is excluded from the cost model.
For example, a machine with an oracle for <Boolean satisfiability> can ask whether a given <Boolean formula> has a satisfying assignment. By fixing variables one at a time and querying satisfiability again, it can recover an assignment with at most one additional query per variable. The example turns decision access into search access; it does not provide an ordinary fast satisfiability solver. Oracles let <computability theory> and <computational complexity theory> compare problems while making the granted information explicit.<Introduction to Theoretical Computer Science by Boaz Barak>[oracle machines, reductions and search versus decision]{ref}
Back to article page
