Thursday, 19 June 2014

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, mp, 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: mpm'p.  We want this result inferred from the theory to be close to the real result mp', 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 mp.  We can use our theory to infer m'p, which is now sufficiently close to mp' because we have a good theory.  We can then use mp' 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 mp, 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 mp'.  Because we have a good theory of the physical system, its mp' 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.


  1. Excellent post, we (scientist of the fringe ;)) should really get use to this: summarize your paper in layman's term. I will definitely read your paper. I assume you are aware of the latest paper in the arxiv by David Deutsch (Constructor theory).
    From your post here I feel like arguing the "representation post hoc" thingy, but I need to read the paper first. I hope your paper does define what you mean by "prediction" since it seems to be the deciding attribute for the definition of computing.
    Congratulations on your publication and thanks for the post!

    1. Thanks for your comments.

      I have seen some of the Constructor Theory work, but I haven't read the latest (May 2014) paper -- I will put it on my reading list!

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

    I disagree with this statement.

    To abstract, is to accurately represent something, as something else.

    My brain, is an abstraction machine.

    What I mean, is that when I look at the wall in front of me right now.

    I perceive that wall as an abstraction of its true self.

    My brain is just a collection of neurons.
    The wall is represented as the activity of the photoreceptors in my eye, and represented as the neural activity in my brain.

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

    The brain is a computer, it is a physical system, yet it does not predict the result of an abstraction.

    So there are three options, either you are wrong, the brain is not a computer, or this statement is not the full story.

    1. Or there are four options.

      An abstraction is a model of something else (or somethings else), and "all models are wrong".

      And your brain is predicting the result of an abstraction when you look at a wall: it is predicting things like "the wall will stay as it is and not collapse, or turn into a pink elephant and fly away". If you think you are not predicting such things, would you be surprised if it did collapse? Would you be as surprised if you were looking at a cloud and it moved?