Opting for oracles

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$ that provides 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.