WatchNo. 04
The uncanny shapes of chaos
An ant that follows two rules makes a mess for about ten thousand steps, then at step 9,977 starts building a road it never leaves, and nobody has proved every start ends that way. A die that picks corners at random draws a Sierpinski triangle, sand poured on one square settles into the same mandala whatever order it topples in, fireflies and a footbridge’s crowd fall into step, and rule 30 turns a tidy rule into noise with a $30,000 prize still unclaimed.
Explore it yourself
The explorations this episode covers
The Ant That Builds a Road
Langton’s ant follows a tiny rule invented in 1986: on an all-white square grid it turns right on white and left on black, then flips the square’s colour and moves forward one square. From this start, a repeating diagonal path appears after about 10,000 steps; this finite wrapping grid lets you inspect its formation, not prove its infinite continuation.
The Chaos Game
Barnsley’s chaos game marks three corners of a triangle and starts on one of them. Pick a corner at random, move half the way there, and leave a dot; repeat from where you landed. Starting at (0, 0) in the triangle (0, 0), (1, 0), (0, 1), a draw of (1, 0) puts the dot at (0.5, 0). The dots never fill the triangle: they land on the Sierpinski gasket, the holes Pascal’s triangle shows when each entry is reduced modulo 2. The random draws decide the order the dots appear in, not the shape they appear on.
The Sandpile That Draws Itself
Pour sand onto one square of an endless grid. Any square holding four or more grains topples: it gives one grain to each of the four squares it touches along an edge, and this repeats until no square holds more than three. Pour four grains and one toppling settles them. Pour sixteen thousand and the finished pile is an intricate, symmetric pattern of squares holding 0, 1, 2 or 3 grains, though the rule mentions no pattern. The order of topplings does not change the result, which is proved; the pictures keep resembling one another as the pile grows, which this page shows and measures rather than proves.
Fireflies That Keep Time
Each of 120 fireflies has its own natural rhythm and a random starting phase, the point in its cycle where it flashes. In Kuramoto’s 1975 model every firefly nudges its phase towards the others, harder when the coupling K is bigger. Below a critical coupling the flashes stay scattered and the order measure r stays near the level scattered phases give; above it a cluster locks together and r climbs towards 1. For rhythms spread in a bell curve of width 1, the limit of infinitely many fireflies puts that coupling at about 1.6; a run of 120 only blurs around it.
Rule 30: Order That Makes Chaos
In an elementary cellular automaton, each cell of a new row is black or white according to a lookup of the three cells above it, eight cases in all, so there are 256 rules. Rule 30, started from one black cell, makes stripes down its left side and what looks like noise down its right; this page grows it row by row and counts the black cells in its centre column, which are an observation here and not a proof of randomness.
Notes and references
Langton’s ant
The ant sits on a grid of squares. On a plain square it turns one way, colours the square and steps forward; on a coloured square it turns the other way, clears the square and steps forward. Started on an empty grid it makes an irregular mess for about 10,000 steps, then falls into a repeating pattern of 104 steps that moves it two squares diagonally each time, a road it keeps building for as long as anyone has run it. The episode counts the road as starting at step 9,977; the Langton exploration’s detector reports 9,976 because it counts from step 0, so the two agree about the same moment. Bunimovich and Troubetzkoy proved in 1992 that the ant’s trajectory is always unbounded, whatever finite set of squares is coloured at the start. That every finite start eventually builds a road is a conjecture, still open; Gale, Propp, Sutherland and Troubetzkoy state it as a question in 1995. Gajardo, Moreira and Goles showed in 2002 that the ant can carry out any computation, given a suitable start, which is one reason not to expect a short argument for the road.
The chaos game
Mark three corners of a triangle, start a dot anywhere, and repeat: roll a die to pick a corner and move the dot halfway towards it. Each jump halves the dot’s distance to the finished picture (the attractor), at the least, so after a few dozen jumps where it started no longer shows, and the dots that follow trace the Sierpinski triangle. The order of the rolls does not change the picture, only that each corner keeps coming up. The same game with more rules draws other shapes: the commonly quoted recipe for Barnsley’s fern uses four affine maps picked with probabilities 1, 85, 7 and 7 in 100. The exploration states the theorem that a set of such maps has a unique attractor and cites Hutchinson and Barnsley for it.
The sandpile
Pour grains on one square of a grid; any square holding four or more grains topples, passing one grain to each of its four neighbours, and the pile is finished when no square can topple. Dhar’s abelian property (1990) says the finished pile does not depend on the order in which the unstable squares are toppled, which is why the picture is the same however the toppling is arranged; the exploration proves the order-independence itself and does not lean on the paper for it. The model was introduced by Bak, Tang and Wiesenfeld in 1987 as a system that drives itself to a critical state. Pegden and Smart proved in 2013 that as the number of grains grows the rescaled piles converge in a weak sense: averages over regions settle down, though the individual squares do not. The mandala is a picture of that limit, not a claim about every square.
Fireflies and the footbridge
Kuramoto’s 1975 model gives each oscillator its own natural rhythm and lets each be pulled by the others. When the coupling is weak they drift apart; past a critical strength a growing share of them lock together, and Strogatz’s 2000 review describes what was and was not rigorous about that threshold. Sarfati, Hayes and Peleg (2021) recorded swarms of the fireflies Photinus carolinus and report that their synchrony organises itself from the insects’ interactions; the exploration does not claim that fireflies obey the Kuramoto equations. Pantaleone (2002) showed metronomes on a movable base falling into step. The Millennium Bridge in London opened on 10 June 2000, swayed sideways under the crowd and was closed two days later; it reopened in February 2002 after dampers were fitted. Strogatz and colleagues proposed in 2005 that the walkers’ footsteps fell into step with the sway once the crowd passed a critical size. That is a proposed explanation and a model, not a measurement of opening day. The engineers’ account is Dallard and colleagues (2001).
Rule 30
In rule 30 a row of cells is rewritten from the three cells above each one by a fixed table of eight cases. Started from a single cell it draws a triangle with a regular edge on one side and, inside it, what looks like noise. Wolfram proposed in 1986 that the centre column makes good random bits, and Mathematica’s random integers were generated from it. The Rule 30 Prizes, announced in October 2019, are three problems of $10,000 each, $30,000 in all: whether the centre column ever becomes periodic, whether its two colours occur equally often, and whether finding its nth cell takes at least on the order of n steps of work. As of 27 October 2026 rule30prize.org lists no winner. The shell Conus textile has a pigment pattern that looks like rule 30’s; that is a resemblance and not an identity, and no claim is made that the shell follows the rule.
Simple rules, repeated
Each of the five systems is a few lines of rule, repeated. What is proved about them differs, and the notes above say which is which: the ant’s unbounded path is a theorem and its road is a conjecture; the chaos game’s picture and the sandpile’s order-independence follow from the rules; the footbridge is a proposed model; and whether rule 30 is as random as it looks is open, with a prize for an answer.
How the site classes a statement as proved, checked or open is set out in the method.
References
- L. A. Bunimovich, S. E. Troubetzkoy, Recurrence properties of Lorentz lattice gas cellular automata, Journal of Statistical Physics 67(1–2), pp. 289–302, 1992. Link to Recurrence properties of Lorentz lattice gas cellular automata
- D. Gale, J. Propp, S. Sutherland, S. Troubetzkoy, Further travels with my ant, The Mathematical Intelligencer 17(3), pp. 48–56 (preprint on arXiv), 1995. Link to Further travels with my ant
- A. Gajardo, A. Moreira, E. Goles, Complexity of Langton’s ant, Discrete Applied Mathematics 117(1–3), pp. 41–50, 2002. Link to Complexity of Langton’s ant
- M. F. Barnsley, Fractals Everywhere (second edition), Academic Press (publisher’s listing), 1993. Link to Fractals Everywhere (second edition)
- P. Bak, C. Tang, K. Wiesenfeld, Self-organized criticality: An explanation of the 1/f noise, Physical Review Letters 59(4), pp. 381–384, 1987. Link to Self-organized criticality: An explanation of the 1/f noise
- D. Dhar, Self-organized critical state of sandpile automaton models, Physical Review Letters 64(14), pp. 1613–1616, 1990. Link to Self-organized critical state of sandpile automaton models
- W. Pegden, C. K. Smart, Convergence of the Abelian sandpile, Duke Mathematical Journal 162(4), pp. 627–642, 2013. Link to Convergence of the Abelian sandpile
- Y. Kuramoto, Self-entrainment of a population of coupled non-linear oscillators, International Symposium on Mathematical Problems in Theoretical Physics, Lecture Notes in Physics 39, pp. 420–422, 1975. Link to Self-entrainment of a population of coupled non-linear oscillators
- S. H. Strogatz, From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators, Physica D: Nonlinear Phenomena 143(1–4), pp. 1–20, 2000. Link to From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators
- R. Sarfati, J. C. Hayes, O. Peleg, Self-organization in natural swarms of Photinus carolinus synchronous fireflies, Science Advances 7(28), eabg9259, 2021. Link to Self-organization in natural swarms of Photinus carolinus synchronous fireflies
- J. Pantaleone, Synchronization of metronomes, American Journal of Physics 70(10), pp. 992–1000, 2002. Link to Synchronization of metronomes
- S. H. Strogatz, D. M. Abrams, A. McRobie, B. Eckhardt, E. Ott, Crowd synchrony on the Millennium Bridge, Nature 438(7064), pp. 43–44, 2005. Link to Crowd synchrony on the Millennium Bridge
- P. Dallard, T. Fitzpatrick, A. Flint, A. Low, R. Ridsdill Smith, M. Willford, M. Roche, London Millennium Bridge: Pedestrian-induced lateral vibration, Journal of Bridge Engineering 6(6), pp. 412–417, 2001. Link to London Millennium Bridge: Pedestrian-induced lateral vibration
- S. Wolfram, Random sequence generation by cellular automata, Advances in Applied Mathematics 7(2), pp. 123–169, 1986. Link to Random sequence generation by cellular automata
- S. Wolfram, Announcing the Rule 30 Prizes, Stephen Wolfram Writings, October 2019, 2019. Link to Announcing the Rule 30 Prizes
- MerlinCharon, Conus textile (photograph, public domain), Wikimedia Commons, file Conus_textile_a1.jpg. Link to Conus textile (photograph, public domain)