any number of white cells. At any point one can follow the arrow to the left to get a black cell, but the form of the network implies that this black cell must always be followed by at least one white cell.

The pictures on the next page show more examples of class 1 and 2 cellular automata. Unlike in the picture below, these rules do not reach their final states after one step, but instead just progressively evolve towards these states. And in the course of this evolution, the set of sequences that can occur becomes progressively smaller.

In rule 128, for example, the fact that regions of black shrink by one cell on each side at each step means that any region of black that exists after t steps must have at least t white cells on either side of it.

The networks shown on the next page capture all effects like this. And to do this we see that on successive steps they become somewhat more complicated. But at least for these class 1 and 2 examples, the progression of networks always continues to have a fairly simple form.

Networks representing possible sequences of black and white cells that can occur at successive steps in the evolution of the two cellular automata shown above. In each case the possible sequences correspond to possible paths through the network. Both rules start on step 1 from random initial conditions in which all sequences of black and white cells are allowed. On subsequent steps, rule 255 allows only sequences containing just black cells, while rule 4 allows sequences that contain both black and white cells, but requires that every black cell be surrounded by white cells.

From Stephen Wolfram: A New Kind of Science [citation]