But it turns out that the additive nature of the underlying rule still makes comparatively straightforward cryptanalysis possible. … The first set of pictures show the ordinary evolution of the rule 60 cellular automaton, in which each successive row is deduced from the one above. The second set of pictures show a kind of sideways evolution in which the rule is reinterpreted so as to allow a column of cells to be deduced from the column immediately to its right.

For without every cell there does not appear to be enough information for any kind of local rule to be able to deduce one column from others. … It turns out that the approach relies crucially on the additivity of the underlying rules. And since rule 30 is not additive, it simply does not work.

The Threshold of Universality in Cellular Automata By showing that rule 110 is universal, we have established that universality is possible even among cellular automata with the very simplest kinds of underlying rules. … What about additive rules such as 90 and 150? With simple initial conditions these rules always yield very regular nested patterns.

Rules (a) and (b) yield very simple repetitive networks in which there is in effect a notion of time but not of space. … But with rules (a) and (b) only a limited number of points in space can ever be reached. … Rules (c) and (d) yield networks that can be laid out in a quite

Numbers of possible [2D cellular automaton] rules The table below gives the total number of 2D rules of various types with two possible colors for each cell. Given an initial pattern with a certain symmetry, a rule will maintain that symmetry if the rule is such that every neighborhood equivalent under the symmetry yields the same color of cell. … Totalistic rules depend only on the total number of black cells in a neighborhood; outer totalistic rules (as in the previous note) also depend on the color of the center cell.

The rule for this cellular automaton considers the 8 neighbors of a cell (including diagonals): if two of these neighbors are black, then the cell stays the same color as before; if three are black, then the cell becomes black; and if any other number of neighbors are black, then the cell becomes white. This rule is outer totalistic 9-neighbor code 224.

Rule equivalences [for cellular automata] The table below gives basic equivalences between elementary cellular automaton rules. In each block the second entry is the rule obtained by interchanging black and white, the third entry is the rule obtained by interchanging left and right, and the fourth entry the rule obtained by applying both operations. (The smallest rule number is given in boldface.)

Numbers of reversible [cellular automaton] rules For k = 2 , r = 1 , there are 6 reversible rules, as shown on page 436 . For k = 2 , r = 2 there are 62 reversible rules, in 20 families inequivalent under symmetries, out of a total of 2 32 or about 4 billion possible rules. For k = 3 , r = 1 there are 1800 reversible rules, in 172 families.

Implementation [of cyclic tag systems] With the rules for the cyclic tag system on page 95 given as {{1, 1}, {1, 0}} , the evolution can be obtained from CTEvolveList[rules_, init_, t_] := Map[Last, NestList[CTStep, {rules, init}, t]] CTStep[{{r_, s___}, {0, a___}}] := {{s, r}, {a}} CTStep[{{r_, s___}, {1, a___}}] := {{s, r}, Join[{a}, r]} CTStep[{u_, {}}] := {u, {}} The leading elements on many more than t successive steps can be obtained directly from CTList[rules_, init_, t_] := Flatten[Map[Last, NestList[CTListStep, {rules, init}, t]]] CTListStep[{rules_, list_}] := {RotateLeft[rules, Length[list]],Flatten[rules 〚 Mod[Flatten[Position[list, 1]], Length[rules], 1] 〛 ]}

Substitution systems in which all replacements are done that are found to fit in a left-to-right scan can be implemented as follows GSSEvolveList[rule_, s_, n_] := NestList[GSSStep[rule, #] &, s, n] GSSStep[rule_, s_] := g[rule, s, f[StringPosition[s, Map[First, rule]]]] f[{ }] = { }; f[s_] := Fold[If[Last[Last[#1]] ≥ First[#2], #1, Append[#1, #2]]&, {First[s]}, Rest[s]] g[rule_, s_, { }] := s; g[rule_, s_, pos_] := StringReplacePart[ s, Map[StringTake[s, #] &, pos] /. rule, pos] with rules given as {"ABA"  "BAAB", "BBBB"  "AA"} .