Numerical regularities in the classification of cellular automata

Question

This is a question about elementary cellular automata (ECA) and their classification into uniform (class I), periodic (class II), chaotic (class III), complex (class IV) due to Wolfram.

Maybe I missed something and this is folklore, but is there a good explanation

• why three out of eight class I rules (upto equivalence) are powers of $2$?
  $8\equiv 64, 32, 128$

• why the other powers are class II?
  $1, 2 \equiv \textbf{16}, 4$

• why six out of eleven class III rules are multiples of $15 = \textbf{16} - 1$?
  $30\equiv 135,45\equiv 75,60\equiv 195,90\equiv 165,105,150$

• why rules $15\equiv 240$ and $180\equiv 210$ are exceptional and in class II?

• why rule $120\equiv 225$ is exceptional and in class IV?

It comes as no surprise that rule $0\equiv 255$ is class I.

Maybe it's possible to see "patterns" here:

The scheme on top indicates the position of the $i$-th bit in the binary representation of the rule numbers.

Choosing another, more natural representation gives different rule patterns:

With equivalence class representatives only:

Note that all multiples of $15$ (except for $0\equiv 255$) have two bits in the upper row (the subrules for black pixels) and two bits in the lower row (the subrules for white pixels), i.e. are "doubly balanced" in a sense. In turn, there are only four doubly balanced class II rules ($15, 46, 154\equiv 180, 184$), one doubly balanced class IV rule ($120$), and no doubly balanced class I rule. So being a multiple of $15$, i.e. being doubly balanced, somehow strongly correlates with being class III. While being a power of $2$, i.e. having exactly one bit, strongly correlates – more or less obviously – with being class I.

The question remains open why doubly balanced rules – even the most symmetric one, $90$ – tend to be class III, i.e. to produce chaotic patterns. And why rule $120$ produces complex patterns.

Answer 1

First of all, the general reason why powers of two come up so frequently when looking at the Wolfram numbering of elementary CA rules is because the natural representation of the rules is actually the 8-bit rule string, not the number obtained by interpreting this string as a binary number and converting it to decimal.

From that viewpoint, I think all of your observations can be seen as arising from a single general one: rules that map most local configurations to the same state tend to have simpler dynamics than those whose rule strings are more or less evenly split between zeros and ones, and which are thus roughly equally likely to map a randomly chosen configuration to either state.

Of course, there are plenty of counterexamples to this general rule of thumb, but on average, it's still a pretty decent guideline.

In particular, let $H(n)$ be the Hamming weight of the rule number $n$ written in binary, i.e. the number of bits in the rule string that are ones.

(Note: $H(n)$ is closely related to e.g. the "activity" parameter $\lambda$ as defined by Langton (1990), although Langton's $\lambda$ is only defined for rules with a designated "quiescent state" that is stable in a homogeneous configuration. Indeed, for ECA rules with quiescent state 0, $\lambda(n) = \frac{H(n)}{7}$, where the division by the number of non-quiescent input patterns simply rescales the activity parameter to $0 ≤ \lambda(n) ≤ 1$.)

Considering $H(n)$ for various rules, we observe the following:

• If $n$ is a power of two, then $H(n) = 1$. All such rules have very simple dynamics (Wolfram class I or II), since there's only one local input pattern (out of the eight possible ones) that will produce a state-1 cell in the next generation. (The same is true, of course, also for the equivalent rules with $H(n) = 7$, where there's only one pattern that will yield state 0.)

• For a rule to be in Wolfram class I, all initial configurations containing cells in both states must evolve to a stable homogeneous configuration consisting of one "dominant" state. (Thus, there rules come in equivalent pairs related by state inversion.) For an ECA rule to be Wolfram class I with dominant state 0, it turns out that:

  • the local input pattern 000 must yield state 0, otherwise the all-zero configuration would not be stable;
  • the patterns 001, 010 and 100 must also yield state 0, otherwise isolated state 1 cells would persist forever; and
  • at least one of the patterns 011 and 110 must also yield state 0, otherwise pairs of adjacent state 1 cells would persist forever.

  That means that the only patterns that can yield state 1 for a class I rule with dominant state 0 are 101, 111 and at most one of 011 and 110, and so $H(n) ≤ 3$ for any such rule. In fact, exactly four of these 12 rules have $H(n) = 1$ (and a fifth, rule 0, has $H(n) = 0$).

  (Also taking mirror symmetry into account, it turns out that four of these 12 rules — including rules 0, 32 and 128 — are amphichiral, i.e. invariant under mirroring, while the rest come in four mirror pairs, one of those pairs being rules 8 and 64.)

• Rules whose Wolfram number is of the form $15k$ for $1 ≤ k ≤ 16$, on the other hand, have $H(n) = 4$, i.e. exactly half the bits of their rule string are 1 and half are 0:

  dec	bin	dec	bin	dec	bin	dec	bin
  15	0000 1111	30	0001 1110	45	0010 1101	60	0011 1100
  75	0100 1011	90	0101 1010	105	0110 1001	120	0111 1000
  135	1000 0111	150	1001 0110	165	1010 0101	180	10110100
  195	1100 0011	210	1101 0010	225	11100 001	240	11110000

  In fact, these are exactly the 16 ECA rules that are linear in their leftmost input, such that inverting this input cell always inverts the output cell. This is reflected in their (binary) Wolfram rule code by the high four bits (which encode the outputs when the leftmost input is 1) being the ones' complement of the low four bits (which encode the outputs when the leftmost input is 0). (The fact that all multiples of 15 up to 240 have this property in binary is a somewhat remarkable consequence of how binary multiplication works.)

  Of course, not all of these rules actually give rise to complex dynamics. For example, rule 240 (binary 11110000) is a simple shift map where the output state is equal to that of the leftmost cell of the input pattern, and none of the other input cells matter at all! Rule 15 (binary 00001111) is the same, except that the output is inverted. Wolfram, reasonably enough, classifies both of these rules in class II.

  Rules 180 and 210, meanwhile, are a bit more complex, and arguably close to the boundary between classes II and III. Let's look at the rule table for rule 210 (and the closely related rule 90, which Wolfram puts in class III) more closely:

  input:	111	110	101	100	011	010	001	000
  rule 90	0	1	0	1	1	0	1	0
  rule 210	1	1	0	1	0	0	1	0

  We can see that when the middle input cell is 0, then the output of both rules is equal to the binary XOR of the other two inputs. However, whereas this is always the case for rule 90, regardless of the value of the middle cell, for rule 210 the output when the middle cell is 1 is equal to the left input cell.

  Indeed, if started from a single state 1 cell on a state 0 background (or, more generally, from a configuration where all even-numbered or all odd-numbered cells are in state 0), rule 210 behaves exactly like rule 90 and produces the same distinctive linear superposition of discrete Sierpinski triangles. In particular, under both rules, such a starting configuration guarantees there there will never be two adjacent state 1 cells, and thus the differences between the rule tables will never come into play. (The same is true for rules 18, 26, 82, 90, 146, 154, 210 and 218, i.e. all rules with Wolfram codes of the form $2 + 8a + 16 + 64b + 128c$ for $a,b,c \in \{0,1\}$.)

  What puts rule 210 in class II (at least according to Wolfram, presumably) however is the fact that, when two Sierpinski patterns offset by an odd number of cells collide, they do not pass through each other without interference (as they would under rule 90), but rather the left pattern overrides the right one.

  In particular, this means that, when started from a random initial configuration (which tend to contain a large number of state 1 cells an odd number of steps apart), rule 210 tends to produce diagonal stripes with fairly low-period partial Sierpinski patterns within them, whereas rule 90 displays apparently chaotic (although actually linear and thus quite easily predictable) dynamics consisting of freely growing and overlapping Sierpinski triangles.

  
  ^{Figure 1: Evolution of Wolfram elementary cellular automaton rules 90 (top) and 210 (bottom) from a random initial configuration (left) and from two state-1 cells placed an odd number of positions apart (right)}

  
  ^{Figure 2: Evolution of Wolfram elementary cellular automaton rule 210 / rule 90 from an initial configuration where all even-numbered cells have state 0 and odd-numbered cells (within a small section of the grid) have random states. Rule 210 behaves identically to rule 90 on such initial conditions, exhibiting apparent chaos that is actually just a linear superposition of shifted Sierpinski triangle patterns.}

  Of course, Wolfram's classification is to some extent subjective and could be argued with. For example, do linear ECA rules like rule 90 really belong in class III, or should they be in class II, or should they perhaps be put in a separate class entirely? Certainly they're not "chaotic" in the same sense as, say, rule 30, even if they may look that way when started from a random initial condition. And does the fact that rule 210 may exhibit exactly the same kind of dynamics as rule 90, but only when the initial configuration satisfies a special condition (one of the two checkerboard sublattices is empty), mean that it too should be in class III? Maybe. Or maybe not.