• Featured in Physics

Computational Irreducibility and the Predictability of Complex Physical Systems

Navot Israeli and Nigel Goldenfeld
Phys. Rev. Lett. 92, 074105 – Published 20 February 2004
Physics logo

Abstract

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.

  • Figure
  • Figure
  • Received 16 June 2003

DOI:https://doi.org/10.1103/PhysRevLett.92.074105

©2004 American Physical Society

Authors & Affiliations

Navot Israeli and Nigel Goldenfeld

  • Department of Physics, University of Illinois at Urbana–Champaign, 1110 West Green Street, Urbana, Illinois, 61801-3080, USA

See Also

Complexity is Elusive

Don Monroe
Phys. Rev. Focus 13, 10 (2004)

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 92, Iss. 7 — 20 February 2004

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×