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}}

{{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

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]

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

k = 2, n = 2

✖

n = 2 block cellular automata generate anything beyond simple nested patterns. In general, there are k^nkn

✖

\!\(\*SuperscriptBox[\(k\),\(\!\(\*SuperscriptBox[\(nk\),\(n\)]\)\)]\) possible rules for block cellular automata with k colors and blocks of size n. Of these, kⁿ!

✖

\!\(\*SuperscriptBox[\(k\),\(n\)]\)! are reversible. For k = 2

✖

k = 2, the number of rules that conserve the total number of black cells can be computed from q = Binomial[n, Range[0, n]]

✖

q = Binomial[n, Range[0, n]] as Apply[Times, q^q]

✖

Apply[Times,\!\(\*SuperscriptBox[\(q\),\(q\)]\)]. The number of these rules that are also reversible is Apply[Times, q!]

✖

Apply[Times, q!]. In general, a block cellular automaton is reversible only if its rule simply permutes the kⁿ

✖

\!\(\*SuperscriptBox[\(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ⁿ

\!\(\*SuperscriptBox[\(k\),\(n\)]\) colors and range r = n/2

✖

r = n/2.