Simple Rules, Complex Behavior
Elementary cellular automata are among the simplest possible computational systems: a row of cells, each either on or off, updating simultaneously based on a local rule that looks at only three cells (left neighbor, self, right neighbor). There are exactly 256 possible rules, numbered 0 through 255 by Stephen Wolfram's naming convention. Despite this extreme simplicity, some of these rules generate patterns of extraordinary complexity.
The Wolfram Classification
Wolfram organized the 256 rules into four behavioral classes. Class 1 rules (e.g., Rule 0, Rule 255) quickly collapse to a uniform state. Class 2 rules (e.g., Rule 4, Rule 108) produce simple periodic patterns — stripes, triangles, repeating blocks. Class 3 rules (e.g., Rule 30, Rule 90) generate chaotic, apparently random patterns. Class 4 rules (e.g., Rule 110) sit at the boundary — producing complex, long-lived structures that interact in intricate ways.
Key Rules to Explore
Rule 30 — The poster child for chaos in cellular automata. From a single cell, it generates a pattern that appears random on the left side but has a regular structure on the right. Wolfram used it as a random number generator.
Rule 90 — Produces the Sierpinski triangle, a famous fractal. This is because Rule 90 is equivalent to XOR of the two neighbors, and the binary rows of Pascal's triangle modulo 2 produce the same pattern.
Rule 110 — Proven Turing complete by Matthew Cook in 2004. This means that, in principle, this simple one-dimensional automaton can perform any computation — a profound result connecting the simplest systems to the most powerful.
Emergence and Computation
Cellular automata demonstrate a fundamental principle: complex global behavior can emerge from simple local rules with no central control. This principle underlies phenomena from crystal growth to traffic jams to the development of biological organisms. The fact that Rule 110 is computationally universal suggests that the capacity for complexity is inherent in even the most minimal systems.