HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the number of inequivalent elementary cellular automata rules really 88?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
numbertheinequivalentreallycellularautomataelementaryrules

Problem

Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia article).

Now, the problem is that I am failing to reproduce the 88 number. No matter how I try - I always get 72.

And it gets worse. Sequence A005418 seems to be defined exactly as Wolfram's inequivalence (see the comment: "Number of bit strings of length (n-1), not counting strings which are the end-for-end reversal or the 0-for-1 reversal of each other as different."). And in that sequence at position 8 they also have 72, not 88.

Off course, there is a chance that my program is wrong and/or I do not fully understand the definition of rule equivalence. Therefore I would like to ask someone to reproduce the computations, and either confirm Wolfram's original number 88, or give me the correct number of inequivalent rules (be it 72, or something else).

This problem is important for a research paper I am working on. And it's not very difficult to implement.

Solution

OK! Peter de Rivaz has confirmed the number $88$ by careful analysis of the two equivalence rules, and a clever script.

Here I will try to repeat the analysis (for my own understanding) and then apply some mathematical magic.

A binary cellular automaton is denoted by a bit string $ABCDEFGH$ where the consecutive letters denote each a bit (next state) for the three bits that encode the configuration at position with its two neighbours, $xyz = 111, 110, 101, \dots, 001, 000$.

The mirror operation is the automaton in left-right reverse, meaning that the bit for $xyz$ is now at $zyx$. Thus $A$ at $111$ stays in place, but $B$ at $110$ is swapped with position $E$ at $011$. The new rule is then $AECGBFDH$. There are $64$ rules that stay unchanged under this operation. Says Wikipedia.

The complement operation is the automaton with bits swapped, meaning that the bit for $xyz$ is now the negation of bit $\bar x\bar y\bar z$, which looks rather DeMorgan to me. In words, the bits are reversed and inverted. The new rule is then $\bar H\bar G\bar F\bar E\bar D\bar C\bar B\bar A$. There are $16$ rules that stay unchanged under this operation. Says Wikipedia.

We can also combine the two rules. Mirror complement gives $\bar H\bar D\bar F\bar B\bar G\bar C\bar E\bar A$. Again there are $16$ rules unchanged under this rule. The math is easy, unchanged means $A=\bar H$, $B=\bar D$ etc, finally leaving $4$ free variables.

Applying no operation identity keeps all $256$ bit strings unchanged. Also any combination of mirror and complement will again be one of the four above operations (but you have to convince yourself on that).

The magic is Burnside's Lemma: the number of orbits under a group $G$ of permutations of a set $S$ equals $\frac1{|G|}\sum_{\psi\in G}|\text{fix}(\psi)|$.

The number of orbits here is the number of inequivalent cellular automata. Let's check the math: $\frac14(256+64+16+16) = 352/4 = 88$. This (again) confirms the number on Wikipedia.

Context

StackExchange Computer Science Q#38327, answer score: 3

Revisions (0)

No revisions yet.