Self-similarity [of rule 90] The pattern generated by rule 90 after a given number of steps has the property that it is identical to what one would get by going twice as many steps, and then keeping only every other row and column. After 2 m steps the triangular region outlined by the pattern contains altogether 4 m cells, but only 3 m of these are black. In the limit of an infinite number of steps one gets a fractal known as a Sierpiński pattern (see page 934 ), with fractal dimension Log[2, 3] ≃ 1.59 (see page 933 ).

[Repetition in] 2D cellular automata As expected from the discussion of constraints on page 942 , the problem of finding repeating configurations is much more difficult in two dimensions than in one dimension. … Indeed, as discussed on page 1139 , it is in a sense possible that the only repeating configurations are arbitrarily complex. Note that if one considers configurations in 2D that consist only of infinitely long stripes, then the problem reduces again to the 1D case.

Relation to 2D cellular automata The kind of constraints discussed are exactly those that must be satisfied by configurations that remain unchanged in the evolution of a 2D cellular automaton. … The point is that of the 32 5-cell neighborhoods involved in the 2D cellular automaton rule, only some subset will have the property that the center cell remains unchanged after applying the rule. And any configuration which does not change must involve only these subsets.

In class 4, changes can also spread, but only in a sporadic way—as illustrated on the facing page and the one that follows. … In class 2, some information about initial conditions is retained in the final configuration of structures, but this information always remains completely localized, and is never in any way communicated from one part of the system to another. … Class 4 systems are once again somewhat intermediate between class 2 and class 3.

And during the time that a boat is caught up in a particular one of these waves, its motion will always be quite regular; it is only when one watches the effect of a sequence of waves that one sees behavior that appears in any way random. … And indeed, it is only at a fairly superficial level of description that it is useful to say that the randomness in the motion of the boat comes from interaction with an environment about which one will say nothing more than that it is random.

And as an example the pictures below show what happens if at each step one reverses the color of a random square not only if this will decrease the total number of squares violating the constraints, but also if it leaves this number the same. … But now the color of that square is reversed not only if doing so actually changes the total number of squares that violate the constraint, but also if it leaves this number the same.

But in fact, as it turns out, a rather large fraction of the most obvious examples of biological complexity seem to involve only surprisingly limited parts of the organisms. Elaborate pigmentation patterns, for instance, typically exist just on an outer skin, and are made up of only a few types of cells.

tell, the only kinds of correlations that are ultimately important to our auditory system are those that lead to some form of repetition. … Most kinds of statistical analysis are fundamentally based on the assumption that such models must be probabilistic, in the sense that they give only probabilities for behavior, and do not specifically say what the behavior will be. … By effectively enumerating all such sequences, it is easy to see that such a model predicts that in any particular sequence the fraction of black squares is most likely to be 1/2 .

The rule applies only to this active cell. … But unlike a cellular automaton, a mobile automaton has only one "active cell" (indicated here by a black dot) at any particular step.

Equivalence is concerned not only with the computational sophistication of complete systems but also with the computational sophistication of specific processes that occur within systems. … But from this there is no guarantee that the vast majority of initial conditions—including perhaps all those that could readily arise in nature—will not just yield behavior that corresponds only to very simple computations.