Rule 30: one black cell

Rule 30 has a useful property: if you know the centre column and the column beside it, every square to the left is forced, one after another. So a repeating centre forces the whole left side. The prize asks about one black square; we ask the same of every finite start, a pattern with only finitely many black squares, which includes it. For any of those the forced left side would have to turn white for good beyond some depth. A counterexample to Problem 1 is exactly that: a white edge that never breaks.

The same property works the other way round. Choose anything for the centre to say, the primes, the Fibonacci numbers, the digits of π in binary, your own name, and build the start one square at a time, leftwards: the square t places left of the centre decides the centre at step t outright, without disturbing the steps before. So every sequence can be made. The catch is that the start never ends; each step needs one more square. Cut it to a finite start and the sequence breaks, just as the first square it lacks reaches the centre. Even the best of every start of 18 squares follows the primes for only 18 steps, and π for 19. A finite start buys about one step per square, whatever it is asked to say, unless the sequence is one Rule 30 makes by itself. Problem 1 asks whether any repeating pattern is one of those.

A start word can also be animated. Flip one of its bits and the picture below changes, but only inside a cone that opens from the flipped square, and the change arrives one step at a time, so it sweeps down the page. Its right edge is a straight line, exactly one square per step, for the same reason the start could be built square by square. Its left edge moves only when the colours let it through: about a quarter of a square per step across the random-looking inside, a full square once it reaches the white outside. A flip left of the centre reaches the centre column after exactly as many steps as it is squares away. Flip the bits in Gray-code order and the frames walk through every possible start, each one flip from the last.

Try it. Below, the centre is held to its beat (teal) and the column beside it (amber) is given a repeating pattern; pick one from the menu or ask for a random one. Rule 30 then fixes the columns to the left one at a time, so the picture grows leftwards from the centre. Whatever the pattern, after a short stretch (the dashed line) the left side freezes into a crystal: a wall built from one brick, repeating across as well as down. The brick is never blank, so the left side can never turn white. That is Jen's theorem of 1990. Across every pattern of even length up to 20, 1,398,100 of them, only 20 different bricks ever appear.

So a counterexample's second column can never repeat, and its left side has no crystal to settle into. The picture below shows how that left side is built. It is turned on its side: time runs left to right, the top row is the centre's beat, the next is the column beside it, driven by a random right side, and each row below is the next column to the left. Built this way, each row records where the row above it changes, plus scattered dots, the edge events, which the pattern makes for itself.

That makes the left side a pile of Sierpinski triangles. Start with one black square, and fill each row below it by a far simpler rule than Rule 30: a square is black when exactly one of the two squares above it, straight up and up-right, is black (this comparison is the Gray code, which chapter 7 comes back to). The single dot grows into a triangle made of three half-size copies of itself, each made of three smaller copies, and so on for ever: the Sierpinski triangle, which is also the pattern of the odd numbers in Pascal's triangle. Give the same rule several dots and each grows its own triangle, but where two triangles overlap they cancel, so a square ends up black exactly when an odd number of triangles cover it.

This is not special to the left side, nor to running sideways. Read the ordinary way, down the page, Rule 30 is the same kind of rule: do what Rule 60 does, black when the square up-left and the square above differ, then flip the square under every kick, a white square with a black one to its right. Rule 60 alone grows one black square into a Sierpinski triangle, and each kick starts another, so every square of the whole pyramid, the striped side and the wild side alike, is an odd overlap of Sierpinski triangles. About a quarter of all squares are kicks on both sides; what differs is only how they are arranged, in regular stripes on the left and scattered on the right. All the triangles lean the same way, down and to the right, because Rule 30 uses its left neighbour exactly and its right neighbour only through the kick, which is also why only the left side can be built sideways.

The demonstration below shows both readings of that one equation. Down the page is the familiar pyramid: point at any square, on either side, to see the triangle of kicks that decides it. Sideways, beside the wall is the left half built outwards from a centre held to the beat, the picture this chapter has been describing. There, click or drag on the green line, time 0, to ask what a counterexample would need: if its white edge started at that depth, everything in the shaded wedge below would have to stay white, one depth deeper at every step. The darker squares are where this random start is black instead. With every row shown, the wedge closes into a whole triangle where the picture itself ends; in a real counterexample it would go on for ever.

We looked at what such an edge would cost. It drags a disturbance along with it, and that disturbance pulls on the squares that must stay white with a beat: odd, odd, even, odd, odd, even, the pattern of the Fibonacci numbers 1, 1, 2, 3, 5, 8, 13. Something inside has to answer that beat for ever. The four short animations below show the beat, the one pattern that could pay it and why Rule 30 forbids it, why the payment always needs older and older events, and how real Rule 30 keeps trying regardless.