Oracle Machines

An oracle machine is a theoretical computational model introduced by Alan Turing in 1939 that extends the standard Turing Machine with access to an oracle — a black-box device that answers queries about some fixed problem (such as the Halting Problem) in a single computation step, regardless of the problem's intrinsic difficulty. Oracle machines do not model physically realizable systems; they are a formal device for measuring the relative difficulty of undecidable problems. If machine A with access to oracle B can decide problem C, then C is said to be reducible to B — B is at least as hard as C. This framework is the basis of relative computability theory and the Turing degrees, a rich partial order on the degrees of unsolvability.