TITLE: Oracles and Advices as Measurements in Physics

ABSTRACT:

In this talk we will try to understand how oracles and advices,
classical mathematical abstractions in the Science of Computability
and Complexity, can be seen as physical measurements in Classical
Physics. In one way, oracles and advices can help us to understand
how the structure of space and time and the laws of Physics have an
information content in the sense of Barry Cooper and Piergiorgio
Odifreddi (in one aspect) and JackCopeland and Dianne Proudfoot (in
another aspect). In the other way, physical measurements are a
natural external information device to a Turing machine.

We will argue that as more developed a physical theory is, as less
information content can be retrieved from Nature.

In developing the mathematics of interactions between oracles in
Nature and oracle Turing machines, an inner structure of advice
classes P/log*, P/poly, and BPP//log* can be dug and put in
relation with Kolmogorov complexity measure.

(Joint work with Edwin Beggs, Bruno Loff, and John Tucker)