Computational Irreducibility and the Predictability of Complex Physical Systems

Navot Israeli, Nigel Goldenfeld

Research output: Contribution to journalArticlepeer-review


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

Original languageEnglish (US)
JournalPhysical review letters
Issue number7
StatePublished - 2004

ASJC Scopus subject areas

  • Physics and Astronomy(all)


Dive into the research topics of 'Computational Irreducibility and the Predictability of Complex Physical Systems'. Together they form a unique fingerprint.

Cite this