Pattern (a) can be viewed as formed from a tessellation of 5×10 blocks of cells; pattern (b) from a tessellation of 24×24 blocks.

The problem is that for any block more than one square across changing the color of a square at either end will not reduce the total number of squares that violate the constraint. And as a result, such blocks remain fixed and cannot disappear.

The pictures at the top of the next page show the results of computing the frequencies of different blocks in various sequences, and in each case each successive row shows results for all possible blocks of a given length.

Testing for reversibility [in cellular automata] To show that a cellular automaton is reversible it is sufficient to check that all configurations consisting of repetitions of different blocks have different successors. This can be done for blocks up to length n in a 1D cellular automaton with k colors using ReversibleQ[rule_, k_, n_] := Catch[Do[ If[Length[Union[Table[CAStep[rule, IntegerDigits[i, k, m]], {i, 0, k m - 1}]]] ≠ k m , Throw[False]], {m, n}]; True] For k = 2 , r = 1 it turns out that it suffices to test only up to n = 4 (128 out of the 256 rules fail at n = 1 , 64 at n = 2 , 44 at n = 3 and 14 at n = 4 ); for k = 2 , r = 2 it suffices to test up to n = 15 , and for k = 3 , r = 1 , up to n = 9 . … For 2D cellular automata an analogous procedure can in principle be used, though there is no upper limit on the size of blocks that need to be tested, and in fact the question of whether a particular rule is reversible is directly equivalent to the tiling problem discussed on page 213 (compare page 942 ), and is thus formally undecidable.

The initial condition contains a block of 10 cells.

The pictures in the middle above show that with this rule blocks of opposite color are progressively destroyed, so that whichever color was initially more common eventually dominates completely.

Block cellular automata with three possible colors which conserve the combined number of black and gray cells.

Another initial condition [for rule 90] Inserting a single in a background of blocks in rule 90 yields the pattern below in which both the white and striped regions have fractal dimension 2.

Nesting in rule 45 As illustrated on page 701 , starting from a single black cell on a background of repeated blocks, rule 45 yields a slanted version of the nested rule 90 pattern.

The individual velocity vectors drawn correspond to averages over 20×20 blocks of cells.