Computational Irreducibility and the Predictability of Physical Systems
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.
(April 20, 2004)