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.
Is the number of inequivalent elementary cellular automata rules really 88?
automata;combinatorics;cellular automata
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 tdef complement(a):    return a ^ 0xffdef 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...UPDATEI 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 tthis 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.