When does a physical system compute?

Posted on 10 July 2014

Can physical systems from bacteria to black holes act as a computer? A University of York computer scientist and colleagues from the universities of Oxford and Leeds address this question in newly published research which seeks to define unconventional computational devices.

Professor Susan Stepney, of the Department of Computer Science at York and her fellow researchers propose a framework which which defines and distinguishes scientific experiments, physical computation, and engineering technology.

The evolving focus on the physical basis of computing has been prompted by a growing interest in non-standard computing systems including quantum and biological computers. But there is no consensus on how identify if a physical system is operating as a computer or not.

The new research, published in Proceedings of the Royal Society A,introduces a formal framework that can be used to determine whether or not a physical system is performing a computation.

The researchers demonstrate how the abstract computational level interacts with the physical device level, drawing the comparison with the use of mathematical models to represent physical objects in experimental science.

This formulation allows a precise description of the similarities between experiments, computation, simulation, and technology, leading the researchers to conclude: physical computing is the use of a physical system to predict the outcome of an abstract evolution.

They give conditions that must be satisfied in order for computation to occur, and illustrate them with a range of non-standard computing scenarios. The framework also covers broader computing contexts, where there is no human computer user. They define the notion of a 'computational entity', and show the role it plays in defining when computing is taking place in physical systems.

Professor Stepney says: “Not every physical event is a computation, and for the first time we can distinguish which systems compute. In the future, this framework will enable the computational activity in biological systems and DNA to be precisely defined. We lay the foundations for computer science as a new natural science.”