[21 Three Color Palindromic Rules] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
21 Three Color Palindromic Rules
(Click here to view the original thread with full colors/images)
Posted by: Lawrence J. Thaden
Figure 1 in the attachment lists 21 three color rules together with their digit expansions and logic expressions.
Notice that the digit expansions are palindromes. They read the same from left to right and right to left.
Primitives
At first glance the logic expressions look complicated. But on closer inspection they are seen as composed of three primitives and three identities. There are two AND type primitives and one OR type.
In parallel fashion there are two multiplicative type identities and one additive.
The first multiplicative type identity is negative multiplicative identity. Its digit expansion is a row of 2s. Its symbol is given correctly in the figure as e subscripted -1. In this post to the Forum we will settle for (e-1).
The second multiplicative type identity is positive multiplicative identity. Its digit expansion is a row of 1s. Its symbol is given correctly in the figure as e subscripted +1. In this post to the Forum we will settle for (e+1).
The single type of additive identity has as digit expansion a row of 0s. Its symbol is given correctly in the figure as e subscripted 0. In this post to the Forum we will settle for e0.
The first AND type primitive is nAND. This is not Boolean NAND. Rather it is the self-similar rule that results from applying the three color AND rule to negative values of variables p, q, and r.
Correspondingly, pAND is the rule that results from applying the three color AND rule to positive values of variables p, q, and r.
Note that pAND and the three identities are the only primitives that stand alone as rules by themselves. All of the other rules are composites of two or more primitives.
There is just one OR primitive. The reason is that the three color rule for OR does not “see” the signs of the variables. So applying the rule for OR has the same result whether the input variables are signed or not.
However, OR never appears as itself. It always presents in lattice complement form as (e-1) - OR. In this form it is actually three color Boolean NOR.
Moreover, (e-1) - OR never appears as a singleton. It is always enclosed and inaccessible within a doublet or triplet or some complemented form of a doublet or triplet.
Complemented forms of the expressions are with respect to the identities and are the modulo 3 difference between an identity and the expression. In some cases complementation is nested.
Note that the primitives pAND, nAND, and OR have no explicit variables. The implication is that pAND has variables p, q, and r associated with it. And nAND has -p, -q, and -r associated with it, while OR takes the absolute values of the variables p, q, and r.
Rule Properties
Here are some observations on the rules:
(1) No digit expansion of any one rule contains all three colors. The identity rules have only one color. All the remaining rules have only two colors. Either {0, 1}, or {0, 2}, or {1, 2}.
(2) Each of the rules can be mapped into another one of the rules using a mapping function defined elsewhere on the Forum.
(3) The rule: nAND + ((e-1) - OR) is called a doublet. It appears in complemented and nested complemented forms. It is the modulo 3 sum of its terms, and the second term is modulo 3 difference of its terms. The terms in this rule are not directly accessible to the mapping function. Nor are modulo 3 sum and difference directly accessible.
(4) The rule: nAND + pAND + ((e-1) - OR) is called a triplet. It appears in complemented and nested complemented forms. It is the modulo 3 sum of its terms, and the third term is modulo 3 difference of its terms. The terms in this rule are not directly accessible to the mapping function. Nor are modulo 3 sum and difference directly accessible.
(5) The set of 21 rules is closed under the mapping function in the following sense: No result of any possible mapping of any rule with its operand rules can result in anything but one of the 21 rules.
(6) This set of 21 rules is a complemented set in the sense that pair wise modulo 3 sums of the digit expansions of the rules and the rules taken in reverse order results in 21 occurrences of the digit expansion of (e-1): Negative Multiplicative Identity.
(7) The terms in the logic expressions are functions as opposed to functions with data. For example, nAND in another context might be taken as (-p nAND -q nAND -r). But here it is considered as the function irrespective of what data might be input to it.
(8) This set of 21 rules is formed by selecting just the palindromic rules from three separate sets of 16 rules. And each of these sets of 16 rules follow observations similar to those listed for the 21 palindromic rules. In fact, the digit expansions of the first set of 16 rules is limited to {0, 1, {0, 1}}. The second set is limited to {0, 2, {0, 2}}. And the third set is limited to {1, 2, {1, 2}}. When all three sets of 16 rules are combined they form a closed set of 45 rules which follow the observations above. (See Figures 3a, 3b, and 3c.)
(9) Another set of 21 rules can be formed by selecting from the above three sets of 16 rules. They form a set that is based on three color Boolean AND, OR, and the identities. There is only one type of AND, nAND. So, pAND does not occur in this set. (See Figure 2.)
Posted by: Lawrence J. Thaden
Figure 4 lists the 21 palindromic cellular automata. It also labels each cellular automaton with the rule number and logic expression used to generate it. Initial conditions are the same for all 21 cellular automata. Namely, the set of 21 palindromes. The cells in the cellular automata are not single three color digits, Rather, they are the complete rule numbers. To evolve this type of cellular automaton, the CellularAutomaton command was not used. Instead code borrowed from the Forum was modified as follows:
EvolveCA[init_List, rule_, maxsteps_Integer]: = Module[{ },
NestList[UpdateCA[#, rule]&, init, maxsteps]]
UpdateCA[list_List, rulenumber_]: = Module[{t, uc},
t = Flatten[{Take[list, -1], list, Take[list, 1]}];
t = Partition[t, 3,1];
uc = Table[map[rulenumber, t[[i, 1]], t[[i, 2]], t[[i, 3]] ], {i, Length[t]}];
Return[uc]]
Rule Equivalences
As with the ECAs (see page 883 of the NKS Book), there are rule equivalences within the set of 21 three color palindromic rules. That is, while the overall CA structure for a pair of equivalent rules is the same, the colors of the cells differ. See Figure 5 for a list of replacement rules required to equate these pairs of palindromic CAs which have the same structure.
Note that the equivalences apply to the part of the CAs after initial startup which can be anywhere from 0 to 5 steps. It takes the rule that long to normalize the initial conditions which are all of the palindromes. After startup only those rules remain that are listed in the replacement rules.
Relevance to NKS
On page 884 of the NKS Book Wolfram lists the logic expressions for ECA rules. While it is not feasible to list all 7625597484987 logic expressions for three color rules, listing this core subset of rules is a small beginning.
Stating the rules in terms of modulo 3 differences between three identities and logic expressions for AND and OR brings the set of three color rules into the neighborhood of algebra with all of its history and power of expression.
Identification of these sets closed under the map function is valuable. It supports further study that is ordered and predictable. For example, you can explore how each of the three sets of 16 rules interacts with the guarantee that no result will be outside the “system”.
The existence of so-called doublets and triplets whose components are inaccessible might be leveraged in modeling processes that involve encapsulation. Perhaps spintronics or any of a number of biological disciplines.
Understanding the three valued rules as an extension of traditional Boolean logic is key to extending today’s electronic industry applications to tomorrow’s needs. Identification of two AND operations and one OR operation and the two types of multiplicative identity that characterize this three valued logic sets the direction for discovery of a multitude of useful processes.
Posted by: Lawrence J. Thaden
After initial conditions, there is never a digit in a cell's digit expansion that is not in the digit expansion of the rule. The converse is true as well. For example, the CA cells for rule 2541865828330: nAND + ((e-1) - or), as well as the rule itself, have digit expansions that only include the digits 0 and 1.
It would be interesting to hear from the Forum members if this is peculiar to these 21 palindromic rule CAs, or if it is the general case that no three color CA can have any digit that is not in the digit expansion of its rule.
Posted by: Lawrence J. Thaden
Figure 6 lists 12 members of the closed set of 45 rules.
Four rules are taken from each of the three sets of 16 rules in Figures 3.
The rules take from each of these three sets are the fourth, sixth, eleventh, and thirteenth.
They do not form a closed set by themselves or even with the 3 identities. But they generate all 45 rules.
This can be demonstrated with code like:
Union[Flatten[Table[map[fifteenRules[[h]], fifteenRules[[i]], fifteenRules[[j]], fifteenRules[[k]]],{h,15},{i,15},{j,15},{k,15}]]] == fortyFiveRules
True
Notice that their digit expansions all have the same pattern: while there are only two different digits per rule, the end digit and the center digits are the same and all the rest are the other digit. Six of the end digits are on the left and six are on the right.
Posted by: Lawrence J. Thaden
Figure 7 in the attachment lists all 45 rules discussed as separate subsets in the previous posts.
Notice that most of the rules are the modulo 3 difference of one of the identities and some logic expression. In another context this is referred to as the algebraic inversion of the expression with respect to an identity.
There is another relevant context that discusses inversion. In binary logic circuit design an inverter turns a 0 signal into a 1 and conversely a 1 signal to a 0. It is also referred to as logical NOT. And in algebraic literature it is called the lattice complement.
Moreover, where early Boolean logic textbooks presented x as {0, 0, 1, 1}, NOT[x] was presented as each of the digits inverted: {1, 1, 0, 0}.
(Perhaps textbooks after Wolfram’s NKS book will rearrange this, consistent with his example on page 884 that puts NOT[p] at the beginning of the list.)
However, with Wolfram’s three color rules you cannot get a result for NOT[x] by using a binary logic inverter. Rather, this is accomplished by modulo 3 difference of the identity (-1) and x.
So, is the logic inverter dead when it comes to the logic of three color rules?
Surprisingly, no. In fact it takes on a more sophisticated service. Instead of inverting a signal 0 to a 1, it changes input p to q. And nested, it then changes the q to r. And finally the r back to p. Likewise, it changes -p to -q to -r to -p. And by the substitution principle, any p to q to r.
Mathematica code for this is a digit expansion coefficient indexing of three color rules:
rotate120[threeColorRule_]: = Module[{rNum},
rNum = threeColorRule;
Return[FromDigits[IntegerDigits[rNum, 3, 27] [[{
1, 4, 7, 10, 13, 16, 19, 22, 25,
2, 5, 8, 11, 14, 17, 20, 23, 26,
3, 6, 9, 12, 15, 18, 21, 24, 27}]], 3]]]
The name “rotate120” is used to differentiate this function from the binary logical inverter function. Its name emphasizes its expanded application and points to its effect on the intrinsic orientation of the digits in a three color rule. Think of it as analogous to geometric rotations by degrees.
How does this apply to the 45 rules?
It doesn’t. The digits of these 45 rules are immune to “rotation by 120 degrees”. That is, when digits of any of the 45 rules are indexed as specified in “rotate120”, the result is identical to the digits before indexing.
And, curiously, if you inspect any of the 45 rule expressions, you will find that none explicitly contains any variable: {p, q, r, -p, -q, -r}.
Does this mean that “rotate120” can be used as a touchstone for determining if a three color rule is like one of these 45 rules or is associated with the variables?
For example, rule 3188647 is not among the 45 rules and it is immune to “rotation by 120 degrees”. If you look at its logic expression, you do not see any explicit variables: ((e -1) - OR) - pAND.
On the other hand rule 146430861993: (-p + q) has a logic expression based on the variables and it does “rotate”:
146430861993: (-p + q) ->
1616787841929: (-q + r) ->
2053105087449: (-r + p) ->
146430861993: (-p + q), and so forth.
It is a good question. Perhaps “rotation by 120 degrees” is a touchstone function. And if it is, it might have far reaching implications. For starters, it might partition three space. And if it does, how many rules will be in each partition?
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings