But in fact, having just specified a block of length x + 2 r t in the initial conditions, the cellular automaton rule then uniquely determines the color of every cell in the patch, allowing a total of at most s[t, x] = k x + 2 r t configurations. … For additive rules like rule 90 and rule 150 every possible configuration of the initial block leads to a different configuration for the patch, so that h tx = 2r = 2 . But for other rules many different configurations of the initial block can lead to the same configuration for the patch, yielding potentially much smaller values of h tx .

Blocks in such sequences obtained from Partition[list, n, 1] must all be distinct since they correspond to successive complete states of the shift register. This means that every block with length up to n (except all 0's) must occur with equal frequency.

one-dimensional blocks.

Summaries of how various underlying cellular automata do in emulating a single step in the evolution of each of the 256 possible elementary cellular automata using the scheme from the facing page with blocks of successively greater widths.

The successive blocks of results in each case show forms of the operator allowed with 2, 3 and 4 possible elements.

This suggests that to determine whether a repetitive pattern with repeating blocks of size n exists may in general take a number of steps which grows more rapidly than any polynomial in n .

The solution to this equation with an impulse initial condition is Exp[-x 2 /t] , and with a block from -a to a it is (Erf[(a - x)/ √ t ] + Erf[(a + x)/ √ t ])/a .

Background [in rule 110] At every step the background pattern in rule 110 consists of repetitions of the block b = {1,0,0,1,1,0,1,1,1,1,1,0,0,0} , as shown in the picture below.

I suspect that universal examples with blocks of the same size exist with just 3 colors.

But searching all 4 billion or so possible such systems with 2 × 2 blocks and up to four colors one finds not a single case in which a nested pattern is forced to occur. … One starts from the substitution system with rules {1  {{3}}, 2  {{13, 1}, {4, 10}}, 3  {{15, 1}, {4, 12}}, 4  {{14, 1}, {2, 9}}, 5  {{13, 1}, {4, 12}}, 6  {{13, 1}, {8, 9}}, 7  {{15, 1}, {4, 10}}, 8  {{14, 1}, {6, 10}}, 9  {{14}, {2}}, 10  {{16}, {7}}, 11  {{13}, {8}}, 12  {{16}, {3}}, 13  {{5, 11}}, 14  {{2, 9}}, 15  {{3, 11}}, 16  {{6, 10}}} This yields the nested pattern below which contains only 51 of the 65,536 possible 2 × 2 blocks of cells with 16 colors. It then turns out that with the constraint that the only 2 × 2 arrangements of colors that can occur are ones that match these 51 blocks, one is forced to get the nested pattern below.