Edwin Beggs - interaction of algorithms and physical systems

Joint research with John Tucker (Computer science, Swansea)

The interaction of a computer with the real world may be modelled by the idea of a physical oracle, based on Turing's use of an oracle as a mystical device for answering queries.

The temple of Apollo at Delphi

Wikipedia, Patar Knight, 2009

These messengers were sent to test the knowledge of the oracles, that, if they were found really to return true answers, he [Croesus] might send a second time, and inquire if he ought to attack the Persians.
Herodotus

John Tucker and I have been investigating the use of physical oracles for some time. A physical oracle can be used in two ways, to boost computation or to control a physical system. Unlike the abstract oracles of computability theory, a physical oracle can take a variable amount of time to answer a query (if ever), and the answer may have errors.

Unconventional computation is a name given to using natural (physical or biological) systems to do computation. With Felix Costa (Lisbon) we have published papers giving the limits of computation using physical oracles in terms of non-uniform complexity classes.

After analysis of many types of experiment we gave a conjecture on the experimental determination of physical quantities, we gave a conjecture on runtime of such an experiment - the runtime is exponential in the accuracy of measurement (accuracy being measured by number of digits). If you can devise a realistic thought experiment which can do better, I would be interested to hear.

Following from this conjecture, we have a derived conjecture: The upper bound on the complexity class of a computation carried out by a digital computer boosted by a physical experiment in polynomial time is the non-uniform complexity class BPP/log*. Previously to our analysis of the experimental time, there was the much higher estimate of P/Poly.

The idea of using a physical oracle to model the interaction of a computer with a physical system is related to hybrid systems and cyber physical systems. Here the idea of error prone oracles which take time to consult becomes important in modelling the uncertainties which arise in dealing with the real world.

No plan survives contact with the enemy.

Helmuth von Moltke the Elder (1800-1891)

It becomes important to distinguish between things which should not happen, but for which we have a plan for (known unknowns) and things we do not have a plan for (unknown unknowns).

There are known knowns; there are things we know that we know.
There are known unknowns; that is to say, there are things that we now know we don't know.
But there are also unknown unknowns - there are things we do not know we don't know.
Donald Rumsfeld (2002)

To make it easier to model and predict the behaviour of a physical system coupled to a computer, we consider modes of operation of the physical system, in a similar manner to object orientated programming. The paper Analogue-digital systems with modes of physical behaviour describes the use of modes in a analogue digital system.

Recommended links:
John Tucker's web page
Felix Costa's web page

Return to Edwin's home page