Lawrence J. Thaden
Registered: Jan 2004
Posts: 350 |
162 Three Color Rules with Simple AND Type Algebraic Expressions in Three Variables
162 Three Color Rules with Simple AND Type Algebraic Expressions in Three Variables
Abstract
There is a one to many relation between rule numbers and their algebraic expressions such that any two algebraic expressions with the same rule number are equivalent.
We examine 162 three color rule numbers that have simple AND type algebraic expressions and three variables. These rules represent all possible algebraic expressions with some type of AND and some type of variables p, q, and r.
When taken with rule numbers for the identities (additive, positive multiplicative, and negative multiplicative), the rule numbers form 27 closed sets, each with nine members. These sets can be input as ternary Cartesian products to a map function, and six projections can be generated each with dimensions of 27 x 27 x 27 cells. There is one projection for each of six AND type rules. The other three rules of the closed sets are the identities. These are not included in this presentation since their projections are uniform and, as such, trivial cases.
Colors are assigned to replace the rule numbers in the projected cells. This results in a set of nested cubes. It was discovered that these cubes come in three pairs of complementary colorings.
These nested cubes are easily recognized by a telltale cluster of 27 contiguous cuboids each with the same color, save one single cuboid which serves as an indicator, showing where the cluster is located relative to the rest of the cells in the cube.
Complementary pairs are identified as inverses of each other in this sense: the modulo two sum of their rule numbers equals one of the identities: additive, positive multiplicative, and negative multiplicative identity.
Pairs associated with multiplicative identities suggest a kind of multiplicative inverse, even though there is no basic operator for modulo three division.
From the changing location of the clusters in the different projections, it is evident that there are 27 unique sets for each AND type. And since there are only six possible AND types, this accounts for all 162 three color rules.
The use of colors in place of rule numbers highlights the fact that all of the cubes are related to each other by virtue of the position of the rule numbers in the closed sets.
There is one exception to this relation of rule numbers to position within closed sets. It occurs with the closed set for AND types having representative algebraic input of {-p, -q, -r}.
In this one exception the three complementary pairs of nested cubes is reversed so that the inverse cube is switched with the non-inverse cube and the colors of the nesting are also switched within each cube.
This one exception makes it possible to chain like cubes in stair-step fashion, where the exception cluster matches complementarily with the cluster at the point of origin on the following cube. And the stair-step string can be closed by wrapping the last in the series of steps around so that it joins the first cube at its point of origin.
Next we explore the behavior of cellular automata of these 162 rules. It turns out that all belong to class 1. They have simple structures and terminate in a single state. However when certain of these rules are combined modulo three sum, the results are class 2 cellular automata. They have nested structure. And when rule numbers for two of these class 2 cellular automata are combined modulo three sum, they result in a rule number that generates a class 3 cellular automaton.
So it is possible to observe more and more complex cellular automaton behavior by combining and recombining these 162 simple AND type rules.
But to observe class 4 behavior, rules with simple forms of AND type and three variables input must be combined with AND type rules with two input variables.
Introduction
On page 884 of the NKS Book ECA rules are listed together with Boolean expressions. Pages 883-884 explain: "The expressions use the minimum possible number of operators". Wolfram continues: "when there are several equivalent forms, I give the most uniform and symmetrical one."
The fact that Wolfram stated "when there are several equivalent forms" indicates that he recognized that, at least for some of the ECA rule numbers, there is a one to many relation between rule number and Boolean expressions.
In fact there is a one to many relation between every rule number and its equivalent Boolean expressions. The reason is that, by De Morgan's Law each of the Boolean expressions has an equivalent expression obtained by complementing the variables and swapping the AND and OR operators.
And even when the expression uses XOR as an operator De Morgan's Law holds, for XOR can be expressed in terms of AND and OR.
Therefore, for the entire set of ECA rule numbers, there is a one to many relation between rule number and Boolean expressions.
Relation Between Rule Number and Algebraic Expression
The implication of this one to many relation is that rule number can be used as a test for equivalence of Boolean expressions.
Any number of different Boolean expressions that have the same rule number are equivalent Boolean expressions.
Simplification of Boolean Expressions
If a dictionary of all possible rule numbers and their most simple Boolean expressions for the ECAs is maintained, then any Boolean expression, no matter how complex, can be simplified by a dictionary look-up on rule number.
Wolfram's list of rule numbers and expressions on page 884 of the NKS Book serves as the dictionary for Boolean expressions with three variables.
And Mathematica expressions which equate the variables and operators to rule numbers can be manipulated so as to find their rule number.
For example, note that ECA rule number 85 is associated with expression NOT[r] while rule number 204 is associated with q. And modulo 2 sum is associated with operator XOR. With the following Mathematica expressions we can find the rule number for q XOR NOT[r].
q=204;
notr=85;
FromDigits[Mod[IntegerDigits[q,2,8]+IntegerDigits[notr,2,8],2],2]
153
Looking up rule number 153 on page 884 of the NKS Book, we find the expression q XOR NOT[r].
Moreover, any such Mathematica expression, no matter how long or complex, that results in rule 153 is equivalent to the simple expression q XOR NOT[r].
Here is a second example. It involves AND instead of XOR. The rule number for q AND NOT[r] uses modulo 2 product instead of modulo 2 sum.
FromDigits[Mod[IntegerDigits[q,2,8] IntegerDigits[notr,2,8],2],2]
68
So any expression, no matter how complex, that is associated with ECA rule number 68 is equivalent to q AND NOT[r].
What's the Point
We are not advocating doing Boolean algebra in this manner. Mathematica does it symbolically in a much more efficient way.
The point to be taken is that there is a one to many relation between rule numbers and algebraic expressions.
As was stated above in the Introduction an obvious example of the ubiquity of this one to many relation is demonstrated with De Morgan's Law, which states equivalence of Boolean expressions involving AND on the one hand and OR on the other.
Applying De Morgan's law to the algebraic expression q AND NOT[r] mentioned above results in the equivalent expression NOT[q] OR r. And both of these expressions have the same rule number. Namely, rule 68.
There is an analogy to this procedure of applying De Morgan's Law to Boolean expressions. It is found in topography where a structure can be deformed into another structure of the same class.
For example, a sphere changing into an ellipsoid. The sphere is to the AND expression as the ellipsoid is to the OR expression. And the class is to the rule number.
Three Color Rules and Their Algebraic Expressions
Operators
The discussion above dealt with ECA rules. Now let's consider three color rules. These have algebraic expressions that include signed values. In other respects they are similar to ECA rules and their algebraic expressions with AND and OR.
However since De Morgan's Law allows for any OR operator expression to be stated as an equivalent AND operator expression, we will simply use the AND operator.
We find there are just six possible AND type operators. They are:
0 + AND = AND
0 - AND = -AND
1 + AND
1 - AND
-1 + AND
-1 - AND
As can be seen, each type of identity has two types of AND associated with it.
0 is additive identity. 1 is positive multiplicative identity. -1 is negative multiplicative identity.
In English we call these operators:
AND
minus AND
minus NOT[AND]
minus NOT[minus AND]
NOT[minus AND]
NOT[AND]
Variables
We restrict the discussion to three variables. Following the pattern of the ECAs, the variables are p, q, and r. But as with the operators, there are six possible types for each of the three variables.
Here are the types for p:
p
-p
1+p
1-p
-1+p
-1-p
In English we call these:
p
minus p
minus NOT[p]
minus NOT[minus p]
NOT[minus p]
NOT[p]
Forming Expressions
Each type of AND can be conjugated through all its possible variables.
So we have:
AND[p,q,r], AND[p,q,-r], AND[p,q,1+r], AND[p,q,1-r], AND[p,q,-1+r], AND[p,q,-1-r],
AND[p,-q,r], AND[p,-q,-r], AND[p,-q,1+r], AND[p,-q,1-r], AND[p,-q,-1+r], AND[p,-q,-1-r],
AND[p,1+q,r] ...
AND[p,1-q,r] ...
AND[p,-1+q,r] ...
AND[p,-1-q,r] ...
AND[-p,q,r] ...
...
and so forth for a total of 216 AND expressions. But there are 5 more AND types, each with 216 conjugated expressions. So the total number of possible expressions is 1296.
Rule Numbers vs Expressions
As might be guessed, not every conjugated expression has a unique rule number. It so happens that each rule number is associated with 8 different conjugated expressions. That means there are eight equivalent expressions for each rule number. And there are only 162 unique rule numbers for all of the AND expressions.
As an example here are the eight equivalent expressions for rule number 2:
-AND[-1 - p, -1 - q, -1 - r]
-AND[-1 - p, -1 - q, -1 + r]
-AND[-1 - p, -1 + q, -1 - r]
-AND[-1 - p, -1 + q, -1 + r]
-AND[-1 + p, -1 - q, -1 - r]
-AND[-1 + p, -1 - q, -1 + r]
-AND[-1 + p, -1 + q, -1 - r]
-AND[-1 + p, -1 + q, -1 + r]
Using Mathematica to Establish Equivalent Three Color Rules for Three Variable AND Expressions
To show that each of the above -AND algebraic expressions is equivalent we use Mathematica to see that they all are associated with rule number 2.
As explained elsewhere on the Forum, AND is associated with rule number 2541865828329. The rule number for -AND is found by finding the difference between additive identity which is 0 and AND.
and=2541865828329;
negativeAND=FromDigits[Mod[IntegerDigits[0,3,27]-IntegerDigits[and,3,27],3],3]
5083731656658
Negative multiplicative identity is -1 and is associated with rule number 7625597484986.
minus1=7625597484986;
Variables p, q, and r are associated with rule numbers 3812992433055, 3943753520967, 4399383164415 respectively.
{p=3812992433055,q=3943753520967,r=4399383164415};
-1-p, -1-q, -1-r are algebraic expressions for NOT[p], NOT[q], and NOT[r].
Rule numbers for Not[p], Not[q], and Not[r] are found by finding the difference between negative multiplicative identity which is -1 and the variable.
NOTp=FromDigits[Mod[IntegerDigits[minus1,3,27]-IntegerDigits[p,3,27],3],3]
NOTq=FromDigits[Mod[IntegerDigits[minus1,3,27]-IntegerDigits[q,3,27],3],3]
NOTr=FromDigits[Mod[IntegerDigits[minus1,3,27]-IntegerDigits[r,3,27],3],3]
3812605051931
3681843964019
3226214320571
-1+p, -1+q, -1+r are algebraic expressions for NOT[negativep], NOT[negativeq], and NOT[negativer].
Rule numbers for Not[negativep], Not[negativeq], and Not[negativer] are found by finding the sum of negative multiplicative identity which is -1 and the variable.
NOTnegativep=FromDigits[Mod[IntegerDigits[minus1,3,27]+IntegerDigits[p,3,27],3],3]
NOTnegativeq=FromDigits[Mod[IntegerDigits[minus1,3,27]+IntegerDigits[q,3,27],3],3]
NOTnegativer=FromDigits[Mod[IntegerDigits[minus1,3,27]+IntegerDigits[r,3,27],3],3]
193720085
146064945221
1466461054805
Now we can show the equivalence of the 8 expressions that have rule number 2.
We use the map function defined elsewhere in forum posts.
-AND[-1 - p, -1 - q, -1 - r]
map[negativeAND,NOTp,NOTq,NOTr]
2
-AND[-1 - p, -1 - q, -1 + r]
map[negativeAND,NOTp,NOTq,NOTnegativer]
2
-AND[-1 - p, -1 + q, -1 - r]
map[negativeAND,NOTp,NOTnegativeq,NOTr]
2
-AND[-1 - p, -1 + q, -1 + r]
map[negativeAND,NOTp,NOTnegativeq,NOTnegativer]
2
-AND[-1 + p, -1 - q, -1 - r]
map[negativeAND,NOTnegativep,NOTq,NOTr]
2
-AND[-1 + p, -1 - q, -1 + r]
map[negativeAND,NOTnegativep,NOTq,NOTnegativer]
2
-AND[-1 + p, -1 + q, -1 - r]
map[negativeAND,NOTnegativep,NOTnegativeq,NOTr]
2
-AND[-1 + p, -1 + q, -1 + r]
map[negativeAND,NOTnegativep,NOTnegativeq,NOTnegativer]
2
Which Expression to Use?
Just as Wolfram had to do when listing the Boolean expressions for the ECA rule numbers on page 884 of the NKS Book, so we need to do with these expressions. We have to choose one from the eight.
Our criterion for selecting one from the eight expressions as representative of the set of equivalent expressions is to take the one that sorts out last. For rule number 2 it is -AND[-1+p, -1+q, -1+r].
The complete list of representative expressions for all 162 rules is shown in Figure 1. Notice that the list of variables is in the same order for the types of AND expressions in the three columns at the top of the figure. And the order is reversed in the three columns at the bottom of the figure.
Mathematica User Defined Functions for Negative and Complemented Expressions
The following user defined functions facilitate presentation of the various forms of operators and variables. We present them here since they will be used extensively in the discussion that follows.
neg returns the additive inverse of an operator or a variable. rn stands for rule number but may be a symbol representing operator or variable.
neg[rn_]:=map[prodpq,minus1,rn,dontcare]
where prodpq is rule number 3943933137846, which represents the modulo three product of p and q.
not returns the negative multiplicative complement of its input argument.
not[rn_]:=map[diffpq,minus1,rn,dontcare]
where diffpq is rule number 146430861993, which represents the modulo three difference between p and q.
Note on Operator vs Operands Input to map Function
These 162 rules take all three input variables as operands to the map function. There are other rules that only take two of the three input variables, and still others that take only one of the three input variables with the AND type operators. When using the map function, and less than three input variables are required, the map function ignores the other inputs. As a convention we usually assign the symbol "dontcare" to the ignored operand and give it a value of 0.
Since these 162 rules require all three variables as input to the map function, the associative law comes into play. While associativity holds for a list of operators each having three input variables as operands, it is not possible to break down any one set of three inputs and use the associative law to obtain their result piece by piece.
For example, here are three expressions:
a = AND[p, -1+q, r]
b = AND[-p, q, 1+r]
c = AND[1-p, q, -1-r]
Say we want to find AND[a, b, c].
We can apply the associative law:
AND[AND[a, b], c]
or
AND[a, AND[b, c]]
for the same result.
But if we have as an example AND[p, q, r]
where AND is rule 1594323 (see Figure 1.), the associative law is not applicable because rule 1594323 acts on all three variables simultaneously.
You might compare this to quarks in physics. Baryons require three quarks and these 162 AND type expressions require three input variables. However mesons require just two quarks and there are other AND type operators outside this set of 162 rule numbers that require just two variables as input.
Incidentally, there are six types of quarks (up, down, top, bottom, and strange and beauty) just as there are six types of AND expressions.
Here is an example of an AND type analogous to the mesons in physics. It takes two negative inputs and a dontcare. Its rule number is not one of the 162 rules listed in Figure 1.
dontcare=0;
andpq=7625597484973;
map[andpq,neg[p],neg[q],dontcare]
7625597484973
Notice that this result is the same rule number as that used for andpq. In general, whenever the operator is specified without its operand inputs, the assumption is that the inputs are additive inverses of the operand variables.
Here is an example of an operator that takes one input and two dontcares. Its rule number is not one of the 162 rules listed in Figure 1. It returns the negative multiplicative complement of the additive inverse of the first operand. In the example you can see that it flips the sign of the operand p, and then complements the result.
map[not[p],p,dontcare,dontcare]==not[neg[p]]
True
Complementary Pairs of Variables and Operators
Here are complementary variable pairs for p. They sum to -1, the negative multiplicative identity. Similar code can be written for variables q and r.
p and -1-p
FromDigits[Mod[IntegerDigits[p,3,27]+IntegerDigits[not[p],3,27],3],3]==minus1
True
-p and -1+p
FromDigits[Mod[IntegerDigits[neg[p],3,27]+IntegerDigits[not[neg[p]],3,27],3],3]==minus1
True
1+p
Positive multiplicative identity is 1. Here is its rule number. It is combined with p to make 1+p, which is the same as -1(-1-p), where -1(-1-p) is neg[NOT[p]].
plus1=3812798742493;
negNOTp=FromDigits[Mod[IntegerDigits[plus1,3,27]+IntegerDigits[p,3,27],3],3]
negNOTp==neg[not[p]]
7625210074339
True
1-p
Here positive multiplcative identity has p subtracted from it to make 1-p, which is the same as -1(-1+p), where -1(-1+p) is neg[NOT[neg[p]]].
negNOTnegp=FromDigits[Mod[IntegerDigits[plus1,3,27]-IntegerDigits[p,3,27],3],3]
negNOTnegp==neg[not[neg[p]]]
387410647
True
1+p and 1-p
The two above expressions are also complementary expressions of each other with respect to negative multiplicative identity.
FromDigits[Mod[IntegerDigits[negNOTp,3,27]+IntegerDigits[negNOTnegp,3,27],3],3]==minus1
True
Here are complementary operator pairs for AND. They sum to -1, the negative multiplicative identity.
AND and -1-AND
FromDigits[Mod[IntegerDigits[and,3,27]+IntegerDigits[not[and],3,27],3],3]==minus1
True
-AND and -1+AND
FromDigits[Mod[IntegerDigits[neg[and],3,27]+IntegerDigits[not[neg[and]],3,27],3],3]==minus1
True
1+AND and 1-AND
FromDigits[Mod[IntegerDigits[neg[not[and]],3,27]+IntegerDigits[neg[not[neg[and]]],3,27],3],3]==minus1
True
Other Complementary Pairs
The examples in the previous section are of complementary pairs with respect to the negative multiplicative identity. All six operators and variables can also be selected as pairs of complements with respect to additive identity and positive multiplicative identity.
Here is an example of operator pairs that sum to additive identity.
AND and -AND
FromDigits[Mod[IntegerDigits[and,3,27]+IntegerDigits[neg[and],3,27],3],3]==0
True
Here is an example of variables that sum to positive multiplicative identity.
q and 1-q
FromDigits[Mod[IntegerDigits[q,3,27]+IntegerDigits[neg[not[neg[q]]],3,27],3],3]==plus1
True
De Morgan's Law Extended to Three Color, Three Variable Rules
Just as with Boolean expressions, so with these three color, three variable expressions, De Morgan's Law can be applied to the AND type to turn it into an equivalent OR type expression. And the rules for applying De Morgan's Law are the same in three color logic.
With Boolean algebra you complement the variables and change the AND operator to an OR operator and then complement it. For example:
AND[p, q] = NOR[NOT[p], NOT[q]]
Similarly with three color, three variable algebraic expressions, you complement the variables and change the operator from AND to OR, and then you also complement the operator. The signs on the variables are not affected. They stay the same.
Figure 2. presents a table for equivalent AND type and OR type expressions when the AND type has {-1+p, -1+q, -1+r} as input variables. Notice that the three identity operators (0, 1, -1) are included but that they are not affected by De Morgan's Law.
To see how De Morgan's Law is applied, we illustrate step by step for rule number 3812798742492: 1-AND[-1+p, -1+q, -1+r] = -1+OR[-p, -q, -r].
(1) Complement the variables:
not[not[neg[p]]]==neg[p]
not[not[neg[q]]]==neg[q]
not[not[neg[r]]]==neg[r]
True
True
True
(2) Change AND type to OR type: 1-AND -> 1-OR.
(3) Complement 1-OR[-p, -q, -r], where 1-OR in code is neg[not[neg[OR]]] and the result is -1+OR (in code: not[neg[OR]]):
map[not[neg[or]],map[neg[not[neg[or]]],neg[p],neg[q],neg[r]],dontcare,dontcare]==map[not[neg[or]],neg[p],neg[q],neg[r]]
True
All 162 rules are subject to De Morgan's Law, not just the ones shown in Figure 2.
Tables for Three Color Rules and Their Algebraic Expressions
We now want to organize these 162 rule numbers and their algebraic expressions so that all of the AND types that have the same variables are ordered as complementary pairs. There will be one pair that sums modulo three to positive multiplicative identity. Another pair that sums modulo three to negative multiplicative identity, and a third pair that sums modulo three to additive identity.
Each set of three pairs of rules and algebraic expressions having the same set of three variables together with the three identities forms a closed set with nine members. These sets are closed in this respect: using each rule number with three of the other rule numbers in the map function always returns a rule number belonging to the set.
As an example consider the set that has variables: {-1+p, -1+q, -1+r}. Its members are:
0: 0
1: AND
2: -AND
3812798742492: 1-AND
3812798742493: 1
3812798742494: 1+AND
7625597484984: -1+AND
7625597484985: -1-AND
7625597484986: -1
This is the same set that was illustrated on the left side of Figure 2.
When the rule numbers of this set are input to the following Mathematica code, the result returned is identical to the input. It is in this sense that the set is said to be closed.
rules={0,1,2,3812798742492,3812798742493,3812798742494,7625597484984,7625597484985,7625597484986};
Union[Flatten[Table[map[rules[[i]],rules[[j]],rules[[k]],rules[[l]]],{i,Length[rules]},{j,Length[rules]},{k,Length[rules]},{l,Length[rules]}]]]
{0, 1, 2, 3812798742492, 3812798742493, 3812798742494, 7625597484984, 7625597484985, 7625597484986}
From this set the pair that sums modulo three to positive multiplicative identity is 1: AND and 3812798742492: 1-AND.
FromDigits[Mod[IntegerDigits[1,3,27]+IntegerDigits[3812798742492,3,27],3],3]== 3812798742493
True
The pair that sums to negative multiplicative identity is: 2: -AND and 7625597484984: -1+AND.
FromDigits[Mod[IntegerDigits[2,3,27]+IntegerDigits[7625597484984,3,27],3],3]== 7625597484986
True
The pair that sums to additive identity is: 3812798742494: 1+AND and 7625597484985: -1-AND.
FromDigits[Mod[IntegerDigits[3812798742494,3,27]+IntegerDigits[7625597484985,3,27],3],3]==0
True
When all of the rule numbers have been ordered in this way, there are 27 sets of three pairs of complementary rules. Each set has the same AND types paired as in the example above. But each set has different rule numbers and a unique set of operands.
We have organized all of this information in three charts. They are presented in Figures 3, 4, and 5. Note several things about these figures.
(1) Representative input variables listed in black never have more than one instance of a variable. So, for example, you will never find {p, p, r} because that would be two instances of p. This also applies to instances in which the variable has different types, such as p and 1-p. So you would never find {p, 1-p, r} for the same reason you would never find {p, p, r}.
(2) Each list of three variables in black is unique.
(3) There are three rows of three columns of information in each figure. Call these row-column locations boxes.
(4) Each box has six different rule numbers and its AND type displayed above it. This accounts for all possible AND type rule numbers for the set of variables listed in the box.
(5) With one exception AND types are consistently color coded over all of the boxes. For example the color green is reserved for 1-AND. The exception is on Figure 5. in the box that has variables {-p, -q, -r}. For this set of three pairs, the colors of the types of AND are complemented. Red becomes green, blue becomes orange, etc. The reason for this will be explained later.
(6) Each box has three pairs of rule numbers and AND types.
(7) The first pair are complementary with respect to positive multiplicative identity in the sense that they sum modulo three to positive multiplicative identity. This is indicated by the (+1) at the right side of the box. So these rules are a kind of inverse of each other with respect to positive multiplicative identity.
(8) The second pair are complementary with respect to negative multiplicative identity in the sense that they sum modulo three to negative multiplicative identity. This is indicated by the (-1) at the right side of the box. So these rules are a kind of inverse of each other with respect to negative multiplicative identity.
(9) While there is no operation of modulo three division, there is a kind of multiplicative inverse of rule numbers.
(10) The third pair are complements with respect to additive identity. This is indicated by the (0) at the right side of the box. So these rules are actual inverses of each other with respect to additive identity.
(11) Each box is labeled to indicate a position within a cube with dimensions: 3 x 3 x 3. These 3 x 3 x 3 structures will be called clusters. For example the box in the upper left corner of Figure 3. is labeled Bottom: Row 1, Col 1 to indicate that clusters for the AND types for this box will be located at the bottom of the z axis at cells 1-3 on the x and y axes of a 3D graph of all possible products for the closed set of rule numbers included in the box. This will be explained in the next section.
Graphs of Ternary Cartesian Product Projections for Each AND type
The closed sets of rule numbers for each of the boxes discussed in the previous section can be considered a vector. All members of this vector are input in turn into the map function as operands {p, q, r} with each of the vector members in turn as operator.
The results are a set of projections of vector members that fill a cube with dimensions 9 x 9 x 9. For each vector there are 27 such cubes, and each cube has locations filled with 729 instances of a rule number.
Here is the Mathematica code to generate the cube for rule number 1: AND[-1+p,-1+q, -1+r]:
rules
{0, 1, 2, 3812798742492, 3812798742493, 3812798742494, 7625597484984, 7625597484985, 7625597484986}
Table[map[rules[[2]],rules[[i]],rules[[j]],rules[[k]]],{i,Length[rules]},{j,Length[rules]},{k,Length[rules]}];
Dimensions[%]
{9, 9, 9}
Once these rule numbers are generated, they are replaced by a color indicating their position within the closed set of nine rule numbers.
Figures 6 and 7 present graphs related to the information in the boxes of Figure 4. While the boxes contain all possible AND types and all possible variables, Figures 6. and 7. are only a sample of two boxes. To present graphs for all of the information in the boxes would take 9 figures like Figure 6. or Figure 7. for Figure 4. and 9 figures each for Figure 3. and Figure 5.
Note several things about Figure 6. and Figure 7.
(1) Each figure has three pairs of projections representing the pairs of AND types in two of the boxes of Figure 4. As stated above, projections are formed by taking all six rule numbers within a box together with the three rule numbers of the identities. Then the map function is used with the AND type rule number for the graph as operator together with sets of three rule numbers as operands to make a set of 729 rule number results. These rule numbers are then replaced by one of nine colors, although for any one graph there are only four colors because the rule numbers returned from the map function happen to be one of two identities, the rule used as operator, and its complement.
(2) The color selected for a rule number corresponds to the position in the list of sequentially ordered rule numbers and identities used to generate the cube.
(3) Each set of nine rules is a closed set. No two sets of rules representing the information in the boxes of Figure 4 are alike.
(4) The information in the graphs is nested three deep. There is a single cuboid which occupies one of 27 positions in another set of cuboids that has dimensions 3 x 3 x 3. This other set of cuboids is positioned within the entire graph in one of 27 locations indicated by the position of the single cuboid within this set of cuboids. We call this 3 x 3 x 3 set of cuboids a cluster and refer to its location within the cube as the location of the cluster. In addition to the cluster, the full cube has 27 single cuboids evenly spaced throughout itself. But even these evenly spaced cuboids occupy one of 27 locations relative to the single cuboid within the cluster. So as the cluster location changes with each of 27 graphs, the locations of the evenly spaced cuboids change as well.
(5) The individual cuboids making up the clusters are of a consistent color complementary to the color of the evenly spaced cuboids. This color is the same as that used to print the AND type in its corresponding box in Figure 4.
(6) Cubes of a pair of graphs have complementary colors for their clusters, as well as for their evenly spaced cuboids.
(7) Each pair of graphs has a legend showing the colors used to represent the AND types and identity types.
(8) Figure 6. corresponds to the box labeled Middle: Row 1, Col 1 of Figure 4. and Figure 7. corresponds to the box labeled Middle: Row 3, Col 1 of Figure 4.
Graphs of Exceptional Box
One box, as was mentioned above, has complementary colors. It occurs when the input variables are {-p, -q, -r}. This is the box labeled Top: Row 3, Col 3 in Figure 5. Both the box and the graphs of the rules in the box break the pattern observed for all the other boxes and graphs. The reason is this: rule numbers for this closed set are not in sequence when paired with the constant order of algebraic expressions.
Here is the order of the algebraic expressions for all of the boxes:
{0, AND, -AND, 1-AND, 1, 1+AND, -1+AND, -1-AND, -1}
The order of the rules would have to break sequential order for the exceptional box in order for them to follow the above order of expressions. Here is how the rules would look:
{0, 2541865828329, 5083731656658, 1270932914164, 3812798742493, 6354664570822, 2541865828328, 5083731656657}
Here is the order of the algebraic expressions for this non-sequential set of rule numbers:
{0, 1-AND, -1+AND, AND, 1, -1-AND, -AND, 1+AND, -1}
Rules for the exceptionally ordered algebraic expressions, when sequential order is maintained, are:
{0, 1270932914164, 2541865828328, 2541865828329, 3812798742493, 5083731656657, 5083731656658, 6354664570822, 7625597484986}
Since colors replace rule numbers in the graphs, the colors for this exceptional case are different. In fact they turn out to be complementary to the colors in the non-exceptional cases. See Figure 8.
This exception is puzzling. Everything in this system of logic seems to be well ordered. And to come upon this exception was a surprise.
Consequences of the Exceptional Box
If graphs for all 27 boxes of Figures 3, 4, and 5 were superimposed for any one of the AND types, we would find that the cube had twenty-six clusters all colored the same, but one cluster colored complementary to these. That would be the cluster for the exception box. It stands out at the corner diagonal to the corner of origin as some sort of valence, or capacity to form a radical bond with other cubes of the same AND type.
Moreover, the evenly spaced cuboids are also superimposed, and with all 27 graphs of an AND type they form 27 clusters occupying the same locations as the clusters. So, since they are complementary colored, you have the appearance of one of the colors of the identity for the entire superimposed cube. For example, with AND the colors of the clusters are red and the colors of the evenly spaced cuboids are green. But the identity for AND is 0, so the cube would appear light brown.
But if instead of viewing the cube as a superposition of clusters, we view the cube as stepping through 27 states, all the while occupying the same space, the location of the cluster will move about as will the locations of the evenly spaced but complementarily colored cuboids. The animation gives the appearance of an oscillating structure that is punctuated by step 27 due to the abrupt swap of complementary colors.
But returning to the superimposed collections, if we take two of these superimposed collections of same AND type cubes and adjoin the exception cluster of one to the origin cluster of the other, we have adjacent complementary colored clusters. And if we continue to do this, we have a series of stair-steps. But, at any place in the series, we can imagine the last step joining with the first to close the structure.
This is purely working with the complementary colors which stand for the positions within the closed sets. I don't exactly know how the logic would bind the rules represented by the complementary colors so that complementary colored clusters of adjacent clusters would adhere to each other in stair-step fashion. But since the complementary rules combine modulo three sum to one of the identities, it seems that the red and green clusters will bind such that they manifest a signed quantity of 1, and for the blue and orange clusters -1. However, in the case of the yellow and purple clusters, the sum is 0. So it does not appear that they will bind.
As to what occurs within the cubes, one hint with respect to the logic comes from looking at the digit expansions of all like AND types. For example, take the cluster rule numbers for AND which occupy the second position in the 27 closed sets. They happen to be successive powers of 3.
allANDs={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,3486784401,10460353203,31381059609,94143178827,282429536481,847288609443,2541865828329};
All rule numbers except the last are replaced by a red cuboid in their respective graphs. The last rule number is replaced by a green cuboid.
Here are the digit expansions for these rules. They are gathered from each of the boxes in Figure 3., Figure 4., and Figure 5. They do not form a closed set. In fact, when the test for closure is applied, it returns a set of 3331 members, only 27 of which include the original members being tested for closure. 3331 is a prime number.
TableForm[Table[{IntegerDigits[allANDs[[i]],3,27],allANDs[[i]]},{i,27}],TableDirections->{Column,Row,Row},TableAlignments->Left];
We list them with bold font type where they differ. Notice that bold type font identifies an ever increasing power of three as the list progresses.
000000000000000000000000001 1
000000000000000000000000010 3
000000000000000000000000100 9
000000000000000000000001000 27
000000000000000000000010000 81
000000000000000000000100000 243
000000000000000000001000000 729
000000000000000000010000000 2187
000000000000000000100000000 6561
000000000000000001000000000 19683
000000000000000010000000000 59049
000000000000000100000000000 177147
000000000000001000000000000 531441
000000000000010000000000000 1594323
000000000000100000000000000 4782969
000000000001000000000000000 14348907
000000000010000000000000000 43046721
000000000100000000000000000 129140163
000000001000000000000000000 387420489
000000010000000000000000000 1162261467
000000100000000000000000000 3486784401
000001000000000000000000000 10460353203
000010000000000000000000000 31381059609
000100000000000000000000000 94143178827
001000000000000000000000000 282429536481
010000000000000000000000000 847288609443
100000000000000000000000000 2541865828329
The location of the 1 in each digit expansion indicates where the red or green cluster will be in the cube if we stop the series procession of all the displays at any one rule number.
This is analogous to what occurs in quantum systems. When you stop a system by taking its measure, you can know where the particle is. But in so doing you alter the system.
So here we have a system of 27 superimposed cubes. And the cluster is everywhere simultaneously. However when we consider the superposition as a blazingly fast series of possible states for the cluster rule number, we can stop its procession and observe where the cluster is. But in so doing we alter the system.
While the system is a superimposition, it is defined in terms of a cyclic series of powers of three. When it is stopped, it is a particular power of three.
Cellular Automata
All 162 AND type rule numbers belong to class 1. They have simple structure and terminate in a single state. However, there is some variability in the simplicity of the structure. When run with initial conditions of a single black cell, rules 3 and 19683 show chirality, while rule 27 appears as a vertical stripe. At a high resolution rules 1 and 2 have a dotted vertical line superimposed on black and white horizontal stripes, but this detail is lost at more dense resolutions. Rules 38127987424492 and 7625597484984 show a single black triangle. The rest of the rules have all black, gray, or white, or they have horizontal stripes, either black and grey or black and white.
When certain pairs of these 162 rules are combined modulo three sum, their cellular automata advance to class 2. Their behavior shows various types of nested Sierpinski triangular structures. So by combining two of the simple structures of the 162 AND type rules we build up complexity and advance to class 2 behavior.
The quest then becomes: find two of these class 2 nested Sierpinski triangular structures and combine their rules and see if the resulting cellular automaton has random behavior, which would put it in class 3.
It does. See Figure 9.
But what about class 4 behavior? It appears that this is not attainable by combinations of the 162 rules. However, if AND type rules that take two input variables, such as AND[p, q], are combined with the 162 rules that are AND[p, q, r] types, then class 4 CAs can be generated.
Figure 10. is an illustration of this. Notice the familiar result. Rule 3812797148157 generates a cellular automaton that emulates ECA rule 124, the mirror image of the much studied class 4 ECA rule 110.
Ever since Wolfram published the NKS Book I have hoped there would come a time when we could define membership in the cellular automata classes without the necessity of referencing a description based on a visual inspection of the rule's behavior.
It appears that a step has been made in that direction.
We can say that three color, three variable rules that have AND type algebraic descriptions with three variables generate class 1 cellular automata. When certain of these rules are combined modulo three sum they generate class 2 cellular automata. When these class 2 cellular automata are combined modulo three sum they generate a class 3 cellular automaton.
And when the three color, three variable rules that have AND type algebraic descriptions with three variables are combined modulo three sum with those that have only two input variables, it is sometimes possible to generate a class 4 cellular automaton.
But it must be emphasized that repeatedly combining AND type rules with three input variables never goes beyond generating class 3 cellular automata.
It takes combining one AND type with three input variables with one AND type with two input variables to generate class 4 behavior.
ECA Cellular Automata
Whereas there are 162 three color, three variable rules for all possible simple forms of AND, in Boolean logic there are only 16 rules that have three input variables. They are:
1: AND[1+p, 1+q, 1+r]
2: AND[1+p, 1+q, r]
4: AND[1+p, q, 1+r]
8: AND[1+p, q, r]
16: AND[p, 1+q,1+r]
32: AND[p, 1+q, r]
64: AND[p, q, 1+r]
128: AND[p, q, r]
254: 1+AND[1+p, 1+q, 1+r]
253:1+ AND[1+p, 1+q, r]
251: 1+AND[1+p, q, 1+r]
247: 1+AND[1+p, q, r]
239: 1+AND[p, 1+q,1+r]
223: 1+AND[p, 1+q, r]
191: 1+AND[p, q, 1+r]
127: 1+AND[p, q, r]
The reason there are fewer is that there are no signed values in Boolean logic. Also note that NOT[AND] is 1+AND. In three valued logic NOT[AND] is -1+AND.
This is as expected. NOT, or complementation, is defined in terms of the last rule in the list. On page 884 of the NKS book, the last rule listed is 255. It has 1 as its Boolean expression. So 1+AND is NOT[AND] in Boolean logic. But in three valued logic, the last rule has logic expression -1. So -1+AND is NOT[AND] in three valued logic.
Rules for all 16 simple forms of Boolean AND generate class 1 cellular automata. When these class 1 rules are combined modulo two sum they sometimes result in rule numbers that generate class 2 cellular automata. AND when these rules derived from the simple AND type class 1 rules are combined again modulo two sum, they sometimes generate cellular automata with class 3 behavior. Although, the rules doing so may not, perhaps, both be class 2, one of them may be. And neither is one of the original 16 rules.
As an example, rule 2: AND[1+p, 1+q, r] summed modulo two with rule 4: AND[1+p, q, 1+r] results in rule 6.
And rule 1: AND[1+p, 1+q, 1+r] summed modulo two with rule 128: AND[p, q, r] results in rule 129.
Looking at pages 55 and 56 in the NKS Book we see that the CA for rule 6 is a right chiral line and the CA for rule 129 is a nested Sierpinski triangle in negative on a black background. So this is a case where one class 1 and one class 2 rule number will now be combined. But the class 1 rule, rule 6, is not a simple form of AND.
When rules 6 and 129 are combined modulo two sum the result is rule 135, which is just rule 30 with black and white cells interchanged. So we have achieved a breakthrough into class 3 and the random behavior of rule 30.
The import of this is that even with the simple ECAs there is this process or path to take from the 16 simple forms of AND by combining them and recombining them to transition from class 1 to class 2 to class 3 cellular automata behavior.
However, it turns out that the combining only goes three levels deep. After three levels, nothing new is generated. In particular, no class 4 rule is generated.
To get a class 4 rule, AND types with three variables must be combined with either AND[p, q] or AND[q, r].
Hasse Diagrams
The ECA rule numbers form a Boolean lattice. It can be graphically represented by a Hasse diagram. The diagram has rule 0 at the bottom and rule 255 at the top. In between are 9 rows of nodes. Nodes on a row are connected to certain nodes on the row below and above the row to which they belong. The connection expresses "is a subset of" or "is not a subset of".
Now it just happens to be that the digit expansion of an ECA rule number indicates on which row of nodes the rule number is to be found. All rules whose digit expansions have the same number of 1 digits will reside on the same row. At the bottom is rule 0 with no 1 digits. On row 1, just above rule 0, are all the rules with a single 1 digit. Next, a row in which each node's digit expansion has two 1 digits. And so forth until rule 255 which has all 1 digits in its expansion. When the nodes on each row are numbered from greatest rule number to least, from left to right, the Hasse diagram is ready for the nodes to be connected according to the rule "is a subset of" or "is not a subset of".
But what we want to observe stops short of assigning the connections between nodes.
It turns out that cellular automatons at row 1 and row 9 are all class 1. So are those on rows 2 and 8. On row 3 and 7 some class 2 are introduced. On rows 4 and 6 there is a surprise. Class 4 is introduced and there is no class 3 present. The class 3 rules all show up on row 5.
This suggests either (1) that complexity does not grow greater with row number or (2) that class 4 should be placed before class 3. I believe Tony Smith from Australia argued something to this effect soon after the Forum was set up.
One final observation. On each row there are many rules belonging to classes introduced on previous rows. (Previous as you move from top and bottom toward the center.) Might it be that with carefully selected initial conditions, all nodes on a row will achieve the highest class shown on that row? One hint of this is rule 22 which appears as a class 2 rule on row 4 which contains class 4 rules. In the NKS Book on page 951, Wolfram shows that it is capable of rising to class 3's random behavior, given the right initial conditions. So there is precedent for these rules to change classes of behavior. However, in this case the rule surpasses the highest class introduced on row 4, which is class 4. Again the ambiguity of where class 4 belongs.
Conclusions
Nine major conclusions stand out from this presentation:
(1) Algebraic expressions that have the same rule number are equivalent.
(2) Rule numbers and algebraic expressions stand in a one to many relation with each other.
(3) Rule numbers have a kind of multiplicative inverse even though there is no operator for modulo three division.
(4) All possible types of AND and the three variables together with the three identities form 27 closed sets each with nine members.
(5) These sets can be used to generate ternary Cartesian product projections using each AND type rule as operator for the projection. Rule numbers resulting from these projections come in inverse pairs and can be represented by colors. The projections have clusters that occupy one of 27 positions on a cube with dimensions 27 x 27 x 27 cells.
(6) The color substitutions allow for comparisons among the closed sets based on sequential order of rule numbers within a set.
(7) There is one exception to observation (6). AND types with variables {-p, -q, -r} break the sequential order. This exception suggests something analogous to valence orbits in chemistry.
(8) All 162 rules manifest class 1 cellular automaton behavior. Certain pairs of these rules, combined modulo three sum, generate class 2 cellular automata. Two of these class 2 cellular automata rules when combined modulo three sum generate a class 3 cellular automaton. This suggests that explanatory definitions of the cellular automata classes may be achievable.
(9) Both Hasse diagrams and re-combinations of the simple AND types suggest that the order of cellular automata classes might need to be updated to properly place class 4 behavior.
Last edited by Lawrence J. Thaden on 09-24-2010 at 05:22 PM
Report this post to a moderator | IP: Logged
|
09-18-2010 03:59 AM
Attachment: 
