Once again, the only difference in initial conditions from the facing page is that each block now encodes rule 30 instead of rule 90.

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}]] . … 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.

Each of the blocks in the universal cellular automaton represents a single cell in rule 254, and encodes both the current color of the cell and the form of the rule used to update it.

Indeed, for period p , the length of blocks required is at most 2 2p (or 2 2 p r for range r rules). … The black dots indicate specific block sizes up to 25 that work. … For periods up to 10, examples of such blocks in rule 90 are given by the digits of {0, 40, 24, 2176, 107904, 640, 96, 8421376, 7566031296234863392, 15561286137} For period 1 the possible blocks are and ; for period 2 and .

But each block in the initial conditions now contains a representation of rule 90 rather than rule 254.

Maximal block compression If one has data that consists of a long sequence of blocks, each of length b , and each independently chosen with probability p[i] to be of type i , then as argued by Claude Shannon in the late 1940s, it turns out that the minimum number of base 2 bits needed on average to represent each block in such a sequence is h = -Sum[p[i] Log[2, p[i]], {i, 2 b }] . If all blocks occur with an equal probability of 2 -b , then h takes on its maximum possible value of b . If only one block occurs with nonzero probability then h  0 .

For rule 184, it can be taken to be 1 for each block, and to be 0 otherwise. … In general, if the global conserved quantity involves blocks of size b , the flux can be computed by looking at blocks of size b + 2r - 1 . What the values for these blocks should be can be found by solving a system of linear equations; that a solution must exist can be seen by looking at the de Bruijn network (see page 941 ), with nodes labelled by size b + 2r - 1 blocks, and connections by value differences between size b blocks at the center of the possible size b + 2r blocks.

In Chapter 3 we discussed both ordinary one-dimensional substitution systems, in which every element is replaced at each step, and sequential substitution systems, in which just a single block of elements are replaced at each step. And what we did to find which block of elements should be replaced at a given step was to scan the whole sequence of elements from left to right.

Block occurrences [in rule 30] The pictures below show at which step each successive block of length up to 8 first appears in evolution according to various cellular automaton rules starting from a single black cell. For rule 30, the numbers of steps needed for each block of lengths 1 through 10 to appear at least once is {1, 2, 4, 12, 22, 24, 33, 59, 69, 113} .

In the typical case illustrated below, one has a sequence of elements—each colored say black or white—and at each step each one of these elements is replaced by a new block of elements. In the simple cases shown, the rules specify that each element of a particular color should be replaced by a fixed block of new elements, independent of the colors of any neighboring elements. … Examples of substitution systems with two possible kinds of elements, in which at every step each kind of element is replaced by a fixed block of new elements.