John V Tucker
Edwin Beggs and Felix Costa and I have developed a theory of
combining algorithms with physical systems based upon using physical
as oracles to algorithms. The theory has two broad applications:
(i) exploring the role of physical technologies in boosting computations (Turing's original
motivating idea for oracles) and
The talk will introduce and survey the current state of our theory.
Power: In a series of papers we have shown that adding physical equipment as an oracle can boost the power of algorithms beyond the Turing barrier. For specific examples of physical system(mechanical, optical, electrical) the computational power has been characterised using non-uniform complexity classes. The power of the known examples vary according to assumptions on precision and timingbut seem to lead to the same complexity classes, namely P/log* and BPP/log*. Recently, we have developed axiomatic specifications of experiments that suggest these classes arise naturally and widely.
Limits to measurement: When an experimenter applies a experimental procedure to some equipment, due to its systematic nature, the experimental procedure can be thought of as an algorithm that governseach step in the experiment and processes the data. Indeed, in practice, many experiments are controlled by software. Inspired by Turing's 1936 and 1939 analysis, we have proposed the idea that:
"The experimenter following a systematic experimental procedure can be modelled by a Turing machine, and his or her interaction with equipment can be modelled as an oracle device connected to the Turing machine via an interface that governs the initialisation and operation of physical equipment."
We are creating an algorithmic theory of measurement that enables us to analyse some basic questions about measurement, including:
(i) What are the costs in time to perform measurements to a given