Opting for oracles

What an oracle is

It was the work of Emil Post and others that established the oracle more formally:

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 the oracle is a noncomputable function - originally a predicate, but now more commonly a function returning a wider range of values. This makes the use of oracles highly relevant to languages intended to preserve referential transparency, such as Haskell.

An adapted example

Based on page 42 of 76 in Turing-Post Relativized Computability and Interactive Computing:

The Limit Computable or Approximation Model

There exists a sequence of Turing programs $\{P_t:t\in T\}$ so that $P_t$ computes function $g_t$ at time $t\in T$. There is not necessarily any connection between different programs and computing may have to start all over again with a new program as the time changes from $t$ to $t+1$.

Suppose a meteorologist receives data every second $t\in T$ from weather stations scattered across the country. The configuration at the meteorologist's desk may be described using the Shoenfield Limit Lemma by a computable function where $g_t$ is the computable characteristic function of $B_t$, the configuration of the meteorological computation at the end of time $t$. The computable function $g_t$ gives an algorithm to compute the condition $B_t$ at time $t$ but it gives no relationship between $B_t$ and $B_{t+1}$. It will not be possible for the meteorologist to run, let alone write a new program every second. How will the meteorologist write a program to uniformly compute the index $g_t$ for $t\in T$?

The Online Model With an Oracle Machine

By the Shoenfield Limit Lemma there is a computably enumerable set $A$ (or even a $\underset{2}{\overset{0}{\mathrm{\Delta }}}$ set) and oracle machine ${\mathrm{\Phi }}_e$ such that $B=\underset{e}{\overset{A}{\mathrm{\Phi }}}$. Now the meteorologist can program the algorithm ${\mathrm{\Phi }}_e$ into a computer once and for all at the start of the day. Every second $t\in T$ the meteorologist receives from the weather stations the latest readings $A_t$ which enter directly into that computer by an network connection. The meteorologist does not (and cannot) change the program ${\mathrm{\Phi }}_e$ every second. The algorithm simply receives the “oracle” information $A_t$ from the weather-station network as it is continually updated, and computes the approximation $B_t(x)=\underset{e}{\overset{A_t}{\mathrm{\Phi }}}(x)$. The meteorologist's program then produces the next scheduled weather forecast for the day from the algorithm's result. It is difficult to see how this meteorologist could have carried out that activity using a batch processing, automatic machine model, instead of an online model.

...the oracle is a function of time $t\in T$ with result $A_t$ providing input to the meteorologist's program.

The problem of choice

But for the program's output - the forecasts - an element of choice is often involved:

• the choice of time to send the forecasts to media outlets broadcasting to listeners or viewers - forecasts may need to be sent more frequently to regions experiencing more severe weather conditions.

• the choice of device - the meteorologist may need a hard copy of the latest forecast (or some part thereof) for research purposes.

Choices can also affect the program itself - the meteorologist may for some reason decide to intervene while the program is running (perhaps restarting it to provide more accurate forecasts after software upgrades).

In contrast, output is a simple matter for a function - if there is any, it all goes to its caller! Therefore interactive choice requires something more than functions alone; it usually appearing in the form of an abstract type:

• the various auxiliary types used in dialogues - text and binary files, channels, etc.

• the type of the final result returned by a nested sequence of CPS calls;

• the type of the state passed through all the calls which require it;

• the monadic, comonadic or arrow types of online actions;

Another option is to use an structured value of unbounded size:

• lazy lists, for incremental streaming;

• lazy trees, for providing subtrees to various parts of the program.