When does a physical system compute?

Clare Horsman, Susan Stepney, Rob C. Wagner, Viv Kendon
When does a physical system compute?
Proceedings of the Royal Society A, 2014 (accepted)

A version of our recently accepted paper can be found on the arXiv.  Here is a very potted summary for those for whom its 21 pages is tl;dr.  Warning: what follows is necessarily an incomplete and misleading summary: if it wasn’t, we wouldn’t have written 21 pages in the first place!

The issue is this: the subject area of unconventional, or non-standard, computing has people building (or theorising about) computers made of many weird things: bacteria, slime moulds, soap films, black holes.  You name it, someone probably wants to build a computer out of it. Some people also claim that everything computes: a light ray, stone, the entire universe.

We want to pick apart what really constitutes computation with such a physical system (and, of course, traditional computers are physical systems too).  This helps us (a) distinguish between playing with weird materials from computing with them, and (b) distinguish between physical systems just doing their thing, and them computing.

First, we define science. (No wonder it took us 21 pages!)

Below the blue line is the real world of kickable physical stuff. Above is the abstract world of models and calculations.  p is a real world physical thing (not a model of a thing) that does its thing in the world to become real world physical thing p'.  We can represent p in the abstract world, m_p, using a representation relation R.  This is what scientists do all the time when they model bits of reality.  It’s all theory dependent, and there are many possible representations; we are looking at a specific one here.  If we have some scientific theory of things like p, we can use it to infer, or calculate, how our model of p behaves: m_p → m'_p.  We want this result inferred from the theory to be close to the real result m_p', the representation of the physical state p'.  In other words, we want ε to be small: this is the mark of a good theory.

Once we have a good scientific theory, with a sufficiently small ε, we can use it to predict things in the real world.

Here we start with a p, and represent it as m_p.  We can use our theory to infer m'_p, which is now sufficiently close to m_p' because we have a good theory.  We can then use m_p' to instantiate a p', using the reverse of the representation relation.  (This reverse relation is non-trivial to establish, and there might be no suitable p': is is perfectly possible to build models of unphysical systems!  See the paper if you want all the gory details.)  This is the physical prediction cycle, using science.

Computing goes the other way.  We instead use a physical system to predict the result of an abstract inference or calculation.

With physical computation, we start with some abstract problem m_p, and instantiate it in a physical system p (remember, instantiation is non-trivial).  The physical system does its thing, giving p'.  We then represent p' back in the abstract world as m_p'.  Because we have a good theory of the physical system, its m_p' is sufficiently close to our m'_p, the result of our desired calculation.  Hey presto, we are computing!

So: physical computing is the use of a physical system to predict the outcome of an abstract evolution.

The computation has three steps: the instantiation or encoding of the input problem, the physical evolution of the system (which will almost certainly be a highly engineered physical system), and the representation or decoding of the result.

So a physical system just doing its thing isn’t computing: that’s only the bottom line of the figure.  This includes the case where the physical system is a PC whirring away, but its output is never extracted and decoded.  A watched pot never boils; an unwatched computer never computes.  (We are not requiring the “watcher” to be a conscious agent, however; again, see the paper for details, else this blog post will be longer than the paper.)

And using a stone where we calculate its representation post hoc to give the right answer, or a highly experimental physical system where we throw away those evolutions that don’t work, also aren’t computing: there’s no prediction involved, just a comparison with a result actually computed separately.  There is a lot of work going on in those encoding/decoding stages.  (I blogged about something analogous when explaining why a stopped clock is never right: it is telling the time in exactly the same way that a stone is computing: not.)

If there are bits here you don’t follow, that’s because this is highly summarised, with important steps very compressed.  Read the full paper on the arXiv: it should hopefully make more sense!  Also, there’s lots more in the paper, about engineering, and refinement, and using a system to simulate another system, or even itself, and how that all fits in this model.