Oracle Machine

An oracle machine is a Turing machine connected to an oracle. The Turing machine can write on its own tape an input for the oracle, then tell the oracle to execute. In a single step, the oracle computes its function, erases its input, and writes its output to the tape. Sometimes the Turing machine is described as having two tapes, one of which is reserved for oracle inputs and one for outputs.

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single step. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

The complete, up-to-date and editable article about Oracle Machine can be found at Wikipedia: Oracle Machine
http://en.wikipedia.org/wiki/Oracle_machine