Combining algorithms and physical systems

Edwin Beggs

(Swansea (Maths))

I will explain what a physical oracle is, and how it is used. After a look at what sort of experiments might constitute a physical oracle, I will look at the theory of such devices. This comes in two parts:
1) How a physical oracle can boost the computational power of a Turing machine.
2) How computation places a limit on the experimental method.
I will end by talking about some areas of current research; measurable numbers, axiomatising physical oracles, and a conjecture on physically aided computation.

Tuesday 9th November 2010, 14:00
Robert Recorde Room
Department of Computer Science