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

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

2005-08-24

arxiv.org/abs/nlin/0508033v1

Nonlinear Sciences

Cellular Automata and Lattice Gases

18 pages, 9 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Coarse-graining of cellular automata, emergence, and the predictability of complex systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coarse-graining of cellular automata, emergence, and the predictability of complex systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coarse-graining of cellular automata, emergence, and the predictability of complex systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-263028