Rule 110 and Computation in a Grid

Rule 110 looks like another one-byte transition table.

111 110 101 100 011 010 001 000
 0   1   1   0   1   1   1   0

But its behavior gives us a much deeper idea: a cellular automaton can become a computational medium.

The important shift is this:

pattern generator
      ->
signal system
      ->
computation

Rule 110 is computationally universal — under suitable encodings and initial conditions. Matthew Cook published the universality proof in Complex Systems in 2004, settling a conjecture Wolfram had made in the mid-1980s: this elementary one-dimensional automaton can emulate universal computation.

The proof is much more elaborate than anything we need in this chapter. We are not going to pretend that a visually interesting Rule 110 run somehow proves universality.

Instead, we will study the mechanism that makes the result plausible: structured backgrounds, localized disturbances, propagation and interaction.

Primary reference: Matthew Cook, “Universality in Elementary Cellular Automata”.

Run Rule 110

A single-cell seed is useful for comparing elementary rules, but Rule 110’s characteristic mixture of domains and disturbances is easier to see from a richer initial state.

rng = np.random.default_rng(110)
initial = rng.integers(0, 2, size=241, dtype=np.uint8)

history = run_from_state(
    initial_state=initial,
    rule_number=110,
    generations=160,
)

Visualize it:

import matplotlib.pyplot as plt

plt.figure(figsize=(12, 8))
plt.imshow(history, cmap="binary", interpolation="nearest")
plt.title("Rule 110")
plt.xlabel("cell")
plt.ylabel("generation")
plt.show()

The canonical book figure is generated with:

python scripts/figures/cellular-automata/part01_foundations.py 04

The important observation is not simply that the image is complicated.

Look for the coexistence of:

repeating domains
localized defects
moving boundaries
interactions between structures

That mixture is much more interesting computationally than visual irregularity alone.

Patterns can act like signals

Imagine a repeating background with a localized defect moving through it.

Conceptually:

background background [defect] background background
                           --->

If the defect persists, its position and type can carry information.

If two defects collide and the collision produces another persistent pattern, the interaction can transform information.

    flowchart LR
    A[Persistent local structure] --> B[Propagation]
    B --> C[Collision with another structure]
    C --> D[Changed outgoing structures]
    D --> E[Information transformation]
  

That gives us the ingredients from which computation can be constructed:

persistent structures
        +
controlled movement
        +
interactions
        =
computational substrate

This idea appears again in Conway’s Game of Life, where gliders make the signal interpretation especially visual.

Note the careful wording: ingredients from which computation can be constructed — by deliberate arrangement, not by accident. Everything in this section is plausibility scaffolding. The theorem itself is described two sections below.

Detect local activity

We can start analyzing Rule 110 without knowing the names of every structure.

One simple tool is a temporal activity map:

activity = history[1:] != history[:-1]

plt.figure(figsize=(12, 8))
plt.imshow(activity, cmap="binary", interpolation="nearest")
plt.title("Cells that changed")
plt.show()

Another is neighborhood frequency:

from collections import Counter


def neighborhood_counts(row):
    counts = Counter()
    for i in range(len(row)):
        n = (
            int(row[(i - 1) % len(row)]),
            int(row[i]),
            int(row[(i + 1) % len(row)]),
        )
        counts[n] += 1
    return counts

These tools do not identify Cook’s computational construction for us.

They do something more basic and reusable: they turn the automaton into a system we can interrogate rather than merely watch.

What Cook actually proved

The precise result, stated so later chapters can rely on it:

PROVEN (Cook 2004)
  Rule 110 can emulate a cyclic tag system — itself a known
  universal model of computation — and is therefore capable
  of universal computation. This settled Wolfram's mid-1980s
  conjecture; the main construction was in place by the
  mid-1990s and published with full details in 2004.

CONSTRUCTED / DEMONSTRATED
  The emulation arranges gliders — persistent moving structures —
  against a periodic background (the "ether"), with data encoded
  in the spacing and type of incoming gliders and logic performed
  by their collisions. Universality lives in this deliberately
  constructed arrangement, not in typical runs.

INTERPRETATION (Wolfram)
  That such a tiny rule clears the universality threshold supports
  Wolfram's broader Principle of Computational Equivalence. That
  principle is Wolfram's theoretical position, not a consequence
  of Cook's theorem.

NOT IMPLIED BY THE RESULT
  universal
    ≠ easy to program
    ≠ efficient
    ≠ useful for arbitrary practical computation
    ≠ spontaneously performing arbitrary computation
      from random initial conditions

Two distinctions in that ledger will recur throughout the book. First, performing computation (patterns transforming information) is weaker than universality (emulating any Turing machine under some encoding), which is weaker still than practical programmability. Second, universality is a property of a rule plus a carefully built initial configuration — the ether, the glider fleet, the input encoding. A random Rule 110 run computes nothing in particular, just as an unprogrammed CPU computes nothing in particular. Chapter 27 will formalize this; here the slogan is enough:

Universal means “can be arranged to compute anything,” not “does compute everything.”

Computation does not need a CPU-shaped machine

Programmers are used to computation looking like this:

instruction
register
memory
branch
instruction

Cellular automata show another possibility:

local state
local interaction
propagating pattern
collision
new pattern

The computation is embodied in the dynamics.

There is no separate processor walking over passive memory. The state of the world and the process transforming that state are intertwined.

That is one reason cellular automata connect naturally to distributed and unconventional computing.

Build a perturbation experiment

Start from the same random world twice, then flip one bit.

rng = np.random.default_rng(4)
base = rng.integers(0, 2, size=201, dtype=np.uint8)
changed = base.copy()
changed[100] ^= 1

ha = run_from_state(base, 110, 120)
hb = run_from_state(changed, 110, 120)

diff = ha != hb

Visualize the difference:

plt.imshow(diff, cmap="binary", interpolation="nearest")
plt.title("Propagation of one-bit perturbation")
plt.show()

This experiment gives us a visual map of causal influence.

The broader lesson is useful:

A computation can be studied as the propagation and transformation of distinctions in state.

That statement alone does not prove that a system is universal. It gives us a practical lens for looking for information-bearing dynamics.

Rule 30 versus Rule 110

It is useful to place the two famous rules side by side — same one-byte format, opposite lessons:

Neither label tells the whole story.

The contrast the book wants is sharper than “random versus computational”:

Rule 30  asks: how irregular can determinism look?
Rule 110 asks: how much can local interactions be arranged to do?

The point is to learn to inspect a dynamical system in terms of:

• persistent structures,
• information propagation,
• perturbation growth,
• collisions,
• repeating cycles,
• and measurable state change.

From one dimension to two

One-dimensional automata are wonderful because time gives us the second visual axis.

But two-dimensional grids let structures move inside the world itself.

That is where one cellular automaton became iconic.

In the next chapter we move to Conway’s Game of Life and build its complete rule from first principles.

Research

• Cook, M. — Universality in Elementary Cellular Automata (Complex Systems 15(1), 2004). The theorem this chapter reports: proof of Wolfram’s mid-1980s conjecture that Rule 110 is capable of universal computation, via emulation of a cyclic tag system with gliders on a periodic background. The abstract states the result precisely; the full paper carries the construction. Later universality claims in this book inherit this chapter’s terminology, so check them against this source. https://doi.org/10.25088/ComplexSystems.15.1.1

• Wolfram, S. — A New Kind of Science, Chapter 11, Section 8: The Rule 110 Cellular Automaton (pp. 675–691). The book-length context for the proof: the universality threshold, the ether-and-gliders construction, and the significance Wolfram draws from it. Read the construction description alongside Cook, and treat the Principle of Computational Equivalence material (Chapter 12) as interpretation rather than theorem. https://www.wolframscience.com/nks/p675–the-rule-110-cellular-automaton/

• Weisstein, E. W. — Rule 110 (MathWorld). Compact verification reference: encoding 110 = 01101110, equivalence family (mirror 124, complement 137), and the conjecture-to-proof timeline (conjectured mid-1980s, construction through the 1990s, Cook 2004). Use it to check dates and bit tables before repeating them. https://mathworld.wolfram.com/Rule110.html

• Zenil, H. & Martinez, G. J. — Cellular Automata (Scholarpedia). The precision guardrail: Cook’s construction uses suitably arranged patterns and periodic backgrounds, so the initial-condition convention matters when stating universality — and constructing a logic gate must not be confused with proving a complete universality result. Cite this distinction whenever later chapters approach universality language. http://www.scholarpedia.org/article/Cellular_automata