Indeed, my expectation is that asking about possible outcomes of t steps of evolution will already be NP-complete even for the rule 30 cellular automaton, as illustrated below. … The problem is to determine whether right-hand cells in the initial conditions for rule 30 can be filled in so as to produce a vertical black stripe of a certain height at the bottom of the center column formed after t steps of evolution. … The problem is related to issues of rule 30 cryptanalysis discussed on page 603 .

Among k = 2 , r = 1 elementary cellular automata it turns out that this happens precisely for those 30 rules that are additive with respect to at least the first or last position on which they depend (see pages 601 and 1087 ); this includes both rules 90 and 150 and rules 30 and 45. With k = 2 , r = 2 there are a total of 4,294,967,296 possible rules. … (Thus for example additive rules such as 90 and 150, as well as one-sided additive rules such as 30 and 45 are always 4-to-1.)

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 nk n possible rules for block cellular automata with k colors and blocks of size n . … The number of these rules that are also reversible is Apply[Times, q!]

[No text on this page] A typical example of the behavior of the rule 110 cellular automaton with random initial conditions.

(The rule has totalistic code 976.) The pictures show that on a large scale, the rule leads to regions of black and white whose boundaries behave in a seemingly smooth and continuous way.

The patterns are arranged on the page so that the pattern shown at a particular position corresponds to what is obtained with a rule in which the tip of the right-hand stem goes to that position (corrected for the aspect ratio of the array) relative to the original stem shown as a vertical line on the left-hand side of the page. … Note that for rules outside of a distorted semicircle centered on the dot at the left-hand side of the page, and touching the three other sides of the page, the patterns generated grow at each step, rather than tending to a limit of fixed size.

Nesting in rule 45 As illustrated on page 701 , starting from a single black cell on a background of repeated blocks, rule 45 yields a slanted version of the nested rule 90 pattern.

Semigroups are obtained by requiring that rules come in pairs: with each rule such as "ABB"  "BA" there must also be the reversed rule "BA"  "ABB" . … Groups require that not only rules but also symbols come in pairs. … The icosahedral group A 5 defined by the rules x 2  y 3  (x y) 5  1 has 60 elements.

General rules [for multidimensional cellular automata] One can specify the neighborhood for any rule in any dimension by giving a list of the offsets for the cells used to update a given cell. For 1D elementary rules the list is {{-1}, {0}, {1}} , while for 2D 5-neighbor rules it is {{-1, 0}, {0, -1}, {0, 0}, {0, 1}, {1, 0}} . … If a cellular automaton rule takes the new color of a cell with neighborhood configuration IntegerDigits[i, k, Length[os]] to be u 〚 i + 1 〛 , then one can define its rule number to be FromDigits[Reverse[u], k] .

(Note that the pattern of differences between two initial conditions in a rule with k possible colors can always be reproduced by looking at the evolution from a single initial condition of a suitable rule with 2k colors.) … For any additive or partially additive class 3 cellular automaton (such as rule 90 or rule 30) any change in initial conditions will always lead to expanding differences. But in other rules it sometimes may not.