Phys. Rev. Lett. 92, 074105 (2004) [4 pages]Computational Irreducibility and the Predictability of Complex Physical Systems
See accompanying Physics Focus 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. © 2004 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevLett.92.074105
DOI:
10.1103/PhysRevLett.92.074105
PACS:
05.45.Ra, 05.10.Cc, 47.54.+r
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.