an oracle machine

An oracle machine is an ordinary Turing machine given one superpower: a magic consultant it can ask yes/no questions about a fixed problem, and which always answers instantly and correctly, no matter how hard that problem is. Think of a student taking an exam who is allowed to phone a single all-knowing expert about one specific subject. The student still has to do their own reasoning and writing, but whenever they need a fact about that subject, the answer simply appears.

Concretely, an oracle machine for a language B has, alongside its normal tape, a special query tape. When it writes a string x on the query tape and enters a special query state, in a single step it moves to a 'yes' state if x is in B and a 'no' state otherwise, then continues computing. The oracle is a black box: we do not ask how it knows, even if B is itself undecidable. This is a thought experiment, not a buildable device. Its purpose is to measure the difficulty of one problem relative to another: what could you compute if only you had free, perfect access to B?

Oracle machines are the formal backbone of Turing reductions: A <=T B means an oracle machine with a B-oracle decides A. They let us ask refined questions even among the undecidable, such as: is problem A solvable given an oracle for the halting problem, but problem A' not? This relativized computation builds the layered structure of the uncomputable, the arithmetical hierarchy, where each new oracle (the halting problem, then the halting problem for machines with a halting-problem oracle, and so on) reaches strictly higher. Oracle machines also star in complexity theory, where a polynomially-bounded oracle machine relative to an NP oracle defines higher classes, and where the existence of contradictory oracle results (relativization) is a famous obstacle to settling P versus NP.