Computational Irreducibility and the Predictability of Physical Systems

Nigel Goldenfeld
University of Illinois, Urbana-Champaign

Using elementary cellular automata (CA) as an example, I show how to coarse grain CA in all classes of Wolfram’s classification. The resulting coarse-grained CA emulate the large-scale behavior of the original systems without accounting for small-scale details. Computationally irreducible physical processes can be predictable and even computationally reducible at a coarse-grained level of description. At least one of the CA that can be coarse grained is irreducible and known to be a universal Turing machine.

Created by Mathematica  (April 20, 2004)