The only smaller cluster with the same property is the trivial one with just a single node. … (One can see this by noting that they can overlap inside clusters with dangling connections, not just closed networks.)

Ultimately what one wants to do is to find what possible types of forms for local regions are inequivalent under the application of the underlying rules. But in general it may be undecidable even whether two such forms are actually equivalent (compare the notes below and on page 1051 )—since to tell this one might need to be able to apply the rules infinitely many times.

But to apply such an argument one must among other things assume that we can imagine all the ways in which intelligence could conceivably operate. … And indeed, as we discuss in Chapter 12 , it seems likely that above a fairly low threshold the vast majority of underlying rules can in fact in some way or another support arbitrarily complex computations—potentially allowing something one might call intelligence in a vast range of very different universes.

But if one allows three possible colors, and requires, say, that the total number of black and gray cells together be conserved, then more complicated behavior can occur, as in the pictures below.

The first one on the bottom (with 63 comparisons) has a nested structure and uses the method invented by Kenneth Batcher in 1964: Flatten[Reverse[Flatten[With[{m = Ceiling[Log[2, n]] - 1}, Table[With[{d = If[i  m, 2 t , 2 i + 1 - 2 t ]}, Map[ {0, d} + # &, Select[Range[n - d], BitAnd[# - 1, 2 t ]  If[i  m, 0, 2 t ] &]]], {t, 0, m}, {i, t, m}]], 1]], 1] The second one on the bottom also uses 63 comparisons, while the last one is the smallest known for n = 16 : it uses 60 comparisons and was invented by Milton Green in 1969. … (In general all lists will be sorted correctly if lists of just 0's and 1's are sorted correctly; allowing even just one of these 2 n cases to be wrong greatly reduces the number of comparisons needed.)

One point to notice is that the sharp change which characterizes any phase transition can only be a true discontinuity in the limit of an infinitely large system. … The discrete nature of phase transitions was at one time often explained as a consequence of changes in the symmetry of a system. … But below the transition, it effectively makes a choice of one spin direction or the other.

(One can have lists instead of strings, replacing StringJoin by Flatten .) … To know that no solution is possible of any length, one must in effect have a proof. … As one example of how one proves that a PCP constraint cannot be satisfied, consider case (s).

1D phenomena Among the phenomena that cannot occur in one dimension are those associated with shape, winding and knotting, as well as traditional phase transitions with reversible evolution rules (see page 981 ).

[Iterated maps from] bitwise operations Cellular automata can be thought of as analogs of iterated maps in which bitwise operations such as BitXor are used instead of ordinary arithmetic ones.

Looking carefully at the pictures of multiway system evolution on previous pages [ 204 , 205 , 206 , 207 ], a feature one notices is that the same sequences often occur on several different steps.