Oracle Machine
Jump to navigation
Jump to search
An oracle machine is an abstract machine that can compute some operation in constant time.
- See: Adversary System.
References
2010
- http://en.wikipedia.org/wiki/Oracle_machine
- 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 operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.
- An oracle machine is a Turing machine connected to an oracle. The oracle, in this context, is thought of as an entity capable of answering some collection of questions, and usually represented as some subset [math]\displaystyle{ A }[/math] of the natural numbers. Intuitively then, the oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle for an answer to a specific question of the form "is [math]\displaystyle{ x }[/math] in A?" There are several different definitions of an oracle machine, all of which are equivalent in the sense that they agree on when a specific function [math]\displaystyle{ f }[/math] can be computed by an oracle machine with oracle A. The following is a description of one particular definition.