Block cellular automata

With a rule of the form {{1,1}->{1,1}, {1,0}->{1,0}, {0,1}->{0,0}, {0,0}->{0,1}} the evolution of a block cellular automaton with blocks of size n can be implemented using

BCAEvolveList[{n_Integer, rule_}, init_, t_] := FoldList[BCAStep[{n, rule}, #1, #2]&, init, Range[t]] /; Mod[Length[init], n] == 0 BCAStep[{n_, rule_}, a_, d_] := RotateRight[Flatten[Partition[RotateLeft[a, d], n]/.rule], d]

Starting with a single black cell, none of the k=2, n=2 block cellular automata generate anything beyond simple nested patterns. In general, there are (k^^{n})^(k^^{n}) possible rules for block cellular automata with k colors and blocks of size n. Of these, (k^^{n})! are reversible. For k=2, the number of rules that conserve the total number of black cells can be computed from q = Binomial[n, Range[0, n]] as Apply[Times, q^^{q}]. The number of these rules that are also reversible is Apply[Times, q!]. In general, a block cellular automaton is reversible only if its rule simply permutes the k^^{n} possible blocks.

Compressing each block into a single cell, and n steps into one, any block cellular automaton with k colors and block size n can be translated directly into an ordinary cellular automaton with k^^{n} colors and range r=n/2.