BLOCK TRANSFORMATIONS OF ONE-DIMENSIONAL DETERMINISTIC CELLULAR AUTOMATON RULES

Given a one-dimensional cellular automaton rule f, a block transform of f is a rule T(b)f such that there exists between the limit sets of both rules a bijection that replaces each site value x in a configuration belonging to the limit set of f with a string x(b) = xx ... x of length b in the corresponding configuration belonging to the limit set of T(b)f. If f is totalistic, there exists a unique totalistic block transform and a large number of non-totalistic block transforms T(b)f. If f is not totalistic, there are no totalistic block transforms but there still exists a large number of non-totalistic block transforms. Their number increases very rapidly with the block size b and the range r of f. The range of T(b)f may be any integer greater than or equal to rb. Many block transforms are studied. The evolution according to rule T(b)f towards its limit set is discussed in terms of the annihilation of defects. These defects are often simply related to the defects characterizing the evolution according to rule f.