How much complexity can you build from a single byte of logic? It turns out, you can build everything. The universe of Elementary 1D Cellular Automata demonstrates that simple rules, applied repeatedly over time, can give rise to structures of infinite complexity, chaos, and even universal computation. Let's break down how this works.

The Rule Table

Imagine a one-dimensional grid—a single line of cells. Each cell has two possible states: 0 (dead/empty) or 1 (alive/filled). Time progresses in discrete steps, or generations. At each generation, every cell looks at itself and its two immediate neighbors (the cell to its left and the cell to its right) to determine what state it should take in the next generation.

Because a cell only cares about its 3-cell window, and each cell in that window can be either 0 or 1, there are exactly $2^3 = 8$ possible patterns: 111, 110, 101, 100, 011, 010, 001, and 000.

A "rule" is simply a lookup table that assigns an output state (0 or 1) for each of these 8 patterns. Because there are 8 outputs to assign, there are $2^8 = 256$ possible rules in total. By numbering these 256 configurations from 0 to 255, we get Wolfram's famous naming convention. For example, Rule 110 is simply 01101110 in binary. The output dictates the next state for the 8 possible patterns.

Wolfram's Four Classes of Complexity

Stephen Wolfram embarked on a systematic study of all 256 rules and made a profound discovery. Despite the vast differences in the rules, their behaviors generally fall into one of four distinct classes:

• Class I (Uniformity): The system rapidly converges to a uniform state. Any initial pattern is quickly wiped out, ending in all 0s or all 1s. (e.g., Rules 0, 255)
• Class II (Repetition): The system quickly settles into a stable, periodic structure. It becomes a repeating pattern that doesn't change or oscillates predictably. (e.g., Rules 4, 108)
• Class III (Chaos): The system generates chaotic, aperiodic patterns. It never settles down, and the patterns appear completely random. (e.g., Rules 30, 45)
• Class IV (Complexity): The system produces complex, localized structures that move and interact. These rules balance between order and chaos, leading to persistent, interesting behaviors. (e.g., Rule 110)

Rule 30: Deterministic Chaos

Rule 30 is a perfect example of Class III behavior. Even when starting from a single live cell in an otherwise empty universe, it generates a chaotic, unpredictable pattern that grows endlessly. In fact, the center column of the resulting triangle passes statistical randomness tests so well that Wolfram used it as the default pseudo-random number generator in the software Mathematica for many years! It is a striking demonstration of how a completely deterministic, simple rule can generate apparent randomness.

Rule 90: Fractals Everywhere

Rule 90 belongs to Class II. When fed a single live cell, Rule 90 builds a perfect fractal—the Sierpiński Triangle. The rule acts as an XOR (exclusive OR) function between the left and right neighbors. This simple bitwise operation visually manifests as self-similarity across all scales.

Rule 110: Universal Computation

Rule 110 is perhaps the most famous of all Class IV automata. In the 1990s, Matthew Cook proved that this tiny rule table—just 8 bits of logic—is Turing-complete. This means that, given the right initial conditions, the simple interactions of cells moving across the grid in Rule 110 can perform any calculation that any modern supercomputer can do. Gliders, stationary structures, and their collisions serve as the "wires" and "logic gates" of this computational substrate. It is one of the most profound examples of emergence in the mathematical world.

Experience It Yourself

You can explore this universe of computation in our interactive Cellular Automata experiment. Try typing in Rule 30, 90, or 110. Draw random initial conditions, let the generations unfold, and watch complexity emerge from simplicity in real time.