Five ways to bend a cellular automaton

The recipe

Every family starts from the same recipe, the elementary cellular automaton or ECA, written as six items:

1. cells $c_i$ in a row, one for every integer $i$;
2. states $S = \{0, 1\}$;
3. the state of cell $c_i$ at tick $t$, written $s(c_i, t)$;
4. a start $s(c_i, 0) = s_0(c_i)$;
5. a neighbourhood $\mathcal{N}(c_i) = \{c_{i-1}, c_i, c_{i+1}\}$;
6. a rule $\phi$ that turns the three states of the neighbourhood into the next state:

Three cells of two states make eight neighbourhoods, and a rule is a 0 or a 1 for each: $2^{2^3} = 256$ rules, numbered 0 to 255 by reading the eight answers as a binary number $W(\phi)$. A rule seen in a mirror, or with 0 and 1 swapped, draws the same pictures, which leaves 88 genuinely different ones. A few of those, like rule 110, are complex enough to compute anything.

The five families each change one item. Three of them change item 6, the rule: the asynchronous family changes when a cell applies it, the stochastic family lets a coin choose it, and the non-uniform family lets it depend on the cell. The multi-state family changes item 2, the states, and the extended-neighbourhood family item 5, the neighbourhood. The paper's central diagram puts them round the elementary automaton, with an arrow from the centre for what each family changes and an arrow between neighbours for the identity that turns one into the other:

There is a seventh item, hidden in the first. A computer holds a finite row, so the cells at the ends miss a neighbour, and something has to fill it in. The paper lists eight boundary conditions; a ring, where the last cell's right neighbour is the first cell, is the usual one and the only one in which no cell ever sees an edge. The choice can change the picture well beyond the edge cells:

One more pair of words runs through all the tabs. Some tools read a cellular automaton off its rule without running it: Langton's $\lambda$, the share of neighbourhoods that do not map to 0, or the sensitivity, how often flipping one input flips the output. That is the genotype. Other tools read it off the pictures it draws: Wolfram's four classes (homogeneous, periodic, chaotic, complex), Lyapunov exponents that measure how a flipped cell spreads, entropies. That is the phenotype. Each family tab ends with which of these tools survive the bend, because that is where the price of realism shows.

Asynchronous: no central clock

A cellular automaton claims to be fully local, and then it lets a global clock tell every cell when to move. Nature has no such clock. In an asynchronous cellular automaton (ACA) a cell at each tick either applies the rule or keeps its state. The most common version flips a coin for every cell: with the synchrony rate $\alpha \in [0, 1]$,

where $\tilde{s}(\mathcal{N}(c_i), t)$ is the tuple of states in the neighbourhood. At $\alpha = 1$ this is the elementary automaton, at $\alpha = 0$ nothing moves. Call $Z(t)$ the set of cells that update at tick $t$: here its size is binomial, about $\alpha N$, and the family is the catalogue of ways to choose it. Fully asynchronous schemes update one cell at a time. A random independent ACA picks that cell at random, again and again. A random new sweep shuffles the row into a fresh order every $N$ updates, so no cell goes twice before all have gone once; a random fixed sweep shuffles once and keeps the order; line by line updates the cells from left to right, so every cell sees one neighbour that has just moved. The same rule under all of them, one row per sweep, which is how such diagrams are usually compared:

Rule 126 on a clock draws nested triangles. Take the clock away and they fray, differently for every scheme: the random ones end in noise, while a fixed sweep and line by line settle into a checkerboard. Line by line is not even random, and it fills the row in its very first sweep: every cell reads its left neighbour's new state, so a change can run the whole length of the row at once.

Fixed schemes carry a paradox. Updating cells in a fixed order, or with fixed periods, replaces the global clock with a global timetable: in the paper's words, one tyrant overthrows another. Such a deterministic $Z(t)$ is mathematically convenient, though: Worsch showed that for all deterministic choices of $Z(t)$ a single asynchronous automaton with a radius-1 rule can simulate all the others, so choosing the timetable for a rule is the same as choosing the rule for a timetable. And if $Z(t) = Z$ never changes, the cells outside it simply never move: that is a non-uniform automaton whose second rule is 204, the rule that changes nothing. The same trick, with a coin, is the identity with the stochastic family.

Whether the steps are counted in computer time or physical time, with waiting times drawn from an exponential distribution, makes no real difference: time runs one way, so the two can always be mapped onto each other.

What survives

The genotype survives intact: $\lambda$ and the other rule-table parameters describe $\phi$, which is still one elementary rule. Global properties do not, since attractors and periodic orbits now depend on $Z(t)$ too, and closed expressions exist only for special cases, such as the catalogue of rules whose periodic points do not depend on the order of a fixed sweep. The phenotype can be read in the usual way, as long as the diagrams are cropped to one update per cell on average, as above. It changes, though: asynchrony can move a rule to another Wolfram class, and even among the sixteen one-neighbour automata, simpler than the elementary ones, nine change their behaviour under some form of full asynchrony. Asynchrony is sometimes required, too: a whole row cannot be made to flash in step from every start by any synchronous deterministic rule, but it can by going beyond that, a problem my thesis takes up on networks.

Stochastic: a coin picks the rule

Randomness drives the formation of structure in nature, morphogenesis for one, and a stochastic cellular automaton (SCA) lets every cell, every tick, flip a coin between two rules:

At $p = 1$ this is the elementary automaton again. Make $\psi$ rule 204, which returns the cell's own state, and the coin decides whether the cell moves or waits: that is the asynchronous automaton with $\alpha = p$, the arrow probabilistic update sequence in the diagram. Below, both run from the same start with the same coins; change $\psi$ and they part.

Two rules only disagree on some neighbourhoods, and on the others the coin makes no difference, so most SCAs are only partly random. At the other extreme, rule 0 against its complement 255 with $p = \tfrac12$ ignores the neighbourhood altogether: pure noise. In between sits the majority SCA, rule 232 (follow the majority) against 51 (do the opposite of what you did), with its obvious link to how opinions spread.

More generally, the chance of a 1 can depend on the neighbourhood itself. Eight neighbourhoods, eight probabilities:

The two-rule SCA is the special case where each probability is $p\,\phi + (1-p)\,\psi$ of that neighbourhood, which is also how Fatès defines diploid automata. Other special cases keep only a few of the eight free, like the Domany–Kinzel automaton, whose equivalence to an Ising model matters to percolation theory.

The multi-state tab adds a twist. Read the state of a cell as the probability that it is 1, and the stochastic automaton becomes a deterministic one on the continuous states $s_i \in [0, 1]$:

with $b_j(n)$ the bit of neighbourhood $n$ that belongs to cell $j$. The figure runs the stochastic automaton once, runs it 200 times and averages, and runs the continuous automaton next to it. Pick a mix of two rules or set the eight chances by hand.

The continuous automaton gets the first tick exactly right. After that it multiplies the chances of neighbouring cells as if they were independent, while two neighbours share most of their history. That makes it the mean-field approximation of the SCA rather than its exact twin; the paper presents the correspondence without this caveat, and the figure is my addition. From one cell, rule 22 half the time leaves few cells alive in most runs, and after 60 ticks its continuous twin predicts about three times as many 1s as the runs actually have.

The coin can also be global: all cells follow $\phi$ together, except that with a small chance $\pi$ the whole row takes a step of $\psi$ instead, a noisy hiccup. For all 3825 pairs of genuinely different elementary rules, Roy and colleagues found that two chaotic rules can combine into a periodic one this way, and that the behaviour can jump at particular values of $\pi$.

What survives

A rule-table parameter such as $\lambda$ can be averaged over the two rules, weighted by the coin, but there is no reason the SCA should behave somewhere in between its two rules, and in general it does not. The global picture changes character: successive rows form a Markov chain, so the questions become ergodicity and absorption times rather than attractors. The phenotype loses two classes outright, since randomness disturbs any homogeneous or periodic pattern, and complexity can no longer mean computing power: there are no universal SCAs. What SCAs gain is phase transitions, sudden changes of behaviour as $p$ passes a threshold, and a paradox: randomness can make a model more stable. A deterministic cellular automaton for the Ising model of a magnet runs into what Vichniac called a feedback catastrophe, nothing like a real magnet; a temperature-dependent probability per neighbourhood cures it.

More states

Nature rarely comes in two states: a forest has trees, fire and ash, an epidemic has the susceptible, the infected and the recovered. A multi-state cellular automaton (MSCA) lets the state set $S$ be any set, finite or not, with or without structure. The price is paid at once. With $k$ states and $|\mathcal{N}|$ neighbours there are $k^{k^{|\mathcal{N}|}}$ rules: three states instead of two turn the 256 elementary rules into $3^{27} \approx 7.6 \times 10^{12}$. A ternary rule is numbered like an elementary one, $\sum_{i=0}^{26} 3^i s_i$, and most work sticks to totalistic rules, which only look at the sum of the neighbourhood: $k^{(k-1)|\mathcal{N}|+1}$ of them, 2187 for three states.

States can stand in for neighbours. Smith showed in 1971 that a cellular automaton with any neighbourhood is equivalent to one with a neighbourhood of three and more states, by pooling cells into blocks: a block and the two blocks beside it contain everything its own cells look at. So three neighbours are enough in general, and the trade is between the number of states, the size of the neighbourhood and the number of cells. Below is the paper's example: a two-state rule with five neighbours on 50 cells, and the 32-state rule with three neighbours on 10 cells that does the same thing. Try other block sizes, or any other of the $2^{32}$ radius-2 rules.

That is one half of the arrow more time steps or fewer cells between this family and the next. The other half trades time instead of cells: the paper shows the same five-neighbour rule simulated by an eight-state rule with three neighbours on the same number of cells, taking two ticks for each one.

Let the number of states grow without bound and the states fill an interval: a continuous cellular automaton, close kin to coupled map lattices and to the finite-difference schemes that solve differential equations. Rucker objected that they are therefore redundant; what sets them apart is the habit of experiment rather than proof. The stochastic tab shows one of them at work. Fuzzy cellular automata take a middle road: write an elementary rule in logic, rule 18 for example as

and let and, or and not act on degrees of truth between 0 and 1. The result can behave nothing like the original: fuzzy rule 90 from a random start settles on 1/2 everywhere, while Boolean rule 90 never settles at all.

What survives

Most of the genotype survives: Langton introduced $\lambda$ for rules with at least five neighbours and four states in the first place, and roughly matched it to the four Wolfram classes. The sensitivity needs care, since flipping a state now has more than one outcome. Global properties are often out of reach, partly because the relevant questions are undecidable, unless the states have structure, such as linearity. The phenotype can still be sorted into classes, but local measures need the states to mean something: the density of 1s makes no sense when the states are S, I and R, and a change of state is no longer one thing. For continuous states, the tools of coupled map lattices serve better than those of cellular automata.

Wider neighbourhoods

Hardly anything depends only and exactly on its two nearest neighbours, and hardly anything sits on a perfect line. An extended-neighbourhood cellular automaton (ENCA) keeps all neighbourhood information in an adjacency matrix $\mathbf{A}$, with $A_{ij} \neq 0$ when cell $c_j$ is a neighbour of $c_i$, and lets the rule read the neighbourhood at earlier ticks too:

The mildest version widens the neighbourhood to a radius $r$, with $2r + 1$ cells and $k^{k^{2r+1}}$ rules; $r = 2$ already gives over four billion. In two dimensions the usual neighbourhoods are von Neumann's, the four adjacent cells, and Moore's, which adds the diagonals, the simplest of Cole's templates

for the offsets $\mathbf{a}$ of the neighbours in $n$ dimensions. Any cellular automaton in $n$ dimensions can be reduced to one in a single dimension with a wider neighbourhood, and one on a regular tiling can be simulated on another, hexagons for squares, at the cost of more states. Beyond tilings lie Voronoi cells, Penrose tilings and hyperbolic space, and finally network automata, where the cells are the nodes of any network, the neighbourhood of a node is whoever it is linked to and its size, the degree, differs from node to node. That is where the Game of Life on networks of my Physica D paper lives.

The arrow to the asynchronous family, network wiring or ±1 dimension, stands for several results. Golze built a synchronous automaton in one dimension more from an asynchronous one, by reading time as space; Aracena and colleagues showed equivalences of this kind for Boolean networks under different update schedules. The simplest instance I know is below, my own illustration rather than a construction from the paper. Updating the cells one by one from left to right is the same as updating them all at once, provided each cell reads the previous tick through the right wiring: cell $i$ depends on every cell from the far end of the ring up to its right neighbour, through a composite rule of its own. Asynchrony becomes wiring, and a non-uniform one at that.

The neighbourhood can also change over time, as in the structurally dynamic automata of Ilachinski, or reach into the past. An automaton with memory lets the rule read earlier ticks, and a memory of two ticks makes any rule reversible. Only six of the 256 elementary rules can be run backwards, all of them trivial, yet

can always be undone: given the two latest rows, the same formula gives back the row before them. Here the rule runs forward to the marks and then backward, and ends exactly where it began. Rule 30R is the paper's example; any rule works. Toffoli showed more: any cellular automaton can be simulated by a reversible one with one dimension more.

What survives

A wider neighbourhood leaves every definition intact and only makes the rule table longer: Langton's parameter was first studied with five neighbours. Global properties stay well defined but grow unwieldy, which is why totalistic rules are popular here. In a network the degree differs from node to node, so a rule table no longer fits, and the rule usually looks at the weighted share of neighbours in state 1,

which is open to analysis, only not the classical kind. Network science then does more for the genotype than cellular-automaton theory does. In the phenotype, Wolfram's classes carry over to two dimensions but not everything carries to three, network automata show all four classes, and anything with a direction, like a Lyapunov exponent, has to follow paths through the network instead. The wiring alone can cause a phase transition, and adding a memory of up to ten ticks changes the behaviour of almost half of the elementary rules.

More rules

The last family drops the rule that all cells share. In a non-uniform cellular automaton (νCA) the rule depends on the cell and the tick; the simplest has two elementary rules and a set $Z(t)$ of cells that follow the first:

with $\nu$ the degree of non-uniformity, maximal at one half. With $\psi$ rule 204 this is the asynchronous automaton with $\alpha = \nu$, and the family is again a catalogue of ways to choose $Z(t)$. Fixed once and for all, there are $2^N$ allocations. A random one gives each cell a coin once; redraw it every tick and it is the stochastic automaton, the arrow probabilistic rule allocation. A single rogue cell models a permanent fault; a periodic allocation, the first $\nu T$ cells of every stretch of $T$, is the one that admits formulas; a clustered one models regions, such as water and soil in a model of a forest fire.

The last panel lets the neighbourhood choose: rule 153 on the symmetric neighbourhoods 000, 010, 101 and 111, rule 102 on the others. That is no longer non-uniform at all: it is the uniform rule 195, whose bits are the bits of 153 where 153 applies and those of 102 elsewhere. The paper's example; any pair works.

The allocation can also run by its own rule. Let a third elementary rule $\xi$ update, every tick, which cells follow $\phi$:

Now every cell carries two bits, its state and its rule, and both evolve by a uniform rule of the neighbourhood. Four combined states, three neighbours: a uniform quaternary automaton, the arrow mapping onto product states. The paper's figure uses $\phi = 110$, $\psi = 170$ and $\xi = 240$, which shifts the allocation one cell to the right every tick; the rule number in the status line is the paper's, computed here from the three elementary rules, digit for digit.

In general a νCA with $l$ rules and $k$ states is a uniform automaton with $kl$ states and the same neighbourhood. The converse fails, because there are far fewer of the former:

about $256^3 \approx 1.7 \times 10^7$ against $4^{64} \approx 3.4 \times 10^{38}$ here: most quaternary rules are not of this form, because the two bits of a combined state must each follow an elementary rule of their own. At the far end of the family, hybrid automata let a global parameter, such as the wind in a fire model or the temperature in Vichniac's Ising model, steer the rule: useful in applications, out of reach of formulas.

What survives

Much of the classical genotype rests on one rule table applied everywhere, and fails without it. Rule-table parameters can be averaged over the rules, but the paper suggests something less arbitrary: where a uniform automaton that simulates the νCA exists, as above, read the parameters off its rule table. The paper knew of no one who had tried this. Some global properties have been worked out, such as which νCAs built from elementary rules conserve the number of 1s or can be reversed. The phenotype is almost unexplored: two rules can already be allocated in about $2^N / N$ ways on a ring of $N$ cells, and they can cooperate in unpredictable ways. Nearly every local measure stays well defined, and one is new: sensitivity to the allocation itself. Give a single cell the other rule, like the rogue cell above, and ask how far that difference spreads. The simplest νCAs are also convolutional neural networks with their weights written down by hand, which my thesis uses to run many of them at once.

What it adds up to

The five families build up to the paper's main conclusion:

The variants of the cellular automaton are not a melting pot but a family tree: five families, each bending one item of the classical definition, tied together by exact mathematical identities, and in which every gain in realism is paid for in mathematical elegance.

Three observations stand out. First, a paradox: the cellular automaton is meant to be strictly local, yet most of its families impose some global or random choice on the cells, a timetable, a coin, an allocation, a parameter. Second, the trade-off: more realism and more applications almost always come with less mathematical elegance and fewer general methods, as the table shows. Third, the overlap: the identities round the rim mean that one question can be attacked from several families at once, and they connect research communities that rarely read each other.

The paper ends on the two families it sees as best placed to reveal more: non-uniform automata and network automata, close to well-documented families, easy to simulate in bulk and widely applied. That is where the rest of my PhD went: the thesis studies Life-like rules on networks, how far their rule alone predicts their behaviour, and non-uniform automata as neural networks.

A caveat about this page. The identities are exact and the figures check them cell for cell, but each family is represented by its simplest members, one-dimensional rows of two-state cells with two rules at most. The paper covers much more ground, from Penrose tilings to fuzzy logic, in words and references rather than simulations.

Read more

• A comprehensive taxonomy of cellular automata
  M. Rollier, K. M. C. Zielinski, A. J. Daly, O. M. Bruno, J. M. Baetens
  Communications in Nonlinear Science and Numerical Simulation 140, 108362, 2025 · preprint
• A survey of cellular automata: types, dynamics, non-uniformity and applications
  K. Bhattacharjee, N. Naskar, S. Roy, S. Das, Natural Computing 19, 2020. The closest earlier survey.
• Progress, gaps and obstacles in the classification of cellular automata
  M. Vispoel, A. J. Daly, J. M. Baetens, Physica D 432, 2022. The genotype and phenotype tools this page keeps coming back to.
• A guided tour of asynchronous cellular automata
  N. Fatès, 2014. The asynchronous family in depth.

Keys once a figure has focus: n draws new coins or a new start. The address bar follows the settings, so a view can be linked.