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^{nkn} 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.