TY - JOUR

T1 - Coarse-graining of cellular automata, emergence, and the predictability of complex systems

AU - Israeli, Navot

AU - Goldenfeld, Nigel

PY - 2006

Y1 - 2006

N2 - We study the predictability of emergent phenomena in complex systems. Using nearest-neighbor, one-dimensional cellular automata (CA) as an example, we show how to construct local coarse-grained descriptions of CA in all classes of Wolfram's classification. The resulting coarse-grained CA that we construct are capable of emulating the large-scale behavior of the original systems without accounting for small-scale details. Several CA that can be coarse-grained by this construction are known to be universal Turing machines; they can emulate any CA or other computing devices and are therefore undecidable. We thus show that because in practice one only seeks coarse-grained information, complex physical systems can be predictable and even decidable at some level of description. The renormalization group flows that we construct induce a hierarchy of CA rules. This hierarchy agrees well with apparent rule complexity and is therefore a good candidate for a complexity measure and a classification method. Finally we argue that the large-scale dynamics of CA can be very simple, at least when measured by the Kolmogorov complexity of the large-scale update rule, and moreover exhibits a novel scaling law. We show that because of this large-scale simplicity, the probability of finding a coarse-grained description of CA approaches unity as one goes to increasingly coarser scales. We interpret this large-scale simplicity as a pattern formation mechanism in which large-scale patterns are forced upon the system by the simplicity of the rules that govern the large-scale dynamics.

AB - We study the predictability of emergent phenomena in complex systems. Using nearest-neighbor, one-dimensional cellular automata (CA) as an example, we show how to construct local coarse-grained descriptions of CA in all classes of Wolfram's classification. The resulting coarse-grained CA that we construct are capable of emulating the large-scale behavior of the original systems without accounting for small-scale details. Several CA that can be coarse-grained by this construction are known to be universal Turing machines; they can emulate any CA or other computing devices and are therefore undecidable. We thus show that because in practice one only seeks coarse-grained information, complex physical systems can be predictable and even decidable at some level of description. The renormalization group flows that we construct induce a hierarchy of CA rules. This hierarchy agrees well with apparent rule complexity and is therefore a good candidate for a complexity measure and a classification method. Finally we argue that the large-scale dynamics of CA can be very simple, at least when measured by the Kolmogorov complexity of the large-scale update rule, and moreover exhibits a novel scaling law. We show that because of this large-scale simplicity, the probability of finding a coarse-grained description of CA approaches unity as one goes to increasingly coarser scales. We interpret this large-scale simplicity as a pattern formation mechanism in which large-scale patterns are forced upon the system by the simplicity of the rules that govern the large-scale dynamics.

UR - http://www.scopus.com/inward/record.url?scp=33344472563&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33344472563&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.73.026203

DO - 10.1103/PhysRevE.73.026203

M3 - Article

AN - SCOPUS:33344472563

SN - 1539-3755

VL - 73

JO - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

JF - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

IS - 2

M1 - 026203

ER -