Emergence in the Game of Life

Conway's Game of Life is the best-known picture of emergence: simple rules on a grid of cells give patterns that behave like objects. Read with the words of lesson 1.2, the whole game is one system of rules. Classical: Conway's game, published by Gardner in 1970.

• Cells are distinctions. Each cell at each step of time is a variable: 1 when the cell is alive, 0 when it is dead.
• The rule is a rule on ten variables. A cell is alive at the next step exactly when three of its eight neighbours are alive now, or when it is alive now and two of them are. That links the cell's next value to the present values of the cell and its eight neighbours. It allows 512 of the 1,024 states of those ten variables, and like every rule it can be written as a CNF.
• A history is an allowed state. Stack the steps in layers, with one variable for each cell in each layer. Together, the rules of every cell allow exactly the possible histories: the first layer can be anything, and every later layer is forced.
• The famous patterns are solutions. A still life, such as the block, is a state that the rules carry to itself, so it is an allowed state of the rules with the next layer equal to the present one. An oscillator, such as the blinker, comes back to itself after a fixed number of steps (two for the blinker), and a spaceship, such as the glider, comes back moved (one cell diagonally every four steps). Each is an allowed state of the same rules with time closed into a cycle, shifted in the case of a spaceship.
• Every rule is local, and what the rules allow is global. A rule reads only one cell and its neighbours, but neighbouring rules share variables, so a pattern can be forced or ruled out by rules far away, through the rules in between.
• Contradictions are objects too. A lone live cell and an empty board both become an empty board, so two different patterns have the same successor. By the Garden of Eden theorem (Moore 1962; Myhill 1963), some patterns therefore have no predecessor at all, and asking for one gives a system of rules that allows nothing. Chapter 5 shows that such a system still has structure: how much of it a proof must hold at once to see that nothing is allowed.

The grid is drawn in advance. Each rule of Life mentions one cell and its eight neighbours, and the grid is what decides which cells those are. Logic needs no grid. A rule may mention any set of variables, and a variable may appear in rules with any others; lesson 3.4 shows that every shape, of any dimension, is the shape of some system of rules. So Life shows patterns emerging on a space that someone drew. The program asks for more: rules that make their own neighbourhoods, so that the space emerges too (lesson 7.2, question 1).

Reading. Life is a picture of emergence, not the program's first instance of it. Its rule cannot be split into two-place rules, even with witnesses (lesson 3.1 gives the test), and it is not a knot either (lesson 2.1); its patterns also rest on the drawn grid. The lessons that follow look for the first thing that a whole allows and no part shows: a binding between two loops, which lesson 2.1 calls a knot. The game's name is only a name, and nothing here is a claim about biology.