[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?
Posted by: Lawrence J. Thaden
Motivation for exploring these 21 rules using the phased approach, introduced when considering a set of 27 rules referred to as t5, stems from a desire to further explore the behavior of AND and OR, fundamental operations in logic and computer circuits.
Unlike with operation modulo 3 sum and difference, operations presented here with AND and OR offer less variety in their cellular automata behavior. There are only two types of structure, using the phased approach. The first type has two phases. The one is an original phase with either vertical lines or initial rows with variously sized triangles. This is followed by a phase with no variation in structure. The other type is an original phase with a left and right symmetrical structure. The left or right is similar to ECA 30 in that it appears to be random. When the next phases are generated, the symmetry is lost but the random appearance is retained.
However, note that the next phases are generated from just the beginning of the original phases. I have yet to determine where the cycle begins and ends for these rules. In the attached graphs only 567 rows of the original phases are included. This holds true for both types of structure. Figure 1 graphs the first type. Figure 2 graphs the second type.
Furthermore, the symmetric and random structures of the second type rule are related. If the initial conditions are discounted -- since they are always the same-- the following rules are related as specified below. First there are three groups of three equivalencies provided cell content types are swapped according to indicated rules.
(4) 1270931319840: e1[mAND+pAND+NOR] =
(9) 2541867422653: mAND+pAND+NOR by swapping 0s and 1s.
(4) 1270931319840: e1[mAND+pAND+NOR] =
(18) 6354666165146: e2[e1[mAND+pAND+NOR]] by swapping 0s and 2s.
(4) 1270931319840: e1[mAND+pAND+NOR] =
(6) 2541862639680: e2[e0[mAND+pAND+NOR]] by swapping 1s and 2s.
(13) 5083730062333: e2[mAND+pAND+NOR] =
(6) 2541862639680: e2[e0[mAND+pAND+NOR]] by swapping 0s and 1s.
(13) 5083730062333: e2[mAND+pAND+NOR] =
(9) 2541867422653: mAND+pAND+NOR by swapping 0s and 2s.
(13) 5083730062333: e2[mAND+pAND+NOR] =
(18) 6354666165146: e2[e1[mAND+pAND+NOR]] by swapping 1s and 2s.
(16) 5083734845306: e0[mAND+pAND+NOR] =
(18) 6354666165146: e2[e1[mAND+pAND+NOR]] by swapping 0s and 1s.
(16) 5083734845306: e0[mAND+pAND+NOR] =
(6) 2541862639680: e2[e0[mAND+pAND+NOR]] by swapping 0s and 2s.
(16) 5083734845306: e0[mAND+pAND+NOR] =
(9) 2541867422653: mAND+pAND+NOR by swapping 1s and 2s.
Next there is a single pair of rules that are equivalent provided cell contents are swapped according to indicated rules. This pair is easily distinguished from the above pairs by observing the graphs of the figures. The center triangle at the top of each figure is larger than the triangles of the figures for the above pairs of rules. Nonetheless, the structures are symmetrically random on the original phase and then random but not symmetrical on the following phases.
(15) 5083731656660: e0[mAND+NOR] =
(7) 2541865828326: e2[e0[mAND+NOR]] by swapping 0s and 2s.
But the definition of random again comes into question. How can several structures be called random when by a simple substitution of cell values one rule generates behavior equivalent to another?
Posted by: Lawrence J. Thaden
Six of the eight rules that generate CAs that are symmetrical and appear to have random patterns actually have the same cycle length. In each case it is 448 rows long and begins at row 591. I used code written by Jason Cawley and Jesse Nochella called period[ ] to locate these cycles.
Figure 1 shows a typical example. It is for rule (13) 5083730062333: e2[mAND+pAND+NOR]. Notice that the background of the figure is the startup portion consisting of 590 rows. If you look closely at the top of the figure, you can spot the presence of 0 content in the cells as red lines. This is the only time 0s appear as content, as was mentioned earlier in this thread. It is because the digit expansion of the 21 rules, in reverse order, are used for initial conditions. Because the digit expansion of rule (13) 5083730062333: e2[mAND+pAND+NOR] contains no 0s, no 0s are found in the cells of the cellular automaton after the initial conditions.
In the foreground of Figure 1 the cycle of 448 rows is presented as a torus. As said, this is a typical example for the set of six rules. The other two rules that have a random symmetrical appearance but do not cycle as soon as these six rules are (7) 2541865828326: e2[e0[mAND+NOR]] and (15) 5083731656660: e0[mAND+NOR].
In fact, I have yet to determine the startup and cycle length for these two rules. It just may be that they are like ECA 30 in that they go on and on for an indefinite time. I tried using period[ ] on two million rows but gave up after four days of processing for fear that paging might eventually damage my hard drive. If anyone on the Forum has ideas on how such a cycle can be found on a desktop computer, please post.
In any case, taking additional phases for these six rules presents random but not symmetrical results that appear to go on and on indefinitely. I have not been able to identify any cycles for these additional phases.
For convenience, here are the six rules:
(4) 1270931319840: e1[mAND+pAND+NOR]
(6) 2541862639680: e2[e0[mAND+pAND+NOR]]
(9) 2541867422653: mAND+pAND+NOR
(13) 5083730062333: e2[mAND+pAND+NOR]
(16) 5083734845306: e0[mAND+pAND+NOR]
(18) 6354666165146: e2[e1[mAND+pAND+NOR]]
After analyzing the logic expressions, one might have thought that (4), (13), and (18) would have similar structure. Likewise, (9), (16), and (6) seem to go together. But as the code period[ ] revealed, all have the same startup length and cycle length.
Forum Sponsored by Wolfram Research
© 2004-2013 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