Oracle Turing machine

A Turing machine augmented with a special query step that determines in one step whether a queried string belongs to a specified set, called its oracle.

Oracle: An idealized information source that answers membership queries about a fixed set. The machine’s special step asks this source whether a string belongs to its set.
P^A: The class of languages decidable in polynomial time by a deterministic machine with oracle access to set A. It names the efficient computations available when this machine queries A.
Turing machine: An abstract machine that computes by manipulating symbols on an unbounded tape according to finite rules. Oracle machines extend this model with a special membership-query operation.
Turing reduction: A reduction that may make multiple adaptive queries to a target problem. Unlike a machine relative to a fixed oracle, it describes one problem’s reducibility to another.
Oracle tape: A tape used to present a query to an oracle during a computation. The machine writes a candidate string here before receiving the membership answer.
NP^A: The class of languages recognized in nondeterministic polynomial time with oracle access to set A. It expresses how nondeterministic computation changes when queries to A are allowed.
Decision problem: A problem whose answer for each input is yes or no. An oracle query asks precisely whether an input has a yes answer for a fixed problem.
Many-one reduction: A reduction that transforms each input into one instance whose answer preserves membership. It uses a single transformed instance rather than adaptive oracle queries.
Oracle Turing machine computation: A computation in which a Turing machine may query a fixed oracle set. Its sequence of queries and answers specifies how oracle access affects a run.
Polynomial hierarchy: A hierarchy of complexity classes extending P and NP through bounded alternations of quantifiers or computation. Oracle machines provide a standard way to define its levels using queries to complete sets.

Linked from 8 pages