Chaos and Order: Statistical Properties of Random Soups

Seed a 100×100 grid of Life with cells randomly switched on or off at even odds — 50% density. Run it for a thousand generations and look at what’s left.

You will see, almost certainly, some blocks. Many blocks. Scattered beehives. A loaf or two, some boats. Perhaps one or two blinkers oscillating quietly. If you are lucky, a glider making its way toward the edge. The grid that began in pure noise has organized itself into a recognizable, boring mixture: a handful of the same simple patterns, arranged in roughly the same proportions, regardless of which specific random seed you used.

This convergence is not a coincidence. It is a mathematical consequence of how Life’s rules transform information — and understanding it requires thinking about Life not as a collection of specific patterns but as a dynamical system that acts on probability distributions.

The Information Theory Perspective: Life Is Lossy

Life’s rules are deterministic: every configuration has exactly one successor. But the function from configurations to successors is not injective — multiple different configurations can evolve into the same configuration. This is the fundamental reason why information is destroyed at each step.

When a function is not injective, information is lost when you apply it. If configurations A and B both evolve to configuration C, then looking at C and asking “what was the previous configuration?” has no definite answer. The information that distinguished A from B is gone. You can run Life forward, but you cannot run it backward — not uniquely.

This is a lossy rule. The state space contracts under Life’s dynamics. Starting configurations that differed in some detail — say, one live cell in a position that immediately dies without affecting anything else — converge to the same successor. The differences are erased.

The concrete evidence for this lossiness is the existence of Garden of Eden patterns. A Garden of Eden is a Life configuration that has no predecessor — no configuration that evolves into it in one step. Edward Moore proved, in a theorem that applies to any injective-free CA (including Life), that such patterns must exist: because the rule is not injective, there must be configurations that are “unreachable” — outputs with no input. In Life, specific Garden of Eden patterns were first exhibited by Roger Banks et al. in 1971, and subsequent researchers (most recently in a 2019 arXiv paper by Guan, Kehne, Moraschini and others) have found smaller examples and studied their density.

Garden of Eden patterns are the signature of irreversibility. They can only appear at generation zero, placed there by explicit fiat; no amount of running Life forward can produce them. Any random soup that does not begin life as a Garden of Eden will, as it evolves, produce more Garden of Eden configurations as debris — configurations that could not have existed before the evolution produced them. The space of reachable configurations shrinks at each step.

This is entropy decreasing — not in the thermodynamic sense (there is no heat or energy in Life), but in Shannon’s information-theoretic sense. The Shannon entropy of a Life grid, measured as the surprise content of the configuration given the rules and the prior evolution, decreases over time for most starting conditions. Structure is not created from nothing; rather, the information that was present in the initial random configuration is compressed and discarded as the evolution erases distinctions.

The Density Curve

The statistics of random soups are well-characterized by the relationship between initial density and final population.

Define initial density p as the probability that any given cell is alive at generation 0. For p = 0, the grid is empty and stays empty. For p = 1, the grid is full and rapidly empties (overcrowding kills almost everything immediately). The interesting behavior is between these extremes.

Nathaniel Johnston studied this systematically, and the Catagolue project (Adam Goucher’s large-scale census of random soups) has provided high-precision data from millions of trials. The key finding:

  • Very low p (below ~5%): Most cells die in isolation or in small clusters; the grid empties quickly. The final population is very small.
  • Very high p (above ~80%): Overcrowding kills most cells within a few generations. The grid crashes to a sparse remnant. The final population is also small, though from a different cause.
  • Intermediate p (~20%–60%): The grid evolves into a characteristic mixture of stable and oscillating patterns. The final population peaks somewhere in this range.
  • Peak survival: The maximum final population, averaged over many random soups, occurs near an initial density of 37.5%. This is not an accident: 3/8 is exactly the birth threshold for Life’s B3 rule — a dead cell is born if it has exactly 3 live neighbors. At 37.5% density, randomly placed cells have, on average, the birth condition approximately met for a maximal fraction of empty cells.

Research by Johnston found that lifespan (how long the soup takes to stabilize) also peaks near 37.5%, with a plateau across the 25%–50% range. The median final population peaks at 13 cells for an initial density of ~38%. The numbers are small because most random soups collapse to a handful of survivors; but the shape of the peak is consistent and reproducible.

The causal explanation for the bimodal collapse (both low and high densities produce small final populations) is that Life has a kind of carrying capacity. Too sparse, and patterns can’t sustain themselves — they die before finding neighbors. Too dense, and patterns can’t form — overcrowding kills cells faster than they can organize. The “goldilocks” density range produces the right balance of local activity and global space for stable patterns to form and persist.

What Survives: The Census

When random soups stabilize, what is left? The census data from Catagolue is unambiguous: the distribution is extremely concentrated.

The block — a 2×2 square of live cells, the simplest possible still life — is overwhelmingly dominant. According to Catagolue’s census of Life soups at standard density, the block accounts for approximately 30.9% of all object occurrences. It is the most common outcome of local dynamics, appearing almost everywhere that activity collapses into stability.

The beehive (a six-cell hexagonal still life) is the second most common, and the loaf, boat, and tub follow. The first five still lifes together account for 96% of all still life occurrences. The long tail of larger, rarer still lifes contributes almost nothing to the typical census.

This extreme concentration in a few simple attractors is directly related to the lossy nature of Life’s rules. The dynamics are funneling diverse initial conditions into a small set of stable outcomes. The block and beehive are not just common — they are attractors: local configurations that, once formed, persist indefinitely and are unreachable from most other nearby configurations (meaning they are not easily disturbed by adjacent dynamics).

The efficiency of this funnel is remarkable. A 16×16 random soup — 256 cells, each independently on or off — has 2²⁵⁶ ≈ 10⁷⁷ possible initial configurations. Almost all of them collapse to configurations containing only blocks, beehives, loafs, and a small number of other simple objects. The enormous initial variety is compressed, by a few hundred generations of local rule application, into a distribution concentrated on a handful of patterns.

Phase Transitions and the Edge of Chaos

In statistical mechanics, a phase transition is a sharp qualitative change in the behavior of a system at a critical value of some parameter. Water freezes at 0°C — above that temperature, it flows; below, it is rigid. The transition is sharp.

For some families of parameterized cellular automata, sharp phase transitions also occur. As a parameter (the density of live cells in a random initial configuration, or a parameter in the rules themselves) crosses a critical value, the qualitative behavior of the CA changes abruptly: from “almost everything dies” to “almost everything survives,” from “patterns stay local” to “information propagates globally.”

Life itself does not exhibit a sharp phase transition in its density-versus-stability curve — the transition from dead-dominated to survivor-dominated behavior is gradual, not abrupt. But Life’s position in the broader landscape of CA rules does reflect a kind of phase transition in rule space.

Christopher Langton, in his 1990 paper “Computation at the Edge of Chaos,” argued that CAs near the boundary between ordered and chaotic behavior — the “edge of chaos” — are capable of complex, sustained computation. The lambda parameter measures where a CA rule sits in this landscape: low lambda means ordered (Class I/II), high lambda means chaotic (Class III), intermediate lambda means complex (Class IV).

Life has lambda ≈ 0.273, placing it firmly in the intermediate range. But this understates the precision of Life’s position. The rules Conway selected — after experimenting with many alternatives — are not just somewhere in the intermediate range. They are specifically balanced so that:

  1. There exist patterns that grow without bound (glider guns, spaceships).
  2. There exist patterns that stabilize into simple still lifes.
  3. There exist patterns that exhibit complex, indefinitely sustained behavior (the methuselahs, the long-running computations).

Conway was looking for rules that satisfied these conditions empirically, testing combinations on a Go board before computers were available for the task. He did not have Langton’s language, but he was solving Langton’s problem: find a rule at the edge of chaos.

The observation that Life sits near a phase transition is not merely descriptive. It explains why Life is interesting. Rules deep in the ordered regime produce boring behavior — everything freezes or blinks. Rules deep in the chaotic regime produce noise — nothing persists, patterns dissolve before they can interact meaningfully. Rules at the edge produce the kind of behavior that Life is famous for: patterns that form, travel, collide, and sometimes do something surprising.

The edge of chaos is where information can be stored and transmitted and processed — all three at once. Ordered CAs can store information (in stable patterns) but cannot easily transmit it. Chaotic CAs transmit disturbances rapidly but cannot store information stably. Edge-of-chaos CAs do both, which is exactly what you need for nontrivial computation.

The Exceptional Cases: Methuselahs and the Statistical Tail

Random soup statistics measure averages. The average random soup at 37.5% density stabilizes in a few hundred generations, collapses to around 13 cells, and contains mostly blocks and beehives.

But averages do not describe extremes, and the extremes are interesting.

The statistical distribution of stabilization times is heavy-tailed: most soups stabilize quickly, but a small fraction stabilizes extremely slowly. These slow-stabilizing patterns — called methuselahs when they are small — evolve for hundreds, thousands, or even millions of generations before reaching a stable configuration. The most famous methuselah is the R-pentomino, a five-cell pattern that takes 1,103 generations to stabilize and produces 116 cells in the final configuration. For its initial size, this is extraordinary.

The statistical tail of random soups contains patterns whose lifespans are orders of magnitude longer than the median. In Nathaniel Johnston’s studies of density-vs-lifespan curves, the distribution of lifespans is approximately exponential in its tail: for each factor of 10 in lifespan, the frequency drops by some constant factor, but the tail never reaches zero. There are always rarer and longer-lived configurations.

This tail is what makes Life computationally interesting. The median behavior — rapid collapse to simple attractors — is not where the interesting dynamics live. The interesting dynamics live in the tail: patterns that, by chance or by design, happen to avoid the attractors long enough to do something complex. Every universal computation that Life supports, every self-replicating pattern, every engineered construction, lives in this tail. The typical soup is boring; the exceptional soup is everything.

The implication for Life engineering is practical: if you want to find new interesting patterns, you need to search the tail. The apgsearch tool (Adam Goucher), which drives the Catagolue census, is designed exactly for this: it runs millions of random soups, filtering for the ones that produce unusual objects — novel oscillators, rare spaceships, unexpected behavior. The common objects (blocks, beehives) are found in almost every run and filtered out as background. The rare objects appear only once in thousands or millions of runs, but the scale of the search makes them findable.

Entropy and the Direction of Time

There is a final observation about what the entropy of random soups reveals about Life’s relationship to time.

In thermodynamics, the second law — entropy does not decrease in a closed system — defines the arrow of time. We can tell the difference between a film of a glass breaking and a film of glass shards spontaneously assembling into a glass because the first obeys the second law (entropy increases) and the second violates it.

In Life, the analogous statement is: entropy does not increase (for most starting conditions). The Shannon entropy of a Life configuration decreases or stays constant as the system evolves. Starting from a random soup (high entropy), the configuration evolves toward a structured, low-entropy mixture of still lifes and oscillators.

This defines an arrow of time in Life as well — but pointing in the opposite direction from thermodynamics. In thermodynamics, the arrow points toward disorder; in Life, the arrow points toward order. This is because Life’s rules are fundamentally dissipative: they destroy information, funneling many initial conditions into few stable outputs.

You can tell the direction of a Life evolution by watching the entropy curve: starting from noise, entropy falls. Running forward in time, the grid becomes more structured. Run Life backward (if you could, and had a mechanism to do so), you would observe randomness spontaneously emerging from structure — an impossible sight.

The philosophical payoff: Life’s randomness and order are not symmetric. There is a preferred direction — from chaos to structure, from high entropy to low entropy, from noise to pattern. This direction is baked into the rules. It is a consequence of the lossy, non-injective character of the Life function. And it is why, starting from any sufficiently random initial condition, you will always see blocks.

Further Reading