Emergence and Complexity Classes — How Simple Rules Behave
Run enough cellular automata and a pattern in the patterns appears: their behavior falls into a few distinct classes, from dull to chaotic to the fascinating edge between. Wolfram's classification of this behavior, and the deep idea that the most interesting computation lives at the "edge of chaos," are among the most thought-provoking results in complexity science. This post is about how cellular automata behave, why complexity concentrates at a boundary, and the surprising unpredictability lurking in deterministic rules.
CA behavior falls into Wolfram's four classes — homogeneous, periodic, chaotic, and complex — with complexity and computation concentrating at class 4, the 'edge of chaos' between sterile order and sterile chaos. Plus computational irreducibility: for complex systems there's no shortcut, so simple deterministic rules can be fundamentally unpredictable.