[Examples of] reducible systems The color of a cell at step t and position x can be found by starting with initial condition Flatten[With[{w = Max[Ceiling[Log[2, {t, x}]]]}, {2 Reverse[IntegerDigits[t, 2, w]] + 1, 5, 2 IntegerDigits[x, 2, w] + 2}]] then for rule 188 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {3, 5 | 10, 2}  6, {1, 5 | 7, 4}  0, {3, 5, 4}  7, {1, 6, 2}  10, {1, 6 | 11, 4}  8, {3, 6 | 8 | 10 | 11, 4}  9, {3, 7 | 9, 2}  11, {1, 8 | 11, 2}  9, {3, 11, 2}  8, {1, 9 | 10, 4}  11, {_, a_ /; a > 4, _}  a, {_, _, _}  0} and for rule 60 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {1, 5, 4}  0, {_, 5, _}  5, {_, _, _}  0}

Standard operations in logic can be generalized as Not[a_] = 1 - a , And[a_, b_] = Min[a, b] , Or[a_, b_] = Max[a, b] , Xor[a_, b_] = Abs[a - b] , Equal[a_, b_] = 1 - Abs[a - b] , Implies[a_, b_] = 1 - UnitStep[a - b](a - b) .

Mod[Binomial[t, n], k] is given for prime k by With[{d = Ceiling[Log[k, Max[t, n] + 1]]}, Mod[Apply[Times, Apply[Binomial, Transpose[ {IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k]] The patterns obtained for any k are nested.

In this pattern, the color of a particular cell can be obtained directly from the digit sequences for t and n by 1 - Sign[BitAnd[-t, n]] or (see page 583 ) With[{d = Ceiling[Log[2, Max[t, n] + 1]]}, If[FreeQ[ IntegerDigits[t, 2, d] - IntegerDigits[n, 2, d], -1], 1, 0]]

(The presence of nested structure is particularly evident in FoldList[Plus, 0, Table[Mod[h n, 1] - 1/2, {n, max}]] .)

With rules in this form the network update is simply NetStep[rule_, net_]:= Block[{new}, net /. rule /. new[n_]  n + Apply[Max, Map[First, net]]] Note that just as we discussed for strings on page 1033 the direct use of /. here corresponds to a particular scheme for applying the update rule.

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 .

An original more specialized version of this was posed by Max Dehn in 1911 for groups and by Axel Thue in 1914 for semigroups.

This same basic scheme can be used with any associative function h — Max , GCD , And , Dot , Join or whatever—so long as suitable forms for r and s are used.

An example as shown below is rule 250 with u ⊕ v taken as Max[u, v] ( Or ).