But if there are beacons that are intended to be noticed even if one does not already know that they are there, then the signals these produce must necessarily have recognizable distinguishing features, and thus regularities that can be detected, at least by their potential users. … For as we saw in Chapter 10 most of the methods of perception and analysis that we currently use can in general do little more than recognize repetition—and sometimes nesting.

Decrement-jump instructions, on the other hand, do two things. … And decrement-jump instructions are then set up so that if they are applied to a register containing zero, they just do essentially nothing: they leave the register unchanged, and then they go on to execute the next instruction in the program, without jumping anywhere.

Rule 218 [with simple initial conditions] If pairs of adjacent black cells appear anywhere in its initial conditions this class 2 rule gives uniform black, but if none do it gives a rule 90 nested pattern.

[Causal networks for] 2D mobile automata As in 2D random walks, active cells in 2D mobile automata often do not return to positions they have visited before, with the result that no causal connections end up being created.

(h) does not appear to evolve to strict repetition or nesting, but does show progressively longer patches with fairly orderly behavior.

NetCAStep above in general produces a non-deterministic finite automaton (NDFA) for which a particular sequence of values does not determine a unique path through the network. … The Myhill–Nerode theorem ensures that a unique minimal DFA can always be found (though to do so is in general a PSPACE-complete problem).

However, the ordering defined by GrayCode from page 901 does do this for one particular sequence of single square changes.

For infinite groups, it is known (see page 938 ) that in most cases Cayley graphs are locally like trees, and so do not have finite dimension. It appears that only when the group is nilpotent (so that certain combinations of elements commute much as they do on a lattice) is there polynomial growth in the Cayley graph and thus finite dimension.

It seems likely that randomness in the wind has little to do with the behavior of the ocean surface; instead it is the intrinsic dynamics of the water that is most important.

It is difficult to know, however, what an idealized self-gravitating system would do. … (And it is presumably not feasible to do a small-scale experiment, say in Earth orbit.) … And in doing this I quickly came up with cellular automata.