When Do Physical Systems Compute?

Last update: 08 Dec 2024 00:04
First version: 21 March 2022

Yet Another Inadequate Placeholder

My intuition is to throw the term "computation" around very liberally for physical processes, but that's partly just how I was raised. I do get how it sounds odd to say that the planets are computing their orbits, or that collisions of molecules in a gas just so happen to be computing a complicated logical formula, so I'm interested in principled restrictions on the use of the term.

Marco Giunti, Computation, Dynamics, and Cognition [The first two-thirds has a nice treatment of abstract computers as discrete dynamical systems, including some apparently new results about non-Turing computation; the stuff about cognition and scientific explanation seems, by contrast, strained and tacked-on. By Giunti's standards, no analog computer does "computation"!]
Matthias Scheutz, "Computational versus Causal Complexity", Minds and Machines 11 (2001): 543--566 ["notions of implementation based on an isomorphic correspondence between physical and computational states are not tenable. Rather, 'implementation' has to be based on the notion of 'bisimulation' in order to ... incorporate intuitions from computational practice. A formal definition of implementation is suggested ... to make the functionalist notion of 'physical realization' precise. The upshot of this new definition ... is that implementation cannot distinguish isomorphic bisimilar from non-isomporphic bisimilar systems anymore, thus driving a wedge between the notions of causal and computational complexity."]

Neal G. Anderson and Gualtiero Piccinini, The Physical Signature of Computation: A Robust Mapping Account [2024; may supersede Piccinin's solo-authored 2015 book below?]
Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas, "Dynamical systems, simulation, abstract computation", arxiv:1101.0833
Gualtiero Piccinini, Physical Computation: A Mechanistic Account
Matthias Scheutz, "When Physical Systems Realize Functions...", Minds and Machines 9 (1999): 161--196 ["standard notions of computation together with a 'state-to-state correspondence view of implementation' cannot overcome difficulties posed by Putnam's Realization Theorem and that, therefore, a different approach to implementation is required. The notion 'realization of a function', developed out of physical theories, is then introduced as a replacement for the notional pair, 'computation-implementation'. After gradual refinement, taking practical constraints into account, this notion gives rise to the notion 'digital system' which singles out physical systems that could be actually used, and possibly even built."]
Oron Shagrir, The Nature of Physical Computation