My PhD thesis is called The rich landscape of iterated simplicity: cellular automata and network automata. The whole of it turns on one observation. Take a row, a grid or a network of cells, each on or off. Give every cell the same small rule about what to do next, based only on its neighbours. Apply the rule to all cells at once, over and over. What comes out is anything from dead calm to noise, with fractals, gliders, synchronised flashing and majority votes in between. The thesis asks how much of that landscape can be read off the rule before running it, how the wiring changes the answer, and what the whole thing has to do with neural networks.
Each tab below is one chapter, told in plain words with a figure you can play with. The figures run in your browser, on a small scale; where the thesis needed a cluster, the number it found is quoted next to the live version. The thesis was a joint degree of Ghent University and the University of São Paulo, supervised by Jan Baetens and Odemir Bruno, with Aisling Daly as co-supervisor. The papers behind the chapters are on the research page; the Game of Life on networks, from the Physica D paper, has a demo of its own.
Two ants meeting is easy to describe; the colony's foraging is not. One neuron is tractable; a brain is not. The rules for elementary particles fit on a page, and out of them come weather, life and thought. Whether that kind of richness can come purely from simple rules applied over and over is an old argument in science, and this thesis adds a piece to it by studying the cleanest cases we have: cellular automata, and their cousins on networks.
A cellular automaton is a grid of cells, each in one of a few states, where every cell updates at the same moment by one fixed rule that looks only at its neighbours. Even the smallest version, one row of on-or-off cells looking left and right, draws a remarkable variety of pictures, and Conway's Game of Life on a grid can host gliders, oscillators and, given patience, a computer. Real systems, though, are rarely wired as grids. Cells, people and proteins interact along sparse, uneven networks with hubs and shortcuts. Put the same rule on such a network and you have a network automaton, a much less studied object, and the thesis's home ground.
The two chapters before those, Families and Networks, set up the vocabulary, and Answers collects what came out. The Cover tab is about the picture on the front.
The simplest cellular automaton is a row of cells that all follow one rule, all at once, each looking only at its direct neighbours. Every research field that uses cellular automata bends one item of that recipe, and my review paper sorted the bends into five families. The diagram is the one from the thesis: the plain version in the middle, the families around it. The arrows from the centre say what each family changes; the arrows round the rim are the identities that turn one family into another. Onthe page of the paper each family gets a tab of its own, with the identities run side by side.
Click a circle to see that family at work.
A row of cells, each 0 or 1. Every cell looks at itself and its two neighbours, three cells, so eight possible views, and the rule says what the cell becomes next for each of them. Eight yes or no answers make 28 = 256 rules, numbered 0 to 255 by reading the answers as a binary number. Everyone updates at once, and the row closes into a ring. Rule 110 is already enough for a working computer, in principle.
Two symmetries cut the 256 down to 88 genuinely different rules: a rule seen in a mirror, or with 0 and 1 swapped, draws the same pictures reflected or inverted, and the line under the table names both relatives. It also gives λ, Langton's parameter, the share of the eight answers that are 1. That is the simplest example of a genotype, a number read off the rule without running it, and the thesis keeps asking how far such numbers predict the phenotype, the picture the rule actually draws. Click the answers in the table to change the rule, or try 30, 110 and 184.
Nature has no central clock. Here each cell updates with some probability every tick and otherwise waits, so a probability of 1 is the elementary automaton again. Rule 90 draws neat nested triangles in lockstep; lower the probability and they fray, and at 0.5 little of the pattern is left. Rules that are tidy when synchronous often fall apart like this, a few become tidier, and the update scheme can even change which class a rule belongs to.
Round the rim: fix in advance which cells wait, and this becomes a non-uniform automaton whose second rule is 204, the rule that changes nothing. Read time as one more dimension of space, and an asynchronous automaton becomes an ordinary synchronous one in one dimension more.
Give each cell two rules, φ and ψ, and let it flip a weighted coin every tick to choose between them. With ψ = 204, the rule that leaves a cell as it is, this is exactly the asynchronous family, which is the arrow between the two circles: try it and compare. With two proper rules the rows form a Markov chain, and as the weight of the coin moves, the behaviour can change abruptly, a phase transition. And when all cells switch rules together, two rules that are each chaotic can jointly settle into a periodic pattern. Start again draws new coins.
More than two states per cell. The rule space explodes: with three states and three cells there are 327, about 7.6 trillion, rules. So the figure keeps the rules that only look at the total of the three cells, a number from 0 to 6, and the buttons give the next state for each total: 37 = 2187 rules. The one it opens with, code 1599, is a famous one: from a single cell it keeps growing irregularly for thousands of ticks before it settles. Click a total to cycle its answer, or ask for a random rule.
Round the rim: states and neighbourhood size can be traded against each other, and a non-uniform automaton with two rules is secretly a uniform one with four states, one for every combination of a state and a rule.
Let each cell see further, or in more directions. Two cells on either side instead of one already gives 232, over four billion, rules. The best-known member of this family, though, is the Game of Life: a grid in two dimensions where each cell counts its eight neighbours. A dead cell with exactly three living neighbours is born, a living cell with two or three survives, and everything else dies or stays dead. In the usual shorthand that is B3/S23, and the grid below opens with it.
Pick other numbers to be born or to survive with and you get the other Life-like automata, 29 × 29 = 262,144 of them. That is exactly the number of network automata the Synchronisation tab starts from, and not by coincidence. Keep the counting but put the cells on a network, and each cell simply counts whatever it is wired to: the neighbours no longer come in any order, so counting is all a sensible rule can do. Those are the Life-like network automata that the thesis studies from the Two numbers tab onwards, and on a grid where every cell has eight neighbours they are these rules exactly.
Things to try. From one cell, Life dies at once, but Gnarl (B1/S1) and Replicator grow a whole pattern. HighLife is Life with one extra way to be born. Clear, to draw gives an empty grid: draw a row of three cells and it blinks; draw a small shape and see whether it survives. You can draw while the grid runs, too. Life itself also opens the first tab, and the cover is made of it.
Instead of a coin every tick, decide once which cells follow the second rule ψ, and freeze that choice. The tinted columns follow ψ. The share of cells on φ is the degree of non-uniformity ν, and ν = ½ is as mixed as it gets. The extreme case is one cell that does something different, and the most extreme version of that is a cell that never changes at all, a clamped cell. That stuck cell is the seed of the Impact tab, where clamping one node tells us how much it matters, and non-uniform rows come back in CA as CNN, where a neural network runs them. Try one cell on ψ = 204 inside rule 90, or rule 30 against rule 90.
A network is a set of nodes and the links between them, nothing more: people and friendships, metabolites and reactions, atoms and bonds. The links are the whole story. Two nodes are neighbours if a link joins them, and a node's degree is how many links it has. What made networks a science in their own right, in the late 1990s, was the discovery that real ones are neither grids nor random tangles. Watts and Strogatz noticed that real networks are clustered like a grid, your friends know each other, and yet short like a random network, everyone is a few steps from everyone: the small world. Barabási and Albert noticed that many have a few enormous hubs and a long tail of poorly connected nodes, because new links prefer nodes that already have many.
The thesis does not model any real network. It uses three families of synthetic ones as dials that run from grid-like to random and from all-nodes-alike to hub-dominated, and asks what a rule does along each dial. All three are in the figure. Colour the nodes by a centrality, click a node for its six values, and press the sweep to see how the small-world index moves with the rewiring.
A ring, rewired. Start with a ring where every node is linked to its k/2 nearest neighbours on each side, the wiring of a one-dimensional cellular automaton with a wider reach. Then visit each link and move each of its two ends, with probability p, to a random node. At p = 0 it is the ring; a few shortcuts make it a small world; at p = 1 it is as good as random. The shortcuts are drawn in blue. A grid, rewired. Much the same, starting from a torus with four, eight or twelve neighbours and moving only one end of a chosen link, exactly the three neighbourhoods a two-dimensional automaton uses. A signal has two dimensions to spread in before any rewiring, which matters later. Preferential attachment. Grow the network one node at a time; each newcomer links to m existing nodes, picking node i with probability proportional to kiα + 1. At α = 0 everyone is equally attractive and there are no hubs. At α = 1 the rich get richer in proportion to their wealth, the classic Barabási–Albert model, and the degrees follow a power law. Above 1 a single hub grabs a large share of all links, and at α = 3 nearly all of them: not a more heterogeneous network, a different kind of network altogether.
How small is small. The usual measure of small-worldness compares clustering with a random network, and by that yardstick almost everything is a small world. The thesis uses Telesford's index ω instead, which compares the path length with the random end of the dial and the clustering with the lattice end: ω near −1 means lattice-like, near +1 random-like, and the band between −½ and ½ is the small world. The sweep draws ω against p on a logarithmic axis, because that is where the action is. In the thesis the band sits between p ≈ 0.01 and 0.15 for rings and crosses zero near p ≈ 0.05; for grids it crosses near p ≈ 0.09. The point is that six evenly spaced p values, the obvious choice, miss the small world of the rings entirely: at p = 0.2 a ring is already random-leaning, ω ≈ 0.65, while a grid at p = 0.2 just scrapes into the band, ω ≈ 0.35. So the thesis uses evenly spaced p where the gradual loss of local structure is the topic, and logarithmically spaced p where the small world is. One more trap: p is not the same amount of rewiring in the two families, since the ring routine moves both ends of a link and the grid routine one, so 2p − p² of the ring's links change against p of the grid's.
Six ways of being central. Degree is the obvious one. Average neighbour degree asks how well connected your neighbours are, which turns out to be almost unrelated to your own degree. The h index is the largest h such that h of your neighbours have at least h links, a coarse but cheap blend of the two. Eigenvector centrality is recursive: you score high by being linked to nodes that score high. Betweenness counts how many shortest paths between other nodes run through you, the bridges. Closeness is how few steps it takes you to reach everyone. In the thesis's networks degree, the h index and eigenvector centrality move together, and the others each say something of their own; in the preferential-attachment family several of them have heavy tails. The last chapter asks which of the six, if any, predicts how much a node actually matters.
What runs on them. Networks are substrates. Epidemics on hub-heavy networks have no threshold: the hubs keep the disease alive however weak it is. In the voter model a node copies a random neighbour, and a zealot that never changes its mind can tilt the outcome, which is the idea behind the clamped node of the last chapter. In threshold models a node flips once enough of its neighbours have, and the Life-like rules of the next chapters are threshold rules with the threshold replaced by an arbitrary pattern. And a network automaton is what you get when every node runs the same deterministic rule on its neighbours' states at once. Because nodes have no natural order and different degrees, the rule may only count: how many neighbours are on, or what share of them. Rules of that kind are called outer-totalistic, and every network automaton in this thesis is one.
Things to try. Ring, degree 8, drag p up from 0 with the log scale on and watch ⟨l⟩ collapse long before ⟨C⟩ moves. Grid with four neighbours: no triangles, so ω is undefined. Preferential attachment at α = 0, 1 and 3 with the colour set to degree, then to average neighbour degree, and look at who is dark. Click the hub and then one of its leaves.
Take a rule, a random row of cells, and a copy of that row with one cell flipped. Run both. The cells where the two runs disagree form the difference pattern, the red picture below, and how fast it grows is the natural measure of how sensitive a rule is. For a smooth system one would write down a derivative and get a Lyapunov exponent. Here the smallest change is a whole cell, but a derivative exists all the same: flip cell j, does cell i change next tick? Yes or no. That is theBoolean Jacobian, a 0-1 matrix that depends on the current configuration, and it predicts the difference pattern exactly for one tick. After that it generally fails, and it fails at once, not gradually: a rule's response to two flips is not the sum of its responses to each, and there is no small parameter to make the error small.
There is a second object, and telling the two apart is the chapter's first job. Multiply the Jacobians along the run, over the integers rather than modulo 2, and the entries count thebranching walks along which influence can travel from the flipped cell to each cell at each tick. Those counts can grow without bound, as 2t or 3t, and their growth rate is what the Lyapunov spectrum of a discrete system actually measures. The difference pattern is the same matrix applied in a different arithmetic: over the integers two walks arriving at one cell add, over the binary field they cancel. In general neither determines the other. For exactly sixteen rules, the affine ones, whose rule is a sum modulo 2 of some of the three inputs, possibly plus 1, the difference pattern is the parity of the walk counts at every tick, which is also why rules 90 and 150 draw the Sierpiński triangle: their walk counts are binomial and trinomial coefficients. The figure runs the twins, counts the walks on a logarithmic colour scale, and reports the first tick at which parity and pattern part company.
For those sixteen rules everything can be written down. The Jacobian is constant, it is a circulant matrix on a ring, and the spectrum of a circulant matrix is a discrete Fourier transform: the singular values are σk = |a∘ + (a₊ + a₋) cos θ + i (a₊ − a₋) sin θ| with θ = 2πk/N, and the Lyapunov exponents are their logarithms, no simulation and no limit involved. The largest is always the logarithm of the number of inputs the rule is sensitive to: ln 2 for rule 90, ln 3 for rule 150, the largest of any elementary rule. The same holds on a torus in any dimension, so the parity rule with four neighbours and yourself reaches ln 5, with eight ln 9, with twelve ln 13, and it holds for the parity rule on any undirected network, where the Jacobian is the adjacency matrix itself, plus the identity if a node counts itself. There the Lyapunov spectrum is, up to a logarithm and an absolute value, the spectrum of the graph, and the chaos of the rule is a property of the wiring. A consequence you can watch: under a rule like this any pattern reappears at t = 2, 4, 8, 16 as one copy per sensitive input, shifted by that many cells, because at a power of two every walk count but those is even.
The network version below computes the eigenvalues of the adjacency matrix of a network you choose and turns them into the spectrum. Since the largest eigenvalue of a connected graph is at least its mean degree, the maximal exponent is positive on any connected network with more than one link per node: in the walk-counting sense the parity rule is sensitive everywhere. Beside it the rule runs twice from starts one node apart, and the red count of differing nodes shows what the spectrum does not: it is bounded by the number of nodes, it saturates, and on a finite network it eventually cycles. Exponential growth lives in the walk counts only.
For any rule that is not affine the spectrum has to be estimated, and the estimator is Benettin's: carry an orthonormal frame along the run, multiply it by each Jacobian, re-orthonormalise, and average the logarithms of the stretch factors after a burn-in. The exact spectra are what made the estimator auditable, and the audit found something: the spectra of rules 60, 90 and 150 published in an earlier paper had been computed by multiplying the matrices directly, which overflows and loses every direction but the fastest, so their largest exponents were off and their lower tails missing. The chapter recomputed all twelve rules from that paper with a burn-in and the affine ones came out at exactly ln 2, ln 2 and ln 3. The button on the first figure runs the estimator on a ring of 48 in the background and, for an affine rule, prints its error against the closed form.
What the chapter is careful not to claim is that any of this predicts the red picture. Across all 88 distinct elementary rules the sign of the maximal exponent is informative, since a rule with exponent −∞ leaves no lasting damage, but its size is not: the affine rules have the largest exponents and among the sparsest difference patterns. The spectrum is an exact, basis-free account of the roads along which influence can travel through a rule and a wiring; how much traffic uses them is another matter, and the next chapter measures that by simulation.
Things to try. Rule 30 in the twin figure and watch parity and pattern part at tick 2 or 3; then a random affine rule and watch them never part. Rule 150 with 99 cells: a multiple of 3, so some exponents are −∞. In the torus figure, count yourself off and play: four copies instead of five. In the network figure, the ring at rewiring 0 with degree 6, then at 1, then preferential attachment at α = 3 and look at where the top exponent lands relative to the mean degree.
From here on the thesis lives on networks, and the rule it runs is the Game of Life stretched to fit. Life's rule counts neighbours: born with exactly three, survive with two or three. On a network one node has two neighbours and the next has twenty, so counting will not do. Count the shareinstead: ρ, the fraction of a node's neighbours that are on, a number between 0 and 1. Cut the unit interval into r equal pieces and let the rule say, for each piece, whether a dead node is born there and whether a live node survives there. Two sets of pieces, born B and survive S, written as the binary numbers β and σ, and the rule is φrβ,σ. With r = 9 on a grid of eight neighbours the nine pieces are the nine possible counts and Life is back as φ98,12. The family goes by the name Life-like network automata, from the earlier work that first used it to classify networks; there are 22r rules at each r.
The first job of the chapter was to make that definition consistent, and the trap is at the edges of the pieces. Swapping every on for off is a symmetry cellular automata have always had, and to keep it on a network the cut of the density axis has to mirror round ½: below the middle a piece includes its left end, above the middle its right end, the middle piece is closed at both ends, and r has to be odd for there to be a middle piece. With that cut, every rule has an equivalent rule that does the same thing with the colours swapped, and 2r rules are their own equivalent. Earlier work used the obvious cut, every piece closed on the left, and the symmetry quietly breaks whenever a density lands exactly on a boundary, which on a network with small degrees happens all the time. The last figure on this tab shows the break happening.
The diagram below is the rule, and its mean-field curve is the first of the two numbers: at ρ = ½ the curve's height is the Hamming weight, the share of all inputs that give a live node. It is the same diagram as on the other demo, where the curve is explained at more length.
The second number is the Boolean sensitivity: pick a random input, flip one of its k + 1 bits, the node's own state or one neighbour's, and count how often the outcome changes, averaged over everything. It splits in two on the diagram. Identity sensitivity counts the pieces filled in only one of the two rows, where the node's own state decides; neighbourhood sensitivitycounts how often a row changes colour between one reachable density and the next, the jaggedness of the picture. Both are tinted and marked in the figure. The sensitivity is also the slope at the origin of the Derrida curve: take two copies of a random configuration that differ in a share δ of the nodes, run both one tick, and ask what share differs now. A slope above 1 means a small difference grows, below 1 it dies. And it is the expected number of ones in a row of the Jacobian of the previous chapter, which is why the two chapters belong together. Neither number needs a simulation; both need only the rule and the degree.
The degree matters more than one would think. Slide k and watch the marks move: a node with four neighbours can only see the densities 0, ¼, ½, ¾ and 1, so it skips four of the nine pieces of a nine-piece rule, and a node with twenty-four sees almost only the middle piece. On a network with a spread of degrees the honest numbers are the averages over that spread, which the bars on the right show for four kinds of network; for the hub-heavy family it makes a visible difference.
The two numbers are not independent. Every flip that changes the outcome joins an input that gives 1 to one that gives 0, so a rule with few 1s cannot be very sensitive: BS ≤ 2(k + 1)·min(HW, 1 − HW), a tent with its top at HW = ½, where the parity rule sits with every flip counting. Below is every rule of one resolution as a dot under that tent. Click one and it lands in the figure above.
So much for the genotype. The phenotype is what the rule does when run, and the chapter measured two time series to match the two numbers: the share of nodes that are on, and the share that differs between two runs started one node apart. The rule below, Morley, φ9328,52, shows how much the network has to say about both: on the grid it converges gradually, on a rewired grid suddenly, and on a random network sometimes not at all, with sharp transitions in between as the start density or the rewiring changes. The thesis then ran all 528 non-equivalent rules of resolution 5 on 900-node grids, plain, rewired and random, 900 samples each, and correlated genotype with phenotype: the Hamming weight predicts the final share on with R = 0.70 to 0.73, the sensitivity predicts the final share differing with R = 0.54 to 0.55. Good enough to throw away most of a rule space without running it; not good enough to skip running the rest. That is the sentence the next chapters lean on.
One last figure, for the appendix on the symmetry. Below, a rule and its equivalent run side by side on the same random network, one from a random start and the other from the exact negative of that start. Under the thesis's mirrored cut of the density axis the two runs stay negatives of each other for ever, and the red rings never appear. Switch to the older uniform cut and the rings appear on the first tick at nodes whose degree is a multiple of five, where a density sits exactly on a boundary and the two cuts disagree; from there the difference spreads. The readout works through the bit arithmetic: mirror the survive set, toggle it, and you have the born set of the equivalent rule.
Things to try. HighLife at k = 4 and at k = 12 in the sensitivity figure: same rule, different numbers. Rule 150 written as φ32,5 at resolution 3 and degree 2, where it is rule 150 itself: the sensitivity is 3, every flip counts; then slide the degree away from 2. In the scatter, resolution 7 at degree 6, and hunt for the corners of the tent. In the Morley figure, the lattice at 50% on, then 75%, then the same on the random network.
Here is a task that is easy to state and hard to do. Start a network in a random mess and have every node end up flashing on and off in step, all on, all off, all on, for ever. Each node sees only its neighbours; nobody sees the whole; and the rule is the same for everyone. This is the global synchronisation task of Das and colleagues, a cousin of the firing squad problem, and the usual way to find a rule that does it is a genetic algorithm: breed thousands of rules, simulate all of them, keep the winners, and accept an answer you cannot explain. Das and colleagues spent something like ten to a hundred million simulations that way.
The two numbers from the previous chapter make a bottom-up route possible. A good synchroniser should be its own equivalent, since the goal looks the same with the colours swapped; that is a bitwise condition, and it leaves 512 of the 262,144 rules at resolution 9. Its mean-field curve should lie above the anti-diagonal 1 − ρ left of ½ and below it right of ½, so that ½ is an unstable balance and every tick pushes the density further out while flipping it; at degree 8 that leaves 27. No simulation so far: one bit test and one curve per rule, a fraction of a second for all 512. The figure does it in front of you. Change the resolution and the degree, or ask for the condition at every degree from 4 to 12 at once, and watch the count.
Which of the 27 is best is not something the genotype can say. There is a trade-off, visible in the scatter: rules with a steep mean-field slope, which leave ½ quickly, have low sensitivity, and the sensitive rules have a gentle slope. So the thesis ran all 27 on rings of a thousand nodes, degree 8, rewiring 0.2, for 2000 ticks, 900 samples each. Twenty-two never synchronised once. Three managed more than a tenth of the samples. One, φ923,47, managed 83 percent, and the runner-up 65. The winner sits at the sensitive end of the trade-off, which suggests that for this task, on these networks, chaos matters more than speed. Click any dot to run it on a ring below and to load it into the big figure further down.
The success rate depends on the network in ways the rule knows nothing about. On rings of degree 6 the winning rule never synchronises from a balanced start, at any rewiring; on rings of degree 10 it nearly always does once p is above 0.15. At degree 8 the dependence on rewiring is a hump: nothing below p = 0.04, a steep rise, a peak of 94 percent near p = 0.3, and a slide back to 39 percent on a fully random network. Short paths are necessary but not sufficient; some of the ring's local structure has to survive for the synchronised state to spread. On rewired grids, which have two dimensions to spread in, the rule scores 96 percent at p = 0.2 and 82 percent with no rewiring at all, then falls to about 40 percent as p goes to 1; with four neighbours it never works, with twelve it always does. The sweep button above reproduces the hump on a ring of 300 nodes with a dozen trials per point, which is enough to see the shape and not enough to trust the decimals. The figure below is the same synchroniser with everything at hand, and it starts on the grid.
Now the second half of the chapter, and the one the last chapter of the thesis will need. Toggle every outcome of a rule, on to off and off to on, and its mean-field curve flips top to bottom. A curve that flung the density away from ½ while flipping now flings it away while freezing: 0 and 1 become stable, ½ stays unstable, and the rule seeks consensus, every node the same and staying that way. The Derrida curve is unchanged by the toggle, so the sensitivity that made a good synchroniser carries over. The consensus button in the filter applies this second condition; at resolution 9 it gives 27 rules at degree 8, 106 that satisfy it at some degree between 4 and 12, and 12 that satisfy it at every one of them. The thesis ran all 106 on all 54 combinations of network family, degree and rewiring or attachment, 900 samples each, for 100 ticks, and measured consensus by the entropy of the density, which is 1 for a fair split and 0 for unanimity.
Two things came out. Most candidates fail: on a rewired grid of degree 8 only two rules, φ9488,464 and φ9432,484, reach unanimity in more than half the samples, the best in 96 percent, and the fifth-best in under four. And none of the winners is in the set of 12 that pass the test at every degree; every one of them pairs a high sensitivity with a slope that is modest, and for some degrees actually below 1. The chaos compensates for the mean-field's indifference. As for the networks: degree 4 hardly ever reaches consensus, an unrewired ring never, degree 12 always once rewired, and the best rule differs from family to family, which is why the appendix has a table of them. The figure below runs φ9488,464; note that it also judges whether the unanimous answer matched the starting majority, which is a stricter question than the thesis asked and one these rules often get wrong.
Things to try. In the filter, resolution 5 at degree 8: five candidates, and the ring run tells you which of them are any good. Resolution 11 at every degree: 26 survive, all of them tame. Pick the consensus condition, click the most sensitive dot, then run the sweep and compare it with the synchroniser's hump. In the big figures, twenty trials on the lattice with the rewiring at 0, then at 0.3, then at 1.
A convolutional neural network slides a small window over its input, takes a weighted sum in each position, adds a constant, and passes the result through a nonlinearity. A cellular automaton looks at a small window round each cell and applies a rule. The chapter's first claim is that these are the same thing, and not approximately: a two-layer convolutional network with its weights written down by hand reproduces an elementary cellular automaton bit for bit, with nothing learned. The first layer has eight channels, one for each of the eight three-cell neighbourhoods. Channel i gives weight +1 to the cells that are on in its pattern and −ω to the cells that are off, adds 1 minus the number of ones in the pattern, and applies a ReLU, which sets anything negative to zero. The sum is exactly 1 where the pattern is present and at most 0 anywhere else, so across the eight channels every cell lights up exactly one, and that works for any ω of at least 1. The second layer is a one-cell-wide convolution whose eight weights are the rule table; it adds up the channels, and the result is the next row. Forty numbers, all fixed. The figure spells the arithmetic out.
The interesting step is the next one. In a convolution every position uses the same weights. Let cells follow different rules, the non-uniform automata of the second tab, and that assumption goes. Deep-learning frameworks have a layer type for exactly this case, the locally connected layer, whose weights differ from position to position. So the network becomes: the eight detectors, then one rule table per rule, giving every rule's answer for every cell, then a layer that picks, for each cell, the answer of its own rule. Non-uniformity of the rule is, to the framework, non-sharing of weights; the automaton is the architecture. The selection layer can be written two ways, and the parameter count in the figure shows the difference: locally connected, it holds one weight per rule per cell; dense, it holds a full matrix, one weight per rule per pair of cells, almost all of them zero. For 32 cells and eight rules that is 352 against 8,288. The dense one was nonetheless the faster in the TensorFlow benchmarks, because one big matrix product beats a loop of small ones. Paint the allocation below and watch the diagram change.
Then drop the grid. On a network there is no left and right and no fixed number of neighbours, which is what the graph-neural-network literature calls message passing: each node gathers the states of its neighbours, aggregates them with a function that does not care about their order, and combines the result with its own state. A Life-like network automaton is precisely that. The aggregation is the mean, ρ; the combination is a fixed lookup, which interval ρ falls in and what the born or survive row says there. One line of PyTorch Geometric for the mean, a lookup for the rest, no parameters to learn, and one forward pass is one tick. That class ran every simulation of the Jaggedness and Impact chapters. Click a node below and follow one message-passing step.
The second half of the chapter's question, whether this is any faster, gets an honest answer. Against a plain Python loop the convolutional emulator wins once its fixed overhead of a few seconds is spread over about a hundred cells or a few hundred samples, and the graph version wins by orders of magnitude. Against a vectorised sparse-matrix implementation in SciPy the graph version is two to four times slower on a CPU, because at these sizes the arithmetic is cheap and the time goes into dispatching operations. Nobody tested the GPU. So the correspondence is exact; the speed depends on what you compare it with; and the value of the construction is that a cellular automaton can be stated in the native vocabulary of a deep-learning framework, with its rule table as the weights. The next chapter turns that round and asks what such a network learns when it is not told the rule.
Things to try. Show the sums before the ReLU and drag ω: the red gets redder and the ones stay exactly one. Rule 110 with cells fed back a few times. In the painter, rules 30 and 90 as two halves, then one odd cell of rule 204 in a sea of rule 30. In the message passing, a node with two neighbours and one with eight, and the same rule.
People have sorted the 256 elementary rules by behaviour since Wolfram's four classes. The chapter uses the five of Li and Packard, because every rule gets exactly one and you can see the class in the picture: null, everything turns one colour; fixed point, it settles; periodic, it repeats with a short period; locally chaotic, chaos fenced in by walls; chaotic, noise throughout. There are 24, 97, 89, 10 and 36 rules in them. Below is one example of each, from a random start. You can name them at a glance, and so, it seemed, could a convolutional network: earlier papers trained one on spacetime diagrams and reported 98 to 100 percent.
The chapter's question is what that network was looking at. Here is the trouble. Take three neighbouring cells in one row and the cell below the middle one: a T-shaped tetromino. That is one entry of the rule table, read straight off the pixels. Slide it along the first row of a 64-cell diagram from a random start and you will meet all eight neighbourhoods more than 99 times in a hundred. So a network whose filters are 3 wide and 2 tall can simply read the rule, and since every rule has one class, it can then output the class without ever looking at the behaviour. The thesis built that network by hand, the same eight detectors as the previous tab plus a readout, 2,360 fixed numbers, and it identified the rule in 99.87 percent of diagrams. Then it trained the standard network from the earlier papers, with its 3 × 2 filters, and asked it not for the class but for the rule: it got the exact rule right 99.85 percent of the time. The high class accuracies were real, and they proved nothing about recognising behaviour. The figure lets you do the scan yourself.
Two things can push a network away from the cheat. One is architecture: filters no tetromino fits in, 2 × 2 instead of 3 × 2; a wide field of view, 8 × 8 cells instead of 5 × 3, so it has room to see a pattern; and a tiny final layer, so it has no room to memorise 256 rules. The trimmed network has 389 parameters against 7,301. The other is data augmentation, feeding the network altered pictures whose class has not changed but whose rule table has: colours inverted, left and right swapped, 2 × 2 blocks averaged, or noise sprinkled in. Try each in the figure and see what the scan recovers: the complement, the mirror image, contradictions, or a table that makes no sense, while the picture is plainly still periodic or still chaotic. With the first three augmentations, and not the noise, which did not help, the trimmed network reached 98.17 percent on the class, and the same architecture trained to name the rule managed only 61 percent over the 88 genuinely different rules. That is the chapter's honest verdict on itself: a shift towards the behaviour, not a clean break from the rule. Its most frequent mistake is calling periodic diagrams fixed point, a difference in time that its global pooling barely sees; locally chaotic, the smallest class, is recognised least often, 93 percent of the time. And no rule was ever held out of training, the first limitation the chapter names.
Things to try. Rule 30, then press play and watch the table complete within the first row. Rule 59 and a few new starts: three white cells in a row are rare, so one entry can stay unknown. Invert rule 110 and see rule 137 come out; mirror it and get 124. Coarse-grain anything and watch the table contradict itself.
Turn the previous chapter round. There, a network looked at pictures to tell rules apart; here a fixed rule draws the pictures, and the network it ran on is the unknown. Run a Life-like rule on a network you know nothing about, look at the pattern it draws, node by node and tick by tick, and guess what kind of network it was: random, small world, scale-free, geographic; a metabolism, a social circle, a molecule. This works, and has been used since 2016: automaton, fingerprint, classifier. The pattern's statistics are the fingerprint, and a plain linear classifier is enough, which tells you the work is being done by the automaton and the fingerprint. The catch is that only a few rules produce patterns that tell networks apart, nobody knew why, and finding them meant trying all of them. Four thousand at resolution 6, over a quarter of a million at 9.
Several of the rules that worked, though not all, had a look about them. Their diagrams were jagged: born and survive intervals scattered along the density axis rather than sitting in a block. That suggests a story. A smooth rule hardly reacts to a change in the neighbourhood and freezes or cycles, too dull to carry a signal; the maximally jagged rule, the parity rule, reacts to everything and its chaos wipes the structure out; somewhere in between the pattern is rich enough to encode the wiring and calm enough to keep it. So count the colour changes. Walk along each row of the diagram and add one every time the colour flips between neighbouring intervals: that count is the jaggedness J, out of 2(r − 1) possible, and J̄ is its share. It is the neighbourhood sensitivity of chapter five with the network taken out, exact when the degree is r − 1, and by construction it knows nothing about the identity sensitivity or the Hamming weight. The figure counts it for you; the arrowheads are the changes.
The lower half of that figure is the second idea. The rule space at resolution r splits into groups by J, and the size of each group is 4·C(2(r − 1), J): four rules with no colour change, four with all of them, and a bulge in the middle. If jaggedness predicts quality, you need not search the whole space. Search two or three groups at a small resolution, take the group that held the best rule, step to the next resolution and search only the groups with about the same J̄, and repeat. A single step can multiply the rules examined by more than the factor four by which the family grows, but averaged over a path the factor drops below four, so the share of the space you ever look at shrinks as you go; the thesis checked every path from resolution 3. In the thesis the search reached resolution 6 having looked at about a fifth of the rules and found one within five percent of the best; sampling four rules in ten inside each group brought that to a tenth of the rules, within four percent.
Does jaggedness predict quality? The chapter tested every rule from resolution 3 to 6 on 23 collections of networks, a hundred ticks each, with the fingerprint of Zielinski and colleagues and a linear classifier, five folds three times over. On 13 of the 23, all the synthetic and metabolic collections and one social one, jaggedness correlates with accuracy, modestly but consistently, with coefficients between 0.21 and 0.46, and the best rules sit at J̄ between 0.5 and 0.9, almost never at 1. On the other social collections and on the molecules nothing correlates with anything, and even an exhaustive search does poorly there: those networks have average degrees between 0.5 and 5, so a node can only ever see a handful of densities and most of the interval boundaries are never probed. The suggestion, untested, is to keep the resolution close to the typical degree plus one. The surprise of the chapter is that this network-free number predicts accuracy at least as well as the network-aware sensitivity. Why is an open question.
The figure below is the first module of the pipeline, without the classifier. The rule you set above runs on four kinds of network from the same start, drawn as node × time rasters with the nodes sorted by degree, and under each is a fingerprint: the distribution over nodes of how unpredictable each node's time series was. Slide J up from 0 with the random-rule button and watch the rasters go from frozen stripes to structured to noise, and watch when the four fingerprints stop looking alike.
Things to try. The alternating rule φ9170,340 from the 2016 paper against the smooth φ9503,120. A random rule with J = 2, then 8, then 16 at resolution 9. Switch the fingerprint to flips per tick and compare the scale-free network with the geographic one. Then set the resolution to 4 and notice how few rules there are to choose from, and how coarse the cut is.
Which node in a network matters most? The textbook answer is a centrality measure: the one with the most links, the one on the most shortest paths, the one closest to everyone. Those are facts about the wiring. Whether they translate into influence depends on what is actually happening on the network, and that is usually unknown: we know who talks to whom, not how anyone makes up their mind. So the last chapter of the thesis asks for a probe that needs no knowledge of the true rule, and finds one in the consensus-seeking rules of the previous chapter. Run one of them and the whole network ends unanimous, all on or all off, a clean two-valued readout, and the rule was picked to be as touchy as possible along the way. Colloquially, as the chapter puts it: these networks are completely alive, and our methods try to kill them.
The figure below is the setting. Pick a family, and the rule the thesis found best for it is loaded with the share of samples it brought to unanimity. Every start is drawn at half on and chosen so that, left alone, the network ends all on. Now click a node. It is clamped dead: it starts off and is held off for the whole run, whatever its neighbours do. The blue run is the clamped one, the grey run is the untouched one, the red rings show where they differ, and the verdict says whether one stuck node reversed the outcome, did nothing, or left the network stuck between the two.
The thesis turns that into two measurements. The first is observational and uses the centralities. Take a start that ends all on, find the most central node that is on and the least central node that is off, swap their states, and rerun; then swap the next pair, and the next. The share of runs that now end all off, plotted against the number of swaps, tells how far the outcome is decided by where the central nodes start. On preferential-attachment networks of degree 8, ranked by closeness, ten swaps or fewer push the average final share on below one in ten, whatever the power α; up to α = 1.5 that means nine runs in ten flipped, at α = 1.5 two swaps do it, and at α = 2 and 3 some runs stall in between. Swapping random pairs instead merely shuffles the start, and the outcome drifts to a coin toss without ever reaching the nine-in-ten mark. On rings and grids the picture is more nuanced: the h index is a blunt instrument because so many nodes share a value, eigenvector centrality is sharp, especially on the eight-neighbour grid, and the average neighbour degree is useless everywhere. The figure runs twenty realisations on a network of 300 nodes, the chosen ranking against the random reference, and reports m₉₀, the number of swaps at which the curve passes 90 percent.
The second measurement is interventional and uses no centrality at all. Clamp one node dead for the whole run, over many starts that would otherwise end all on, and record how far from all on the network ends: η = 1 − ⟨ρT⟩, the node's dynamical importance. Then do it for every node. Nothing about the wiring is computed; the network only has to be simulated. The figure does exactly that in the background and colours the nodes as the scores arrive, then scatters η against whichever centrality you choose and prints the rank correlation for all six.
What the thesis found, on networks of a thousand nodes and 300 starts each, is that η correlates with centrality but reduces to none of the six. On rings and grids the correlation rises with the rewiring, because on a near-regular network the centralities barely differ between nodes and there is nothing to rank. On preferential-attachment networks degree predicts η well at low α, the correlations dip around α = 2 and recover at 3, plausibly because at α = 2 several hubs of similar weight shield one another, so clamping one of them changes little, while at α = 3 one super-hub stands alone again. And on those networks, at degree 6 and 8, the average neighbour degree is negatively correlated with η: a node whose neighbours are hubs cannot move them, since each hub has many other inputs, while a node whose neighbours are poorly connected owns a large share of their attention. Reaching many neighbours makes a node influential; having neighbours with few alternatives makes the influence stick. No single centrality measure says that.
The chapter is candid about what this is not. The score is a property of a node under one probe, one rule, one horizon, and the thesis used one rule per setting; it mixes clampings that changed the node's start with ones that did not; its own reliability was not measured; and it has not yet been set against an independent dynamical model such as an epidemic. Those are the next steps, and they are why this chapter is the one still being written up.
Things to try. In the sandbox, preferential attachment at α = 1 with 200 nodes: clamp the hub, then release it and clamp a leaf next to the hub, then a leaf far from it. Then the same at α = 3, where the hub is enormous and clamping it does surprisingly little. In the swap figure, rank by average neighbour degree and watch nothing happen. In the scoring figure, score a ring at rewiring 0.2 and at 1, and compare the correlations; then preferential attachment at α = 0, 2 and 3.
The thesis set itself one question per chapter, and the last chapter collects the answers in a table together with the limitation that most qualifies each one and the step that would remove it. Here is that table as cards. Each links back to its tab.
Only affine rules admit an exact linear description of how a defect spreads. For them the Lyapunov spectrum follows without simulation: from the Fourier transform of the rule’s stencil on a lattice, and from the spectrum of the adjacency matrix for the parity rule on a network.
Complementation symmetry requires the mirrored, odd-resolution cut of the density axis. The Hamming weight predicts the final density and the Boolean sensitivity the final defect density at the mean-field level (R ≈ 0.7 and 0.55), up to deviations the network causes and the rule alone cannot see.
Two analytical conditions reduce the resolution-9 rule space by four orders of magnitude, to 27 candidates; one of them synchronises most rewired rings and grids but fails at low degree and on the unrewired ring. A symmetry turns the same conditions into consensus conditions and yields a consensus-seeking rule for every network class except the sparsest.
Exact simulation is possible without a single learned parameter, for non-uniform automata in a CNN and for Life-like network automata in a GNN. The embedding beats only a pure-Python baseline; against vectorised sparse matrices the GNN is two to four times slower on a CPU.
Without precautions the network identifies the rule, because a spacetime diagram contains the rule table. Trimming and augmentation cut rule recovery from over 99 to 61 percent while class accuracy stays at 98: a shift, not a decoupling.
Jaggedness, a network-free simplification of the neighbourhood sensitivity, correlates with classification accuracy on 13 of 23 datasets and supports a search that gets close to the exhaustive optimum at a fraction of its cost. Where it fails, no other rule property succeeds either.
A few targeted swaps redirect the consensus where random swaps only randomise it, and clamping yields a dynamical importance score that needs no structural computation. The score correlates with centrality but reduces to no single measure.
The frame is the genotype and the phenotype. The Defects chapter introduced the Boolean Jacobian, the object that records which inputs a rule is sensitive to, and showed that only for affine rules it stays constant along a run. Two numbers replaced the run by a random configuration and reduced the Jacobian to its expected row sum, the sensitivity, next to the Hamming weight as the expected output. Everything downstream that picks rules without running them uses those two numbers: the synchronisers and consensus-seekers, and the jaggedness, which is the neighbourhood sensitivity with the network taken out. The separation of wiring from rule is exact in one place, the parity rule, whose Lyapunov spectrum is the graph's spectrum; everywhere else it is a factorisation, the Jacobian being the adjacency matrix times a state-dependent factor, and what the genotype does not see is what the wiring does beyond its degree distribution. That remainder was measured by simulation, and then the question was turned round: if wiring shapes dynamics, dynamics carries information about wiring, for a whole network in Jaggedness and for one node in Impact. The two directions meet in one finding: the rules that tell networks apart best are jagged, and the rules that coordinate a network best are sensitive, and both of those measure how strongly a rule's output responds to a change in its input, so both favour sensitive rules.
Three strands, and the thesis names the third as the one to pursue first. Inference:reading the network back from its dynamics, here done for the class of a network and for the rank of a node, is done elsewhere edge by edge; and the networks on which a dynamics-first instrument would earn its keep, empirical ones with partial structural knowledge, are exactly the ones not yet tried. Learning: neural cellular automata learn their rules, graph neural networks contain network automata as a special case, and learned models are more accurate on the classification benchmarks; what the hand-written automaton keeps is that its rule can be read and its genotype computed, and the fixed-weight emulator is the special case of a neural automaton in which nothing is learned. Control: clamping is pinning control with a rule-agnostic, two-valued readout; a faster emulator would let the two kinds of clamping be separated, the score's reliability measured, and the step taken from ranking single nodes to choosing a set of them, which is influence maximisation, with applications from epidemics to marketing.
The closing statement of the thesis connects all this to the gap between the local operations inside a trained neural network and the intelligence they bring forth, which is the concern of AI interpretability and the direction its author is heading. Among its closing lines: evaluation by behaviour does not reveal mechanism, structure does not determine function, and knowing the rule is not the same as knowing what it does.
The front of the thesis is a picture made entirely of pieces of the Game of Life that never move. A still life is a pattern the rule maps to itself: every live cell has two or three live neighbours, every dead cell anything but three. The smallest with a hollow inside is the pond, a ring of eight cells. Ponds tile into diamonds, the border of such a diamond, the lake, is itself a still life, and inside a lake there is room for other still patterns. Level ℓ is the number of ponds along the diamond's side; a level-ℓ tile is 6ℓ cells across. The question is how many eightfold-symmetric still lifes fit inside a lake of each level, and the answer was found not by searching but by asking an integer-programming solver for them one at a time, densest first, excluding each solution as it came: 1, 2, 7, 85, 2632 for levels 1 to 5. At level 6 the solver has not finished; the appendix's table lists 332,321 tiles there, and the counts keep exploding beyond.
With a bank of tiles whose densities cover the range, a greyscale picture becomes a mosaic: sample the picture once per diamond, on two interlocking diagonal grids, and lay down the tile whose density is nearest to how dark that spot is. Because every tile has the same lake for an edge, the assembled picture is a still life by construction. That is the figure below, built from the same tile bank that draws the backgrounds of this site, with the level-5 bank thinned to a few tiles per density. Press play and nothing happens, which is the point. Then click anywhere: a glider lands, hits the nearest lake, and the picture unravels into gliders, oscillators and rubble, because the stability of the whole depends on the integrity of every neighbourhood. Your own photograph works too.
Things to try. Level 3 has seven tiles and a coarse portrait; level 5 a fine one. Lower the cutoff so the light background stays empty. Invert for a light picture on a dark ground. Drop one glider near the edge and watch how far the damage travels before the rubble settles, then drop three.