But at intermediate times one will see all sorts of potentially dramatic gullies that reflect the pattern of drainage, and the formation of a whole tree of streams and rivers. … If one imagines a uniform slope with discrete streams of water going randomly in each direction at the top, and then merging whenever they meet, one immediately gets a simple tree structure a little like in the pictures at the top of page 359 .

consists of all configurations in which black cells occur only when they are surrounded on each side by at least one white cell. … For one-dimensional cellular automata, it turns out that there is a rather compact way to summarize all the possible sequences of black and white cells that can occur at any given step in their evolution. … In the pictures at the top of the facing page , the first network in each case represents random initial conditions in which any possible sequence of black and white cells can occur.

And so for example, in the case of cellular automata, it seems that all the essential ingredients needed to produce even the most complex behavior already exist in elementary rules. … There are some patterns that attain a definite size, then repeat forever, as shown below, others that continue to grow, but have a repetitive form, as at the top of the facing page , and still others that produce nested or fractal patterns, as at the bottom of the page .

But almost all the evidence we have Example of a simple problem that I suspect is NP-complete. … The pictures at the top show that in case (a) stripes up to height 3 can be produced, in case (b) up to height 2, and in case (c) only up to height 1.

that they ultimately tend to be equivalent in their computational sophistication—and thus show all sorts of similar phenomena. … At the top right are axioms specifying certain fundamental equivalences between logic expressions.

The procedure at the top of the facing page already in a sense involved randomness, for it picked a square at random at each step. … Results from a slight modification to the procedure used in the picture at the top of the facing page .

The pictures on the right show which cells in the top row and which cells in the right-hand column determine the cells at successive positions in the right-hand column and in the top row respectively.

Of combinator expressions up to size 6 all evolve to fixed points, in at most {1, 1, 2, 3, 4, 7} steps respectively (compare case (a)); the largest fixed points have sizes {1, 2, 3, 4, 6, 10} (compare case (b)). At size 7, all but 2 of the 16,896 possible combinator expressions evolve to fixed points, in at most 12 steps (case (c)). … The maximum number of levels in these expressions (see page 897 ) grows roughly linearly, although Depth[expr] reaches 14 after 26 and 25 steps, then stays there.

The two cellular automata below both have all white and all black as invariant states. And in the first case, starting from random initial conditions, the system quickly settles down to the all black invariant state. … Instead, as the pictures at the top of the facing page show, one sees a variety of patterns that very Two of the 28 elementary cellular automata whose only invariant states are uniform in color.

For all one need do, as in the pictures at the top of the next page , is to evaluate the expressions for all possible values of each variable, and then to see whether the patterns of results one gets are the same. And in this way one can readily tell, for example, that the first operator shown is idempotent, so that p ∘ p  p , while both the first two operators are associative, so that (p ∘ q) ∘ r  p ∘ (q ∘ r) , and all but the third operator are commutative, so that p ∘ q  q ∘ p . … But even for operators given by finite tables it is often difficult to find axiom systems that can successfully reproduce all the results for a particular operator.