5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

I tried it myself with the following Python code:

def yflip(a):
    D={0:0,1:4,2:2,3:6,4:1,5:5,6:3,7:7} # Vertical flip
    #D={0:7,1:6,2:5,3:4,4:3,5:2,6:1,7:0} # String reverse

    t=0
    for i in range(8):
        c=(a>>i)&1
        t |= c << D[i]
    return t

def complement(a):
    return a ^ 0xff

def canonical_form(a):
    b=yflip(a)
    c=complement(a)
    d=complement(yflip(a))
    return min(a,b,c,d)

A=set()
for patt in range(256):
    A.add(canonical_form(patt))
print len(A)

The dictionary D defines how to do a vertical flip. I think the correct interpretation is to move the state for the case 110 to the state for the case 011. This results in a different arrangement of the bits to just doing a straight string reverse.

Note wikipedia gives us a test case:

For example, if the definition of rule 110 is reflected through a vertical line, the following rule (rule 124) is obtained:

This works with my dictionary assert yflip(110)==124, but not with the string reverse.

The result for this is that with a straight string reverse I get 72 (same as yours).

With my interpretation of the vertical flip I get 80. Unfortunately, this is still not 88 so I am just as confused now...

UPDATE

I had misunderstood the complementary rule:

The actual complementary rule should be implemented as follows:

def complement(a):
    t=0
    for i in range(8):
        # Flip bits in this case
        x = i ^ 7
        # Try case x in the original pattern
        result = 1 & (a>>x)
        # Use the opposite
        result ^= 1
        t |= result << i
    return t

this results in 88 cases being found.

Note that you need to exchange 0's and 1's in both the cases, and in the final results.

$\endgroup$
  • $\begingroup$ Ok. Now I get it. My mistake was this: I though that to reverse the rule one just needs to reverse the bits of the rule number. But this is not the case. Thank you very much, Peter. $\endgroup$ – Vilius Normantas Feb 13 '15 at 17:29
  • $\begingroup$ A small tip: Rather than just appending "Update: the stuff above was wrong" to your answer, it's better to edit the answer so that answer is now fully correct and reads well to someone who is coming across it for the first time. (There's no need to preserve earlier versions of your answer; we have revision history for that.) $\endgroup$ – D.W. Feb 13 '15 at 17:40
  • $\begingroup$ @D.W. Thanks, I agree and I'll try to do that in future $\endgroup$ – Peter de Rivaz Feb 13 '15 at 18:47
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well, you lost me around that part about groups and orbits, so for me some magic will still remain in this question :) Nonetheless now I'm certain about the 88 rules, and I finally were able to reproduce them in my code. $\endgroup$ – Vilius Normantas Feb 14 '15 at 2:16
  • $\begingroup$ @ViliusNormantas I understand that. That is the reason I called it magic. My answer was prompted by the explicit number of automata that are invariant under the two basic rules that were mentioned in Wikipedia. Exactly the information we need to compute inequivalent cellular automata using Burnside's Lemma. However, we do not only need the two basic rules, but also their combinations (and inverses) to make it a "group" and to make the counting work. $\endgroup$ – Hendrik Jan Feb 15 '15 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.