A common feature appears to be the presence of some kind of partitioning: the systems effectively break up into parts that evolve at least somewhat independently for long periods of time.

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.

{Take[#, k], Drop[ #, k](-1)^(Range[0, k - 1]/k)}] &, Partition[##]]] &, BitReverseOrder[data], 2^Range[Log[2, n]]]/ √ n ] (See also page 1080 .)

To see the consequences of such constraints consider breaking a sequence of colors into blocks of length n , with each block overlapping by n - 1 cells with its predecessor, as in Partition[list, n, 1] .

The method can be implemented using Module[{a = Flatten[data], r, s}, {r, s} = Dimensions[data]; Partition[Do[ a 〚 i + {1, s - 1, s, s + 1} 〛 += m (a 〚 i 〛 - If[a 〚 i 〛 < 1/2, 0, 1]), {i, r s - s - 1}]; Map[If[# < 1/2, 0, 1] &, a], s]] In its original version m = {7, 3, 5, 1}/16 , as in the first row of pictures below.

(Some physicists might argue for a somewhat narrower definition that allows only discontinuities in the so-called partition function of equilibrium statistical mechanics, but for many of the most interesting applications, the definition I use is the appropriate one.)

The Thue–Morse sequence discussed on page 890 can be obtained from it by applying 1 - Mod[Flatten[Partition[FoldList[Plus, 0, list], 1, 2]], 2] (b) The n th element is simply Mod[n, 2] .

Given the list of successive configurations of the register machine, the steps that correspond to successive steps of Turing machine evolution can be obtained from (Flatten[Partition[Complement[#, #-1], 1, 2]]&)[ Position[list, {_,{_,_,0}}]] The program given above works for Turing machines with any number of states, but it requires some simple extensions to handle more than two possible colors for each cell.

Fractal dimensions [of additive cellular automata] The total number of nonzero cells in the first t rows of the pattern generated by the evolution of an additive cellular automaton with k colors and weights w (see page 952 ) from a single initial 1 can be found using g[w_, k_, t_] := Apply[Plus, Sign[NestList[Mod[ ListCorrelate[w, #, {-1, 1}, 0], k] &, {1}, t - 1]], {0, 1}] The fractal dimension of this pattern is then given by the large m limit of Log[k,g[w, k,k m + 1 ]/g[w, k, k m ]] When k is prime it turns out that this can be computed as d[w_, k_:2] := Log[k,Max[Abs[Eigenvalues[With[ {s = Length[w] - 1}, Map[Function[u, Map[Count[u, #] &, #1]], Map[Flatten[Map[Partition[Take[#, k + s - 1], s, 1] &, NestList[Mod[ListConvolve[w, #], k] &, #, k - 1]], 1] &, Map[Flatten[Map[{Table[0, {k - 1}], #} &, Append[#, 0]]] &, #]]] &[Array[IntegerDigits[#, k, s] &, k s - 1]]]]]]] For rule 90 one gets d[{1, 0, 1}] = Log[2, 3] ≃ 1.58 .

One can count the number of occurrences of each of the k b possible blocks of length b in a given state using BC[list_] := With[{z = Map[FromDigits[#, k] &, Partition[list, b, 1, 1]]}, Map[Count[z, #] &, Range[0, k b - 1]]] Conserved quantities of the kind discussed here are then of the form q .