Lawrence J. Thaden
Registered: Jan 2004
Posts: 357 
Structure Among ECA Rules
On page 883 and 884 in the NKS Book we see that the 256 ECA rules are related to each other.
For example, on page 883 cellular automata for rules 110 and 124 are specified as mirror images of each other.
And on page 884, rule 60 is seen to be composed of rules 240 and 204 through the operation XOR.
Xor[p, q] p = 240; q = 204; FromDigits[Mod[IntegerDigits[240, 2, 8] + IntegerDigits[204, 2, 8], 2], 2]
p Xor q
60
ECA Families
But there is another example of how the ECA rules can be seen as related to each other.
If all rules, that have the same cellular automaton behavior when run with simple initial conditions, are grouped together, they will be seen to be related to each other when run with the same random initial conditions, even though their individual behavior is unique.
Let all the rules, having the same cellular automaton behavior when run with simple initial conditions, be call a family. And name each family after its least rule number.
Then we see that rule 18 names the family having members {18, 26, 82, 90, 146, 154, 210, 218}.
With simple initial conditions the cellular automaton of each member has the same appearance, as seen in attached Figure 1a. But, as seen in Figure 1b, the behavior for each rule is unique when run with the same random initial conditions.
Chiral Relations
However, the cellular automata in the first row of Figure 1b are related. Rule 26 generates right chiral behavior, rule 82, left chiral behavior, and rule 90, neutral chiral behavior. But rule 18 seems to be class 3 with inconsistent chirality.
And in the second row, rule 154 generates right chiral behavior, rule 210, left chiral behavior, and rule 218, neutral chiral behavior. But rule 146 seems to be class 3 with inconsistent chirality.
So the three rightmost rules on each row are related by virtue of their chiral properties.
Modulo Two Sum Relations
How are these related to the leftmost rule in each row?
Modulo two sum of rules with chirality, 26, 82, and 90, results in the class 3 rule 18.
xrow1 = 26; yrow1 = 82; zrow1 = 90; FromDigits[ Mod[IntegerDigits[xrow1, 2, 8] + IntegerDigits[yrow1, 2, 8] + IntegerDigits[zrow1, 2, 8], 2], 2]
18
Similarly, modulo two sum of rules with chirality, 154, 210, and 218, results in the class 3 rule 146.
xrow2 = 154; yrow2 = 210; zrow2 = 218; FromDigits[ Mod[IntegerDigits[xrow1, 2, 8] + IntegerDigits[yrow1, 2, 8] + IntegerDigits[zrow1, 2, 8], 2], 2]
146
So the last three rules in each row are related to the first rules by modulo two sum, which is identified with the operation Xor.
Moreover, modulo two sum of all four rule numbers on each row is zero.
We can present this in equation form as subtraction of rule 18 from the other three rules due to the fact that modulo two sum is the same as modulo two difference:
rule 18 == (rules 26 + 82 + 90)
(0 == (rules 26 + 82 + 90)  rule 18).
0 == FromDigits[Mod[(IntegerDigits[26, 2, 8] + IntegerDigits[82, 2, 8] + IntegerDigits[90, 2, 8])  IntegerDigits[18, 2, 8], 2], 2]
True
0 == FromDigits[Mod[(IntegerDigits[154, 2, 8] + IntegerDigits[210, 2, 8] + IntegerDigits[218, 2, 8])  IntegerDigits[146, 2, 8], 2], 2]
True
So it is a zerosum mechanism. On the one side of the equation is the class 3 rule. On the other side are the chiral components.
This brings to mind a comparison with the dynamics of physics, where there is the randomness of virtual particle plasma on one side of the equation and real particles with and without left and right handed spin angular momentum on the other side of the equation. This too is a zerosum mechanism.
Cellular automaton behavior for rules {26, 82, 90} run with the same random initial conditions is analogous to particles with left, right, and no spin. And taken collectively, rules {26, 82, 90} are just another structural form of rule 18.
So rule 18 can manifest itself either as a sea of two kinds of cell values, boiling in apparently random class 3 fashion, or as three separate rules with definite chiral directions, none of whose behavior is at all random.
Incidentally, rule 18 has a very short existence as class 3. Run much more than the 50 time steps shown in figure 1b, it morphs to class 1.
And Halfcomplements
Taking it one step further, are rules in row 1 related to rules in row 2?
Modulo two sum of likechiral pairs of rule numbers, one taken from each of the two rows, is always the same.
It is rule 128: (p And q And r).
wrow1 = 18; wrow2 = 146; FromDigits[Mod[IntegerDigits[wrow1, 2, 8] + IntegerDigits[wrow2, 2, 8], 2], 2]
128
xrow1 = 26; xrow2 = 154; FromDigits[Mod[IntegerDigits[xrow1, 2, 8] + IntegerDigits[xrow2, 2, 8], 2], 2]
128
yrow1 = 82; yrow2 = 210; FromDigits[Mod[IntegerDigits[yrow1, 2, 8] + IntegerDigits[yrow2, 2, 8], 2], 2]
128
zrow1 = 90; zrow2 = 218; FromDigits[Mod[IntegerDigits[zrow1, 2, 8] + IntegerDigits[zrow2, 2, 8], 2], 2]
128
Notice on page 884 of the NKS Book that rules 127 and 128 are the middle two rules in the list of all possible rules for the two color rules. In fact these two rules represent (p Or q) and (p And q) respectively. These are so called complements of each other.
Since the pairs of rules from row 1 and row 2 sum modulo two to 128, which is the And rule, let us call these pairs of rules from row 1 and 2 And halfcomplements.
Algebraic Expressions vs Rule Numbers
For the most part we have restricted our discussion to rule numbers. But on page 884 of the NKS Book we see that each rule number is associated with a unique Boolean algebraic expression.
Now, in dealing with rule numbers we refer to their digit expansions. These digit expansion values are ordered left to right by place values, which are powers of two:
{128, 64, 32, 16, 8, 4, 2, 1}.
For example, rule 17 has digit expansion {0, 0, 0, 1, 0, 0, 0, 1}.
The place values for 16 and 1 have digit 1. And modulo two sum of 16 and 1 is 17.
So we say that modulo two sum (Xor) is the operation that joins the place values of the digits to form the rule number.
On the other hand, when discussing Boolean algebraic expressions, we speak of the minterms, rather than the digits. One arrangement of the minterms is sum of products form, called disjunctive normal form (DNF).
The eight DNF minterms from left to right for the two color rules in variables {p, q, r} are:
128: (p And q And r),
64: (p And q And Not r),
32: (p And Notq And r),
16: (p And Notq And Notr),
8: (Notp And q And r) ,
4: (Notp And q And Notr),
2: (Notp And Notq And r) ,
1: (Notp And Notq And Notr)
These terms, when corresponding to a 1 digit of the digit expansion, are joined algebraically by the Or operation to form the algebraic expression for the rule.
For example, rule 18 corresponds to the Or of algebraic expressions for rules 16 and 2:
FromDigits[Boole[BooleanTable[Or[And[p, Not[q], Not[r]], And[Not[p ], Not[q], r]]]], 2]
18
Coefficients of Minterms
More generally, this can be stated as: the digits in the digit expansion are coefficients of the corresponding minterms. Each coefficient is joined algebraically to its minterm by the And operation. The resulting terms are joined algebraically by the Or operation to form the algebraic expression of the rule.
Joining coefficients by the And operation drops the minterm when the coefficient is zero since (0 And n) is always 0, but retains the minterm when the digit is 1 since (1 And n) is always n.
Algebraic Substantiation – Class 3 Rules and Chirality
Now let us use this information to add substance to our discussion about chiral relations among cellular automata generated by rules of ECA family 18. We restrict our discussion to the first row in figure 1b. But same procedure can be carried out with the second row of rules: {146, 154, 210, 218}.
Recall that, with the same random initial conditions, chiral rules 26, 82, and 90 sum modulo two to class 3 rule 18.
Here are the algebraic expressions for these rules as given on page 884 of the NKS Book:
26: p Xor ((p And q) Or r)
82: (p Or (q And r)) Xor r
90: p Xor r
18: (p Xor q Xor r) And (Notq)
Sum the first three algebraic expressions modulo two using the Xor operation.
Xor[(Xor[p, Or[(And[p, q]), r]]), (Xor[(Or[p, (And[q, r])]), r]), (Xor[p, r])]
The result is: Xor[(Or[p, And[q, r]]), (Or[And[p, q], r])].
Is this sum equivalent to the algebraic expression for rule 18, which is listed above as: (p Xor q Xor r) And (Notq)?
Well, both algebraic expressions convert to rule 18.
FromDigits[Boole[BooleanTable[Xor[(Or[p, And[q, r]]), (Or[And[p, q], r])]]], 2]
18
FromDigits[Boole[BooleanTable[And[Xor[p, q, r] , Not[q]]]], 2]
18
So, rule numbers and their algebraic expressions are related. And in this instance the relation is such that the class 3 rule 18 is the modulo two sum of the three chiral rules: {26, 82, 90}.
This is illustrated by the plots of the rules in figure 1b. As we have seen, rule 26 generates right chiral behavior, rule 82, left chiral behavior, and rule 90, neutral chiral behavior. But it is premature to say that all class three rules are composed of a right, left, and neutral chiral rule.
Algebraic Substantiation – And halfcomplements
We saw above that rules in row 1 of figure 1b sum modulo two to 128 with rules in row 2 when the pair of rules are in the same column. So the pairs of rules summing modulo two to 128 are:
{18, 146}, {26, 154}, {82, 210}, {90, 218}.
Now we want to check that the algebraic expressions for these pairs of rules combine to make the algebraic expression for rule 128 which is (p And q And r).
We take the algebraic expressions of the pairs of rules from page 884 of the NKS Book.
First, the class 3 pair:
18: (p Xor q Xor r) And (Notq)
146: (p Xor ((p Or r) And q) Xor r)
Sum them modulo two:
Simplify[Xor[And[Xor[p, q, r], Not[q]], Xor[p, And[Or[p, r], q], r]]]
The result is AND[p, q, r].
This corresponds to rule 128:
FromDigits[Boole[BooleanTable[Xor[And[Xor[p, q, r], Not[q]], Xor[p, And[Or[p, r], q], r]]]], 2]
128
Now for the right chiral pair:
26: p Xor ((p And q) Or r)
154: p Xor (p And q) Xor r
Sum them modulo two:
Simplify[Xor[Xor[p, Or[And[p, q], r]], Xor[p, And[p, q], r]]]
The result is AND[p, q, r].
Next the left chiral pair:
82: (p Or (q And r)) Xor r
210: p Xor (q And r) Xor r
Sum them modulo two:
Simplify[Xor[Xor[Or[p, And[q, r]],r], Xor[p, And[q, r], r]]]
The result is AND[p, q, r].
Finally, take the pair with neutral chirality:
90: p Xor r
218: p Xor (p And q And r) Xor r
Sum them modulo two:
Simplify[Xor[Xor[p, r], Xor[p, And[p, q, r], r]]]
The result is AND[p, q, r].
Conclusion
We illustrated through an example of one family of ECAs that a class 3 rule manifests behavior that is related to the behavior of triplets of rules within the same family. And that pairs of rules in the family are so called AND halfcomplements.
But the family we discussed is not the only family among the ECAs.
The 256 ECAs fall into 143 families, most of which have a single member.
But here are 24 families that have more than one member:
1. {1, 33}
2. {3, 35}
3. {11, 43}
4. {17, 49}
5. {28, 156}
6. {70, 198}
7. {81, 113}
8. {129, 161}
9. {139, 171}
10. {206, 238}
11. {220, 252}
12. {222, 254}
13. {6, 38, 134, 166}
14. {14, 46, 142, 174}
15. {20, 52, 148, 180}
16. {84, 116, 212, 244}
17. {18, 26, 82, 90, 146, 154, 210, 218}
18. {23, 31, 55, 63, 87, 95, 119, 127}
19. {50, 58, 114, 122, 178, 186, 242, 250}
20, {151, 159, 183, 191, 215, 223, 247, 255}
21: {0, 8, 32, 40, 64, 72, 96, 104, 128, 136, 160, 168, 192, 200, 224, 232}
22. {2, 10, 34, 42, 66, 74, 98, 106, 130, 138, 162, 170, 194, 202, 226, 234}
23. {4, 12, 36, 44, 68, 76, 100, 108, 132, 140, 164, 172, 196, 204, 228, 236}
24. {16, 24, 48, 56, 80, 88, 112, 120, 144, 152, 176, 184, 208, 216, 240, 248}
Notice that there are only four families the size of the one discussed here.
Obviously, what has been said is not the last word concerning how members of the families are related.
For instance it could never be said of members of the first 12 families that the leftmost three rules on a row summed modulo two to the first rule.
Figures 1a and 1b are attached.
Lawrence J. Thaden has attached this image:
__________________
L. J. Thaden
Report this post to a moderator  IP: Logged
