Editing Oracle machine (section)

==Definitions ==

There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from {{harvtxt|van Melkebeek|2003|p=43}}.

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 symbol from the tape alphabet; 
* a '''read/write head''', which rests on a single cell of the work tape and can read the data there, write new data, and increment or decrement its position 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''', which is a semi-infinite tape separate from the work tape. The alphabet for the oracle tape may be different from the alphabet for the work tape. 
* an '''oracle head''' which, like the read/write head, can move left or right along the oracle tape reading and writing symbols; 
* two special states: the ASK state and the RESPONSE state.

From time to time, the oracle machine may enter the ASK state. When this happens, the following actions are performed in a single computational step:
* the contents of the oracle tape are viewed as an instance of the oracle's computational problem;
* the oracle is consulted, and the contents of the oracle tape are replaced with the solution to that instance of the problem;
* the oracle head is moved to the first square on the oracle tape;
* the state of the oracle machine is changed to RESPONSE.
The effect of changing to the ASK state is thus to receive, in a single step, a solution to the problem instance that is written on the oracle tape.

=== Alternative definitions ===

There are many alternative definitions to the one presented above. Many of these are specialized for the case where the oracle solves a decision problem. In this case:
* Some definitions, instead of writing the answer to the oracle tape, have two special states YES and NO in addition to the ASK state. When the oracle is consulted, the next state is chosen to be YES if the contents of the oracle tape are in the oracle set, and chosen to the NO if the contents are not in the oracle set.{{sfn|Adachi|1990|p=111}} 
* Some definitions eschew the separate oracle tape. When the oracle state is entered, a tape symbol is specified. The oracle is queried with the number of times that this tape symbol appears on the work tape. If that number is in the oracle set, the next state is the YES state; if it is not, the next state is the NO state.{{sfn|Rogers|1967|p=129}}
* Another alternative definition makes the oracle tape read-only, and eliminates the ASK and RESPONSE states entirely. Before the machine is started, the [[indicator function]] of the oracle set is written on the oracle tape using symbols 0 and 1. The machine is then able to query the oracle by scanning to the correct square on the oracle tape and reading the value located there.{{sfnm|1a1=Soare|1y=1987|1p=47|2a1=Rogers|2y=1967|2p=130}}

These definitions are equivalent from the point of view of Turing computability: a function is oracle-computable from a given oracle under all of these definitions if it is oracle-computable under any of them. The definitions are not equivalent, however, from the point of view of computational complexity. A definition such as the one by van Melkebeek, using an oracle tape which may have its own alphabet, is required in general.