
related topics 
{math, number, function} 
{system, computer, user} 
{god, call, give} 
{work, book, publish} 
{black, white, people} 

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.
Contents
Definition
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 A 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 x in A?"
The definition given here is one of several possible oracle machine definitions. All these definitions are equivalent, as they agree on which specific functions f can be computed by an oracle machine with oracle A.
An oracle machine, like a Turing machine, includes:
 a work tape: a sequence of cells without beginning or end, each of which may contain a B (for blank) or a 1;
 a read/write head, which rests on a single cell of the work tape and can read the data there, write new data, and move left or right along the tape;
 a control mechanism, which can be in one of a finite number of states, and which will perform different actions (reading data, writing data, moving the control mechanism, and changing states) depending on the current state and the data being read.
In addition to these components, an oracle machine also includes:
 an oracle tape, on which an infinite sequence of B's and 1's is printed, corresponding to the characteristic function of the oracle set A;
 an oracle head, which (like the read/write head) can move left or right along the oracle tape reading data, but which cannot write.
Formal definition
An oracle Turing machine is a 4tuple where
 Q is a finite set of states
 is a partial function called the transition function, where L is left shift, R is right shift.
 is the initial state
 is the set of halting states.
Full article ▸


related documents 
Queue (data structure) 
XSL Transformations 
Idempotence 
Ring (mathematics) 
Btree 
Presburger arithmetic 
Preorder 
Assignment problem 
Chain rule 
Richard's paradox 
Extended real number line 
Unicity distance 
MerkleHellman 
Splitting lemma 
Trie 
Boolean ring 
Haar measure 
ML (programming language) 
Meromorphic function 
Definable real number 
Axiom of pairing 
Legendre symbol 
Lazy evaluation 
Generalized mean 
Monster group 
Mathematical model 
Functional analysis 
Base (topology) 
Elementary group theory 
Examples of groups 
