When Do Physical Systems Compute?
21 Mar 2022 09:40
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.
See also: Computation, Automata, Languages; Computational Mechanics; Dynamics; Symbolic Dynamics; Physics of Computation and Information
- 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 computation is "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." PDF]
- To read:
- Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas, "Dynamical systems, simulation, abstract computation", arxiv:1101.0833
- Gualtiero Piccinini, Physical Computation: A Mechanistic Account
- Oron Shagrir,
