title: When does a physical system compute?
abstract: Computing is a high-level process of a physical system. Recent interest in non-standard computing systems, including quantum and biological computers, has brought this physical basis of computing to the forefront. There has been, however, no consensus on how to tell if a given physical system is acting as a computer or not; leading to confusion over novel computational devices, and even claims that every physical event is a computation. In this paper, we introduce a formal framework that can be used to determine whether a physical system is performing a computation. We demonstrate how the abstract computational level interacts with the physical device level, in comparison with the use of mathematical models in experimental science. This powerful formulation allows a precise description of experiments, technology, computation and simulation, giving our central conclusion:physical computing is the use of a physical system to predict the outcome of an abstract evolution. We give conditions for computing, illustrated using a range of non-standard computing scenarios. The framework also covers broader computing contexts, where there is no obvious human computer user. We introduce the notion of a 'computational entity', and its critical role in defining when computing is taking place in physical systems.
authors.affiliation: Department of Computer Science , University of Oxford , Oxford OX1 3QD, UK.
authors.forename: Clare
authors.initials: C
authors.lastname: Horsman
authors.affiliation: Department of Computer Science, and York Centre for Complex Systems Analysis , University of York , York YO10 5GH, UK.
authors.forename: Susan
authors.initials: S
authors.lastname: Stepney
authors.affiliation: School of Physics and Astronomy, University of Leeds , Leeds LS2 9JT, UK.
authors.forename: Rob C
authors.initials: RC
authors.lastname: Wagner
authors.affiliation: School of Physics and Astronomy, University of Leeds , Leeds LS2 9JT, UK.
authors.forename: Viv
authors.initials: V
authors.lastname: Kendon
keywords: computation; computer; physical computation