When does a physical system compute?
Clare Horsman1⇑, Susan Stepney2, Rob C. Wagner3 and Viv Kendon3
- Author Affiliations
1Department of Computer Science, University of Oxford, Oxford OX1 3QD, UK
2Department of Computer Science, and York Centre for Complex Systems Analysis, University of York, York YO10 5GH, UK
3School of Physics and Astronomy, University of Leeds, Leeds LS2 9JT, UK
e-mail: clare.horsman@gmail.com
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.
computation physical computation computer
Received March 6, 2014.
Accepted June 11, 2014.
© 2014 The Authors. Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/3.0/, which permits unrestricted use, provided the original author and source are credited.
FREE PDF GRATIS: Proceedings of the Royal Society A
