View source for Opting for oracles

== An adapted example ==

Based on page 42 of 76 in [http://www.people.cs.uchicago.edu/~soare/Turing/shagrir.pdf Turing-Post Relativized Computability and Interactive Computing]:

<blockquote>
<b>The Limit Computable or Approximation Model</b>

There exists a sequence of Turing programs <math>\{P_t:t \in T\}</math> so that
<math>P_t</math> computes function <math>g_t</math> at time <math>{t \in T}</math>. 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 <math>t</math> to <math>t+1</math>.

Suppose a meteorologist receives data every second <math>t \in T</math> 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 <math>g_t</math> is the computable characteristic function of
<math>B_t</math>, the configuration of the meteorological computation at the end
of time <math>t</math>. The computable function <math>g_t</math> gives an algorithm to
compute the condition <math>B_t</math> at time <math>t</math> but it gives no relationship
between <math>B_t</math> and <math>B_{t+1}</math>. 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 <math>g_t</math>
for <math>{t \in T}</math>?

<b>The Online Model With an Oracle Machine</b>

By the Shoenfield Limit Lemma there is a computably enumerable set <math>{A}</math> (or even
a <math>\Delta_2^0</math> set) and oracle machine <math>\Phi_e</math> such that
<math>B = \Phi_e^A</math>. Now the meteorologist can program the
algorithm <math>\Phi_e</math> into a computer once and for all at the start of the
day. Every second <math>{t \in T}</math> the meteorologist receives from the weather stations
the latest readings <math>A_t</math> which enter directly into that computer by
an network connection. The meteorologist does not (and cannot) change the
program <math>\Phi_e</math> every second. The algorithm simply receives the
“oracle” information <math>A_t</math> from the weather-station network as it is continually
updated, and computes the approximation <math>B_t(x) = \Phi_e^{A_t}(x)</math>.
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.
</blockquote>

...the [[oracle]] is a function of time <math>t \in T</math> with result
<math>A_t</math> 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[https://hackage.haskell.org/package/dialogue <span></span>] - text and binary files, channels, <i>etc</i>. 

* the type of the final result returned by a nested sequence of CPS calls[https://dl.acm.org/doi/pdf/10.1145/165180.165199 <span></span>];

* the type of the state passed through all the calls which require it[https://www.cambridge.org/core/services/aop-cambridge-core/content/view/2EFAEBBE3A19EA03A8D6D75A5348E194/S0956796800001258a.pdf/the-ins-and-outs-of-clean-io.pdf <span></span>];

* the monadic, comonadic or arrow types of online actions[https://web.archive.org/web/20051212060309/http://www.cse.ogi.edu/PacSoft/publications/phaseiiiq10papers/codata.pdf <span></span>][https://hackage.haskell.org/package/io-machine <span></span>];

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

* lazy lists, for incremental streaming[https://arxiv.org/pdf/1907.11354.pdf <span></span>];

* lazy trees, for providing subtrees to various parts of the program[https://dspace.stir.ac.uk/bitstream/1893/12116/1/Harrison%20-%20thesis.pdf <span></span>].


[[Category:Mathematics]]