oracle

An oracle is an abstract entity (sometimes referred to a black box) presumed capable of immediately solving a specific problem, even one that is difficult or incomputable.

As originally defined

From the description by Alan Turing:

Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine. With the help of the oracle we could form a new kind of machine (call them o-machines), having as one of its fundamental processes that of solving a given number-theoretic problem. More definitely these machines are to behave in this way. The moves of the machine are determined as usual by a table except in the case of moves from a certain internal configuration o. If the machine is in the internal configuration o and if the sequence of symbols marked with l is then the well-formed formula A, then the machine goes into the internal configuration p or t according as it is or is not true that A is dual. The decision as to which is the case is referred to the oracle.

Systems of Logic Based on Ordinals (pages 172-173).

• an oracle cannot be computable.

If it was, then an oracle can be a machine for computing it.

• an oracle doesn't access the internal state of the machine that calls it.

To supply its result, the oracle only requires its own copy of the well-formed formula A in a representation that it can use, which the machine can generate from its internal state using l.

• an oracle returns a boolean result.

The oracle determines whether:

it is or is not true that A is dual

a result which is either True or False.

These properties can also be deduced from Emil Post's definition:

Now suppose instead, says Turing   in effect, this situation obtains with the following modification. That at certain times the otherwise machine determined process raises the question is a certain positive integer in a given recursively enumerable set S₂ of positive integers, and that the machine is so constructed that were the correct answer to this question supplied on every occasion that arises, the process would automatically continue to its eventual correct conclusion.²³

²³Turing picturesquely suggests access to an “oracle” which would supply the correct answer in each case. The “if” of mathematics is however more conducive to the development of a theory.

Recursively enumerable sets of positive integers and their decision problems (page 311).

Of interest here is the phrase the otherwise machine determined process - what answers the question is separate from that process. This implies:

• an oracle cannot be computable.

If it was, it could also be computed by the machine-determined process.

• an oracle doesn't access the internal state of the machine that calls it.

It only needs the positive integer of interest to supply the required answer, with all other actions being the responsibility of the machine-determined process.

• an oracle returns a boolean result.

There are only two definite answers to the question:

is a certain positive integer in a given recursively enumerable set S₂ of positive integers

and they can be mapped to the boolean values True and False.

Hence oracles originally were incomputable functions (predicates).

Booleans and beyond

Since then, oracles have been adapted to return a wider range of values and have been used and suggested for a wide variety of roles:

The theory of relative computability developed by Turing and Post and the o-machines provide a precise mathematical framework for interactive or online computing just as Turing a-machines provide one for offline computing processes such as batch processing.

Turing-Post Relativized Computability and Interactive Computing, Robert Irving Soare (page 7 of 76).

including those involving nondeterminism, by combining oracles with nondeterministic Turing machines.