TY - JOUR

T1 - When does a physical system compute?

AU - Horsman, Clare

AU - Stepney, Susan

AU - Wagner, Rob C.

AU - Kendon, Viv

N1 - © 2014 The Author(s) Published by the Royal Society. All rights reserved.
Funding details: Engineering and Physical Sciences Research Council, EPSRC, EP/G004544/3, EP/J008249/1, EP/J008249/2

PY - 2014/9/8

Y1 - 2014/9/8

N2 - 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 nonstandard 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.

AB - 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 nonstandard 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.

KW - computation

KW - computer

KW - physical computation

KW - calculations

KW - computers

KW - mathematical models

KW - biological computers

KW - computational devices

KW - computational entities

KW - computational level

KW - experimental science

KW - formal framework

KW - non-standard computing

KW - physical computing

KW - biology

UR - https://www.scopus.com/inward/record.uri?eid=2-s2.0-84910048210&doi=10.1098%2frspa.2014.0182&partnerID=40&md5=bdbd68be675412c238fb86784753000f

U2 - 10.1098/rspa.2014.0182

DO - 10.1098/rspa.2014.0182

M3 - Article

VL - 470

SP - 1

EP - 25

JO - Proceedings of the Royal Society A : Mathematical, Physical and Engineering Sciences

JF - Proceedings of the Royal Society A : Mathematical, Physical and Engineering Sciences

SN - 1364-5021

IS - 2169

ER -