When Do Physical Systems Compute?
Last update: 21 Apr 2025 21:17
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.
Recommended:
- 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."]
To read:
- 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