Notes

Chapter 5: Two Dimensions and Beyond

Section 7: Systems Based on Constraints


1D [systems based on] constraints

The constraints in the main text can be thought of as specifying that only some of the k^n possible blocks of cells of length n (with k possible colors for each cell) are allowed. To see the consequences of such constraints consider breaking a sequence of colors into blocks of length n, with each block overlapping by n-1 cells with its predecessor, as in Partition[list,n,1]. If all possible sequences of colors were allowed, then there would be k possibilities for what block could follow a given block, given by Map[Rest, Table[Append[list, i], {i, 0, k-1}]]. The possible sequences of length n blocks that can occur are conveniently represented by possible paths by so-called de Bruijn networks, of the kind shown for k=2 and n=2 through 5 below.

Given the network for a particular n, it is straightforward to see what happens when only certain length n blocks are allowed: one just keeps the arcs in the network that correspond to allowed blocks, and drops all other ones. Then if one can still form an infinite path by going along the arcs that remain, this path will correspond to a pattern that satisfies the constraints. Sometimes there will be a unique such path; in other cases there will be choices that can be made along the path. But the crucial point is that since there are only k^n-1 nodes in the network, then if any infinite path is possible, there must be such a path that visits the same node and thus repeats itself after at most k^n-1 cells. The constraint on page 210 has k=2 and n=3; the pattern that satisfies it repeats with period 4, thus saturating the bound. (See also page 266.)


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