Cellular Automata as Computation

A cellular automaton is a state machine distributed across space.

Each cell reads local information, applies the same transition rule, and writes a new state.

That is computation in the thin sense: deterministic state transformation. Every automaton in this book computes, in that sense, every step it runs.

The deeper question — and the one this chapter formally owns — is whether local patterns can carry, transform and combine information in a way that supports general computation. Chapter 5 gave the first exposure through Rule 110’s gliders; here universality becomes a precise comparative property rather than an impressive example.

Information needs carriers

In ordinary software, information lives in variables and memory addresses.

In a cellular automaton, information can be represented by patterns:

stationary structures
moving structures
phase differences
collisions

A moving pattern can act like a signal.

Its position and phase can encode state.

Signals and collisions

Imagine two localized structures moving toward one another.

Their collision may produce:

nothing
one surviving structure
several new structures
a phase-shifted structure

If outcomes depend predictably on the inputs, collisions can implement logical transformations.

The physical-looking interaction is performing information processing.

A tiny Boolean CA example

We can construct a deliberately simple local rule that computes XOR between two neighbors:

def xor_step(state):
    left = np.roll(state, 1)
    right = np.roll(state, -1)
    return left ^ right

This is not merely related to elementary Rule 90 — it is Rule 90’s update (verified identical on all tested configurations): each cell becomes the XOR of its two neighbors, center excluded.

Run it:

state = np.zeros(101, dtype=np.uint8)
state[50] = 1

history = []
for _ in range(60):
    history.append(state.copy())
    state = xor_step(state)

The famous triangular pattern is not merely decorative.

Every new bit is the result of a Boolean computation over local inputs.

Computation can be spatial

Traditional code often looks like:

instruction 1
instruction 2
instruction 3

Cellular automata instead compute through repeated spatial transformation:

state(t)
   ↓ local parallel rule
state(t+1)
   ↓ local parallel rule
state(t+2)

There is no central instruction pointer.

The whole lattice advances together.

Rule 110, stated precisely

Chapter 5 introduced Rule 110’s ether, gliders, and collisions as plausibility scaffolding. The formal statement, kept to its bucket:

PROVEN (Cook 2004)
  Rule 110 emulates a cyclic tag system and is therefore
  capable of universal computation — "universal" meaning it
  can simulate a universal Turing machine under a specified
  encoding. This settled Wolfram's mid-1980s conjecture.

CONSTRUCTED
  The emulation is a deliberately built arrangement: data as
  gliders against a periodic background, logic in collisions.
  Universality is a property of rule + encoding + initial
  configuration, never of the bare rule table.

NOT IMPLIED
  efficiency, programmability, spontaneous computation from
  typical starts, or anything about finite rings (where every
  orbit is eventually periodic by counting alone).

The architectural ingredients generalize beyond Rule 110 — the construction chain every universality result in this book follows:

    flowchart LR
    R[local rule] --> C[stable background + carriers]
    C --> I[predictable collision interactions]
    I --> L[logic gates + memory]
    L --> U[emulated universal machine]
  

A rule does not need a CPU-shaped architecture to compute. But every arrow above is a construction burden: skip one and the chain breaks, which is why the table below separates what each system established from what it merely suggests.

Game of Life as a computer

Conway’s Life provides another intuitive example — and a second, independent universality result with a different construction history.

Gliders can carry signals.

Glider streams can represent periodic signals.

Collisions and engineered structures can implement logical operations and memory — the Berlekamp–Conway–Guy construction shows the computing primitives (storage, transmission, gates) realized as Life patterns, and Rendell later implemented an explicit Turing machine in Life.

Again, the same local Life rule continues everywhere.

The program lives in the arrangement of patterns, not in a changing rule table.

This gives us two layers:

physics = cellular rule
program = initial configuration / structures

That separation is extremely powerful — and it is also why universality claims always carry the arranged-configuration qualifier. Both results assume unbounded grids; both say nothing about random starts.

What universality does not mean

The mandatory distinction block, stated once so later chapters inherit it exactly:

computation
  ≠ universal computation
  (every automaton transforms state; few emulate Turing machines)

universal computation
  ≠ efficient computation
  (the emulation may be astronomically slower than native hardware)

universal computation
  ≠ practical programmability
  (no compiler exists for glider arrangements)

universal computation
  ≠ spontaneous computation
  (random starts compute nothing in particular)

universality
  ≠ Class IV
  (a visual label never proved a computational property)

universality
  ≠ visual complexity
  (Rule 30 looks wild and has no universality result;
   the identity rule looks dead and its status is trivial, not deep)

One consequence, correctly scoped: for universal systems, questions like “will this configuration ever settle” admit no general decision procedure — the halting problem reaches through the emulation. That undecidability belongs to universal systems under their encodings, not to cellular automata as a family.

Measure information flow experimentally

We can probe whether a perturbation influences a distant region.

Start two simulations differing by one bit:

a = initial.copy()
b = initial.copy()
b[source] ^= 1

After t steps, test a target region:

def region_difference(a, b, start, stop):
    return float(np.mean(a[start:stop] != b[start:stop]))

If the target eventually changes, information from the perturbation has propagated there.

This is a simple empirical causal experiment — a probe for influence, not a universality test. No simulation in this chapter pretends to prove a theorem; executable checks validate encodings and constructions, while the theorems live in the cited literature.

Computation versus simulation

These concepts overlap but are not identical.

A forest-fire CA computes its next state, but we usually interpret it as simulation.

A logical construction in Life uses the same mechanism but we interpret patterns as symbols and operations.

The distinction comes from the mapping between physical states and an abstract task:

cell dynamics
    ↓ interpretation
computation

Why this matters for artificial life

Artificial-life systems sit at an interesting boundary.

A persistent, organism-like structure is held together by local updates that depend on local information, as if every cell were answering:

Where is my boundary?
Was I damaged?
What is around me?
How should local cells respond?

That is a way of describing what each update depends on. It is not a claim that cells know anything, and it does not make the structure alive.

Neural cellular automata make that information processing explicit by replacing a hand-written transition rule with a learned local network.

But before neural rules, there is another remarkable step we should take.

We can remove the discrete binary state itself.

Instead of cells being simply alive or dead, let them take continuous values and interact through smooth kernels.

That is the road to Lenia.

Part III complete

We began this part with a simple question:

How do we compare cellular automata without relying entirely on our eyes?

We now have:

measurement
  ↓
activity + density
  ↓
entropy + compression
  ↓
cycles + attractors
  ↓
sensitivity
  ↓
behavioral classification
  ↓
exhaustive search
  ↓
large-space search
  ↓
evolution
  ↓
computation

The next part changes the substrate itself.

We move from discrete cellular automata toward continuous artificial life: smooth state, convolution kernels, growth functions, Lenia, multi-channel systems and eventually Flow-Lenia.

Research

• Cook, M. — Universality in Elementary Cellular Automata (Complex Systems 15(1), 2004). The theorem this chapter is built around: Rule 110 emulates a cyclic tag system and is therefore universal. Cite this — not the behavior, not the class label — for any Rule 110 universality claim. https://doi.org/10.25088/ComplexSystems.15.1.1

• Zenil, H. & Martinez, G. J. — Cellular Automata (Scholarpedia). Supplies the grades of universality this chapter distinguishes: Turing universality (simulating a universal Turing machine under an encoding) versus the stronger intrinsic universality (reproducing another automaton’s full space-time dynamics) — with the simulated class always specified. Also notes Cook’s construction depends on arranged patterns and periodic backgrounds. http://www.scholarpedia.org/article/Cellular_automata

• Berto, F. & Tagliabue, J. — Cellular Automata (Stanford Encyclopedia of Philosophy). The Life half of the comparison: universality via computing primitives (Berlekamp, Conway & Guy), Rendell’s explicit Turing machine, and the correctly scoped undecidability consequence — no algorithm decides eventual fate for universal systems, which is why their evolution must be run, not solved. https://plato.stanford.edu/entries/cellular-automata/