Cellular Automata From First Principles

A cell knows almost nothing. It sees a small neighborhood, applies a local rule, and changes state. Repeat that everywhere, again and again, and surprisingly rich worlds can appear.

Start with a line of cells.

Each cell is either on or off.

It looks only at its neighbors.

Every cell follows the same rule.

Then the entire world updates.

local state
    ↓
local neighborhood
    ↓
local rule
    ↓
next state
    ↓
repeat

That seems too small to be interesting.

Yet systems built from rules this simple can produce stable structures, oscillators, moving patterns, traffic flows, spreading fires, reaction-diffusion fields, universal computation, continuous artificial-life systems and learned local dynamics.

The question of this book is not merely whether those things can happen.

It is:

How much global structure can arise from local rules, and how do we know what we are actually seeing?

That second half matters.

A striking picture is not an explanation. A pattern that looks random is not necessarily random. A persistent object is not necessarily alive. A system that solves examples has not necessarily learned an algorithm. A faster implementation is not necessarily equivalent to the slower one.

So this book builds cellular automata from first principles and then subjects them to the same discipline throughout:

construct
→ observe
→ measure
→ challenge
→ verify
→ reject when evidence fails

That method eventually matters more than any particular automaton.

The local rule and the global world

A cellular automaton begins with a few ingredients.

State is what a cell currently contains.

Lattice is the space in which the cells live.

Neighborhood determines which nearby cells a cell can observe.

Rule maps the local neighborhood to the cell’s next state.

Schedule determines when updates occur.

Boundary condition determines what the simulated world does at its edge.

Those ingredients are local.

The phenomena we normally care about are not.

We ask about structures that persist across thousands of cells, signals that move, cycles that repeat, perturbations that spread, configurations that compute, forms that recover after damage, or rules that generalize beyond the examples used to train them.

The recurring tension of the book is therefore:

The rule is local. The behavior we care about is global.

The work between those two levels is where cellular automata become useful.

Simple does not mean predictable

One of the attractions of cellular automata is the size of the gap between description and behavior.

An elementary one-dimensional automaton has only:

• two possible cell states,
• three cells in each neighborhood,
• eight possible neighborhood configurations,
• and 256 possible rules.

That is small enough to enumerate completely.

But the trajectories of those rules are not equally easy to understand.

Some quickly die out.

Some settle into repeating structures.

Some produce long irregular histories.

Some support carefully constructed computation.

Moving from the rule table to the resulting world is therefore not always a matter of reading the rule more carefully.

That is our first encounter with a theme that returns throughout the book:

simple description
≠ simple behavior

But the reverse mistake is just as dangerous.

complicated-looking behavior
≠ complicated mechanism

Cellular automata give us an unusually compact laboratory in which both mistakes can be examined.

Similar words are not the same claim

The subject attracts strong language.

Patterns are described as chaotic, emergent, intelligent, alive, self-organizing, universal, adaptive or creative.

Sometimes those words are useful.

Sometimes they smuggle the conclusion into the description.

This book keeps several distinctions explicit:

irregular
≠ random
≠ chaotic

complex-looking
≠ computationally universal

persistent
≠ alive

robust
≠ adaptive

learned
≠ intelligent

high score
≠ desired phenomenon

faster
≠ equivalent

These are not semantic niceties.

Each pair requires different evidence.

Rule 30 can produce an extremely irregular signal without giving us a theorem that the signal is random.

Rule 110 is computationally universal under suitable constructions, but universality does not make it easy to program, efficient, or spontaneously computational from arbitrary initial conditions.

A neural cellular automaton can recover a target after damage without implying biological regeneration.

A search procedure can optimize a metric without finding the behavior we actually care about.

The book repeatedly returns to these boundaries because they are where interesting demonstrations most easily become exaggerated explanations.

What counts as evidence

The chapters use several kinds of evidence, and they are not interchangeable.

Established result means something grounded in the literature: a theorem, construction, documented model or known historical result.

Book experiment means something demonstrated by the executable examples in this book.

Measured observation means a result obtained from a stated run, metric, perturbation or comparison.

Interpretation is an explanation we place on top of those observations.

Open question means the evidence does not settle the matter.

That distinction becomes especially important when the subject reaches computational universality, artificial life and learned systems.

The book does not treat the existence of an impressive screenshot as evidence that an interpretation is correct.

Where possible, claims are made executable.

If two implementations are supposed to be equivalent, we compare them.

If a quantity is supposedly conserved, we measure it.

If a pattern is said to move, we measure displacement.

If a system is said to recover, we distinguish recovery of mass from recovery of morphology.

If a model is said to generalize, we test a condition outside the training example.

If an optimization is supposed to preserve semantics, we verify the outputs before celebrating the speedup.

The book begins with rules, not abstractions

The first chapters deliberately start small.

We build an elementary automaton directly.

Then we discover that the first hand-written rule already has a name: Rule 22.

We encode all 256 elementary rules.

We inspect Rule 30 and learn why deterministic does not mean visually predictable.

We move to Rule 110 and separate the existence of computation from the stronger property of computational universality.

Then the Game of Life takes us into two dimensions.

By the end of the foundations we are no longer looking only at pictures. We are building ways to recognize still lifes, oscillators, spaceships and other behaviors as data.

That transition is important.

The book gradually moves from:

look at the pattern

to:

measure the behavior

because visual inspection stops being sufficient surprisingly quickly.

Seven stages

The investigation proceeds through seven parts.

Part I — Foundations (Chapters 1–7)

We construct the basic machinery:

• elementary cellular automata,
• rule encoding,
• Rule 30,
• Rule 110,
• Conway’s Game of Life,
• pattern categories,
• pattern detection.

The aim is to understand exactly what a local update rule is before asking it to carry larger ideas.

Part II — Richer worlds (Chapters 8–17)

The models become less pristine.

We explore:

• Life-like rule families,
• probabilistic rules,
• spreading processes,
• traffic,
• diffusion,
• reaction-diffusion,
• predator-prey systems,
• cave generation,
• terrain,
• textures.

This stage introduces a critical engineering habit: every richer model brings new assumptions.

Boundary conditions matter.

Update order matters.

Conservation may hold in one model and fail deliberately in the next.

A system can resemble a physical or biological process without becoming a faithful model of it.

Part III — Measure and search (Chapters 18–27)

Looking is no longer enough.

We construct observables for:

• density,
• activity,
• spatial variation,
• entropy,
• recurrence,
• sensitivity,
• fingerprints.

Then we use them to classify, search and evolve rules.

This stage also contains one of the book’s strongest warnings:

The metric is not the phenomenon.

A rule can score highly for the wrong reason.

A novelty measure can reward something useless.

A fitness function can be exploited.

The stage ends by returning to computational universality and asking precisely what that word does — and does not — mean.

Part IV — Continuous artificial life (Chapters 28–36)

The state of a cell stops being only zero or one.

We introduce:

• continuous-valued state,
• kernels,
• growth functions,
• Lenia,
• automated discovery,
• parameter regimes,
• multi-channel systems,
• robustness,
• Flow-Lenia.

The conceptual machinery remains recognizably cellular:

local perception
→ local update
→ repeated global evolution

but the visual and dynamical possibilities become much richer.

That richness makes disciplined language even more important.

A persistent moving structure may be called a creature in artificial-life practice, but that is not a biological claim.

Robustness is not adaptation.

Recovery is not automatically regeneration.

Part V — Learned rules (Chapters 37–49)

Until this point, we designed the rules.

Now we ask:

What happens if the local rule itself is learned?

This begins with differentiable and neural cellular automata.

We build:

• neural update functions,
• hidden state,
• target growth,
• stochastic scheduling,
• persistence,
• damage recovery,
• generalization tests.

Then the substrate is asked to perform an algorithmic task: pathfinding through mazes.

That progression lets us ask progressively harder questions.

Did the model merely fit training examples?

Did it generalize to harder mazes?

Does information propagate locally?

Do hidden channels matter causally?

Has the system learned an iterative computation, or are we simply placing that interpretation on successful outputs?

The book keeps those questions open until experiments justify stronger language.

Part VI — Engineering (Chapters 50–58)

Interesting dynamics are not enough if the implementation is wrong.

The final technical stage turns the automata into reproducible software.

We examine:

• profiling,
• vectorization,
• GPU execution,
• FFT convolution,
• reusable engines,
• reproducibility,
• parameter sweeps,
• figure generation,
• laboratory practice.

Several real errors in the book were found only by executing the code:

• incorrect function signatures,
• nonexistent metric keys,
• undefined helpers,
• FFT kernel-centering errors,
• zero-padding where toroidal semantics were intended,
• CPU-only CUDA synchronization failures,
• batch-shape bugs.

That experience earns another recurring rule:

Optimize the verified implementation, not the first implementation that happens to render something plausible.

And:

runs
≠ correct

looks right
≠ equivalent

faster
≠ same semantics

Part VII — Capstone (Chapter 59)

The final chapter puts the method together.

It constructs candidates, observes them, measures them, challenges the strongest one, and asks whether the evidence supports the interpretation we would like to make. The criteria are stated before the search begins, so the verdict comes from the method and not from how attractive the result looks.

From observation to measurement

A recurring progression throughout the book is:

state
↓
trajectory
↓
observable
↓
measurement
↓
comparison
↓
search
↓
claim

Each arrow can fail.

A measure can collapse two very different behaviors into the same number.

A classifier can mistake a heuristic category for a theorem.

A search objective can reward an unintended shortcut.

A learned model can succeed on held-out examples without generalizing beyond the training distribution.

An optimized implementation can silently change the boundary semantics.

The book therefore does not stop at obtaining a result.

It asks what generated the result, what the measurement actually detects, and whether the conclusion survives a stronger test.

Artificial life without pretending

The continuous and learned chapters bring the book close to artificial life, and the literature reports compelling results there: Lenia patterns that persist and move, neural cellular automata that grow forms and recover from damage. Those results invite anthropomorphic language.

The book therefore treats words such as creature, species, regeneration and self-organization carefully. Sometimes they are established terminology within the artificial-life literature. Sometimes they describe a task setup. They are not evidence by themselves that a system is alive, adaptive or intelligent.

The question is always:

What property was actually demonstrated?

Learning changes who writes the rule

The transition to neural cellular automata changes something fundamental.

Earlier chapters ask:

What happens when we design this local rule?

The learned chapters ask:

What local rule does optimization discover for this objective?

The structure remains local.

Cells still receive nearby information and update local state.

But the rule is now parameterized and optimized through training.

That introduces a new separation:

training
≠ rollout

During training, parameters change.

During rollout, those parameters are frozen and the learned dynamics execute.

A system that appears adaptive during rollout may therefore be displaying dynamics learned earlier rather than learning in real time.

That distinction becomes central to how the book interprets regeneration, persistence, hidden state and generalization.

Failure is part of the method

The book does not hide unsuccessful results.

Some examples homogenize.

Some parameter choices collapse.

Some metrics are gamed.

Some configurations that look promising fail robustness tests.

Some implementations disagree until a bug is found.

Some learned models succeed only within a narrow distribution.

Those failures are useful because they tell us where the mechanism or the explanation stops working.

Research throughout the book

Every chapter ends with a ## Research section.

These are not decorative bibliographies.

They identify the papers, technical references and primary sources that materially changed or grounded the chapter.

Across the book they range from primary papers (Wolfram, Cook, Pearson, Drossel and Schwabl, Shannon, Chan, Mordvintsev and collaborators, Earle and collaborators, Lehman and Stanley) through encyclopedic overviews (the Stanford Encyclopedia of Philosophy, Scholarpedia, MathWorld) to software documentation and a reproducibility guide. Von Neumann, Ulam, Conway and Langton appear as history and context, reached through those sources.

The sources are used differently.

Some establish a theorem.

Some provide historical provenance.

Some define a model.

Some motivate an experiment.

Some establish that a claim remains open.

The text tries to make that distinction visible.

What you should be able to do after reading

By the end of the book, you should be able to:

• implement elementary cellular automata from first principles;
• encode and decode Wolfram rules;
• build two-dimensional cellular systems;
• reason about synchronous, asynchronous and stochastic updates;
• distinguish periodic and fixed boundaries;
• measure behavior instead of relying only on images;
• use entropy, recurrence, sensitivity and fingerprints carefully;
• search larger rule spaces;
• evolve candidate rules without confusing fitness with truth;
• explain what computational universality actually establishes;
• build continuous-state and Lenia-style systems;
• train a neural cellular automaton;
• distinguish training, rollout, persistence and regeneration;
• test generalization rather than assume it;
• investigate hidden-state propagation;
• optimize CPU/GPU/FFT implementations while preserving semantics;
• build reproducible experiments;
• and reject a compelling interpretation when the evidence does not support it.

The last skill may be the most important.

The larger idea

Cellular automata are often introduced as a demonstration that simple rules can create complex behavior.

That is true, but it is not enough.

The more interesting lesson is what happens after the surprising pattern appears.

We have to decide what to call it.

We have to measure it.

We have to test whether it persists.

We have to perturb it.

We have to distinguish a visual analogy from a mathematical result.

We have to know whether the implementation actually matches the rule we think we ran.

And when the evidence fails, we have to let the explanation fail with it.

So the deeper progression of this book is not:

simple rules
→ amazing complexity

It is:

simple rules
→ surprising behavior
→ measurement
→ explanation
→ challenge
→ evidence

A tiny local rule can create a world far richer than its description.

But complexity does not excuse us from explaining what we see.

Build the rule. Run the world. Measure the behavior. Challenge the explanation. Keep only what survives.

Continue with How Can Tiny Rules Build Complex Worlds?.