Registered: Jan 2004
Posts: 350

Introduction

Figure 1 lists a set of 27 three-color rules that correspond to algebraic expressions for a ternary logic in two variables:

T5 = ({0, +1, y, z, -1}; +, -; 0, +1, -1)

Where the operations, + and -, are modulo 3 sum and difference and
Where the three identities are,

0: additive identity
+1: positive multiplicative identity and
-1: negative multiplicative identity.

T5 is a closed set. It is an example of a nondegenerate, complemented, distributive lattice.

These algebraic expressions can be entered in Mathematica and will perform T5 ternary logic operations provided they are specified along with a set of rules to ensure absorptive and modulo properties are preserved.

For example, if the list of algebraic expressions are assigned to the symbol t5, a list of the results for modulo 3 plus: y[[i]] + z[[i]] for all i in t5 can be generated with rules:
{2 -> -1, -2 -> 1, 2 y -> -y, 2 z -> -z}.

Moreover, the results correspond to those obtained by use of the map function described in these posts.

Of course, the map function results in rule numbers, not algebraic expressions.

However, there is a correspondence. It is found between the mapped rule number result and the position it holds in the list of algebraic expressions.

So, if the set of rule numbers are assigned to the symbol t5Subset, and the expressions are assigned to t5, executing the following code in Mathematica gives {True}.

Union[(Table[(t5[[i]] + t5[[#]]&/@Range[Length[t5]]/.{2->-1, -2->1, 2 y->-y, 2 z->-z}) == (t5[[#]]&/@(Flatten[Position[t5Subset, #]&/@(map[t5Subset[[10]], dontcare,  t5Subset[[i]], t5Subset[[#]]]&/@Range[Length[t5Subset]])])), {i, Length[t5]}])]

Where t5Subset[[10]] identifies the rule corresponding to the algebraic expression (-y) + (-z).

Similar tests can be constructed for correspondence between three-valued rule numbers and other simple algebraic expressions that are modulo 3 sums and differences.


Expectations Finally Fulfilled

Towards the end of the thread titled “(-x +z) Self Organization Example”, which discussed (at length) the rules and CAs from T5 for x and z, I said:

“I am going to leave this for now and go back to correct the thread for T5 for x and y, in which I failed to reverse the initial conditions. I am anticipating finding some very simple cycles of phases that are analogous to the spinor. The ones found so far have been with very many phases. But T5 for x and y might have some that have just a few phases.”

Well I have made those corrections and posted them in the threads: “Revised T5 = ({0, +1, x, y, -1}; +, -; 0, +1, -1)” Parts 1 – 4.

However, there were no rules with “spinor-like” behavior.

But now with the last set of T5 rules for y and z, we hit pay dirt. There are two rules with cycles of phases that have “spinor-like” behavior within the first nine of twenty-seven rules. And as anticipated, they have short cycles of phases. One has six phases and the other eight phases. Both begin geometrically as tubular objects with a lip at the bottom.

But where the earlier ones in T5 for x and z were self-organizing, these for the most part are arrangements of Sierpinski triangles. So they will not be able to shed any light on how the self-organizing ones come about, as I had hoped they would.


Rules and Their Behavior

So to begin this discussion lets consider these two spinor-like rules.

Rule (6) 1616787841929: (-y + z) has six phases which make up its cycle. The first three have positive polarity and the last three have negative polarity. One to one the first three are identical in all respects to the last three, save for polarity. Wherever there is a cell with a 1 in the first three, the corresponding cell in the last three is a 2, which algebraically behaves as a –1.

This is easily shown by Mathematica code that sums corresponding cellular automaton outputs modulo 3. Whenever the pair consists of polar opposites, the result is all zeros. Here is an example of the code that might be used:

Union[Flatten[Mod[polarPositive[[n]] + polarNegative[[n]], 3]]]

{0}

The cycle is spinor-like in that its phase changes can be compared to a spinor that takes 4 Pi radians to complete a cycle and which after 2 Pi radians changes polarity. Following this comparison, each phase corresponds to a discrete advance of (2/3) Pi radians.

The structure of the first and fourth phases is arrangements of Sierpinski triangles. The structure of the second and fifth phases is an additive version of three sets of Sierpinski triangles. The structure of the third and sixth phases shifts two of those sets down and slightly to the right, while shifting the third fully 50 percent to the left and slightly down. At the same time there appears an additional set of Sierpinski triangles along the left edge. Whether these come from the previous phase or are something knew is hard to determine. If they originate from the previous phase, it might have something to do with modulo 3 sum and difference canceling things out, and with periodic boundaries.

If you accept the concept that the phases alternate as outside and inside surfaces of the tube, then all you could observe is phases 1, 3, and 5. (See Figure 7.)


Rule (8) 2100313177833: (y - z) has eight phases which make up its cycle. The first four have positive polarity and the last four have negative polarity. One to one the first four are identical in all respects to the last four, save for polarity. Wherever there is a cell with a 1 in the first four, the corresponding cell in the last four is a 2, which algebraically behaves as a –1.

The cycle is spinor-like in that its phase changes can be compared to a spinor that takes 4 Pi radians to complete a cycle and which after 2 Pi radians changes polarity. Following this comparison, each phase corresponds to a discrete advance of (1/2) Pi radians.

The structure of the first and fifth phases is arrangements of Sierpinski triangles. The structure of the third and seventh phases is an additive version of three sets of Sierpinski triangles, very similar in appearance to the third and sixth phases for rule (6) 1616787841929: (-y + z), except that the bottom edge does not touch the frame. Rather there are several rows with 0 content before the bottom frame.

The structure of the second and sixth phases is similar to that of phases two and five for rule (6) 1616787841929: (-y + z), with two exceptions noted:

(1) the additive triangles on the right touch the bottom frame, and
(2) Sierpinski “cut outs” for the additive triangles on the right are not 0s. Rather they are a combination of 1s and 2s.

But for phases four and eight Sierpinski is left behind. These phases resemble phase three of rules (6) 146430861993: (-x + y), (16) 3943560596989: (1 – x + y), and (20) 7348404768497: (-1 – x + y), all belonging to T5 in x and y.

But these phases for T5 in y and z have a different orientation than the three just referred to. The center diagonal in these two begins in the upper left corner and descends halfway down the figures. In the three others, it begins in the upper right corner. (See Figure 9 for these phases, but click here to see the comparable phases in figure 4 of the presentation for T5 in x and y. Also note that the figure for rule (20) 7348404768497: (-1 – x + y) is mislabeled “Phase 2”. It should be labeled “Phase 3”.)

If you accept the concept that the phases alternate as outside and inside surfaces of the tube, then all you could observe is phases 1, 3, 5, and 7.

I should think that it would be quite an achievement for someone to be able to explain the derivation of phases four and eight of rule (8) 2100313177833: (y - z). It might be done in the same terms that are used to explain how the Sierpinski triangle is constructed, including Hausdorff dimensions of the various regions. This assumes that the complex pattern can be broken down into regions that at sometimes intersect and at other times cancel out modulo 3.


Besides these two spinor-like rules, there are two other remarkable rules in the first nine rules for T5 in y and z. These are the self-replicating rules (4) 1466461054805: (-1 + z) and (9) 2201047622813: (-1 – y – z). Both begin as tori with 1458 rows and 729 columns.

Rule (4) 1466461054805: (-1 + z) has three phases, the second and third of which make up the cycle. All three phases have stripes running from the upper right corner to the lower left corner. The original phase is replicated in a side-by-side double copy in phase three. The second and third phases mirror each other diagonally. That is, if you place one to the right and above of the other, they reflect each other. (See Figure 5a and 5b.)

Also, since the cycle begins with phase 2, this is the outside surface of the torus. So the self-replicating phase occurs on the inside surface of the torus.

This self-replicating is dependent upon letting phase 2 run for 1458 rows. Actually, phase 2 will cycle after 729 rows. So you really have odd phases with dimensions: 1458 rows and 729 columns and even phases with dimensions of 729 rows and 1458 columns. And there is no self-replication. The length of the rows and columns just keep alternating. And it cycles after the second phase. In this scenario the original phase is the outside surface of the torus.

This dependence upon some external control to let phase 2 cycle twice in order to meet the requirements for self-replicating in phase 3 is just one of the two dependencies on external controls to achieve self-replication. The other is a mechanism for separating the right and left halves of phase 3 so that they stand on their own.


Rule (9) 2201047622813: (-1 – y – z) has thirteen phases and the last phase is a side-by-side double copy of the first phase. However, its cycle runs from phase two through phase thirteen. Instead of stripes running diagonally from upper right to lower left, there are rows of green triangles, and these appear only in the original phase, phase five, phase nine, and phase thirteen.

Moreover, in phases 5 and 9 the image appears to have been rotated clockwise 90 degrees. And each of the phases also has intersecting rows of purple triangles that impart to the images a lattice-like structure.

The intervening phases are characterized by Sierpinski triangle structures, some with green “cut outs” and some with purple. And, as was said, the thirteenth phase replicates the original in a side-by-side double copy. (See Figures 10a and 10b.)

Again, achieving replication is by externally controlling phase 2 so that it runs out to 1458 rows. If no control were exercised, the second phase would have stopped at row 248, a row with every cell a 1. And then continuing on to the subsequent phases would present a bewildering variety of dimensions that would not readily result in the self-replication. For example, by phase three the dimensions are 248 columns by something in excess of 50000 rows.

At first glance phases (3 and 11), (5 and 9), and (8 and 12) appear to be the same. But this is an illusion. Moreover, phase 5 is not the original replicated side-by-side in a 90 degree rotation of itself. If you do take half of phase 5 and rotate it counter clockwise 90 degrees and then animate it with the original, you will notice that the small green triangles in the vicinity of intersections of the larger green and purple triangles scintillate.

This rule is interesting because its cycle starts with phase 2. If you accept the concept that the phases alternate on the outside and inside of the surface of the torus, this means that for this rule only even phases are observable. And the self-replication would take place on the inside surface of the torus.


Remaining Rules

Now lets sequentially consider each of the remaining first nine rules for T5 in y and z.
The first one is the additive identity 0 and needs no explanation.

Next is rule (2) 146064945221: (-1 + y) which has two phases, the second of which cycles on itself. The color is purple because it is made up of evenly distributed cells with 0s (red) and 2s (blue). These cells form a checkerboard pattern, beginning with a red cell in row one and repeating every odd integer row number. The original phase has an alternating pattern of vertical bars, which repeats with each odd integer row number. At first glance the left and right halves appear to mirror each other, but this is an illusion. So both phases are very small tori, but we run them out to 729 rows. (See Figure 3.)

Rule (3) 277019723695: (1 - y) also has two phases, the second of which cycles on itself. Both phases appear gray because of the even distribution of all three types of their cell values. The original and phase 2 both repeat every three rows. The original has a vertical bar appearance. At first glance it looks like the left and right sides reflect each other, but they do not. The second phase has repeating diagonal rows of blue, red, and green cells. So both phases are very small tori, but we run them out to 729 rows. (See Figure 4.)

Rule (5) 1576494063937: (1 + y + z) has three phases and it cycles through all three phases. Each phase has a rich texture but at low resolution appears grayish due to the even distribution of its three colors. The phases all present a diagonal of triangles running from lower right to upper left, with each phase a variation on the filler for the triangular shapes. The original phase has horizontal stripes for filler. Phase three has vertical stripes. And phase two has a combination or blend of the horizontal and vertical that gives it a checkered appearance. In addition there are olive green and purple triangles interspersed about the central diagonal triangles. And this feature becomes more pronounced in each phase until phase three has the hint of a lattice-like appearance. Each of the phases is a torus with 729 rows. (See Figure 6a for the three phases and Figure 6b for close-up views of the diagonal pattern.)

If you accept the concept that these phases alternate between the outside and inside surface of a torus, then this rule is indeed interesting, since its cycle ends up with the last phase an outside surface.

This means that the next iteration of the cycle of phases begins on the inside surface of the torus. So its cycle starting points alternate in a trinary fashion. Viewed from the outside, the surface of the torus would appear to change its phases from 1 to 3 to 2 to 1 to 3 to 2 ad infinitum.

If this alternating cycle of phases is found to manifest itself in any physical process, I should think detecting it would be very obvious.

In the process of preparing graphics for the three phases I considered making them as “painted” tori, the paint being the 729 rows by 729 columns of cell values converted to RGBColor specifications. However, my computer was not able to process all the graphic data.

So, undaunted, I attempted to extract cell values from every third row and column, thus yielding a subset of cells from rows and columns 1, 4, 7, 10, and so on. The result was three tori with dimensions of 243 rows and columns.

This, my graphics card was able to process. But the image for each phase was very different. And the way in which the differences appeared was unexpected.

The purple and olive colors are gone and only the pure red, green, and blue colors are to be seen. Moreover, each phase has a similar structure, although the phases differ in color arrangements.

There is a center diagonal of modified triangular shapes made of triangles that changes color with each phase. In the original phase it is blue; in phase 2 it is green; and in phase 3 it is red.

In addition, there are three rows of three regions of same colored clusters of triangles. (These clusters include the center diagonals referred to above.) The pattern of colors runs over the regions as follows:

..............................Cell Colors…………Cell Values
Original phase: Blue...green...red.…….....2, 1, 0
………………..........Red….blue…green…….....0, 2, 1
…………….........…Green..red…..blue..……....1, 0, 2

Phase 2:………...Red..…blue.…green.….....0, 2, 1
………………........Green…red..…blue….........1, 0, 2
…………….….......Blue....green....red..….…...2, 1, 0

Phase 3:………..Green…red.….blue.…….....1, 0, 2
……………….........Blue….green...red………....2, 1, 0
…………….…........Red..…blue.....green..…...0, 2, 1

Finally, there is a structural symmetry about the diagonals. The same structure, if not color, is found on either side of the diagonals for all three phases. (See Figure 6c.)

It is remarkable how this symmetry is hidden in every 3rd row and column of the original versions for this rule. It is certainly there in the originals. Only it is disguised by the other detail.

Well I was able to paint tori with these extracted versions of rule (5) and also to ListAnimate them. However it took a long time before the animation started. But when it did, it was clear that the three abstracted phases have the exact same structure. Only the colors change during the animation. (I am not including the set of graphic figures for these extracted tori.)

But where did the olive and purple colors go? They are in complements of these extracted phases. And it takes 486 rows and columns to construct tori from them. (See Figure 6d.)

One is tempted to conjecture about subsets of cells that make up a torus, since in this case the two extracted subsets of the original cellular automaton data are also tori, although of different dimensions.

The conjecture would be stated this way: Given cellular automaton output from a rule with periodic boundaries that cycles, subsets of the cycle data also cycle, but not necessarily with the same number of rows and columns.

There would have to be certain constraints such as that the cellular automaton must be 1d with dimensions (n x n) in order to follow from this example.

But I merely throw out the suggestion. I am not making the conjecture. All I can state is that there is one cellular automaton that meets these criteria.


Rule (7) 2053045476727: (1 - z) has two phases and it cycles through these two phases. The appearance is grayish because of the even distribution of cell values. Both phases consist of diagonal stripes running from the upper right to lower left. The two phases are diagonally mirrored. That is, if you place one above and to the side of the other, the two reflect each other. Both phases are tori with 729 rows. (See Figure 8a for the two phases and Figure 8b for close-up views of the original phase.)

Attached are figures 1 - 5 which include the list of rules and figures for the first five rules.

Two subsequent posts will have attachments for the rest of the rules.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 02-06-2009 at 02:50 AM

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Attached are figures for rules numbered (6) - (8).

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Attached is the figure for the rule numbered (9).

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Decomposition and Recombination of Three-Valued CA Output

There is an interesting “trick” for decomposing complex cellular automata generated with three-color rules. It makes two simpler two-color outputs from the three-color rule output, which can be examined separately.

All you do is apply a three-color rule for OR to each of the cells in the three-color cellular automaton output with itself for one of the simpler outputs.

Then you apply a three-color rule for AND to each of the cells in the three-color cellular automaton output with itself for the other simpler output.

These two newly generated cellular automata outputs are simpler because they only contain two cell types, not three, as does their source. That is, they are binary representations of the three-color cellular automaton.

Then to recombine the two separate simpler ones and reacquire the original, just modulo 3 sum the cells of the two simpler ones.

I thought at first that this might hold out promise for compression routines. But existing compression routines that I tried never achieved byte counts for the total of the two simpler ones that were less than the byte count of their source.

At least it is a neat way to show the relation between OR, AND, and modulo 3 sum in three-color rules.

And it might also serve a purpose as an encryption technique. If I had one of the simple copies and you sent me the other copy, I could combine them to get the unencrypted copy of the message.

Attached is a notebook with two examples.

Attachment: decompose and recombine ca example.nb
This has been downloaded 726 time(s).

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Decomposition and Recombination of Three-Valued CA Output by Means of Modulo 3 Difference

The last post presented a way to decompose and then recombine a three-valued cellular automaton output. Simply OR the original CA output with itself for one half of the decomposition and then AND the original CA output with itself for the other half of the decomposition. These two halves become two-valued objects, dropping one of the three values. And one of the two values has twice as many occurrences as the other. To recombine them into the original, sum them modulo 3.

The three-valued rule used for ORing the original with itself is the rule that performs y OR z. Namely, rule 3812411302320. The three-valued rule used for ANDing the original with itself is the rule that performs y AND z. Namely, rule 2541994975053. These two decomposition operations are carried out by means of the map function. Recombining these two is accomplished by summing the two parts modulo 3 with Mathematicas MOD statement.

But now we introduce two other rules to take the place of OR and AND. When they are applied to the original three-valued cellular automaton output, they generate two parts of a decomposition of the original CA that also have only two values. However these values are not from the pool of possible rules taken from the original CA, which are the first three rules in the system of three-valued logic for three variables. Rather they are taken from the last three rules in the system of three-valued logic for three variables. But, in contrast to the previous post, to recombine these two parts of the decomposition, you find their difference modulo 3, not their sum.

The first of these two rules is 7562832176960. Instead of y ~OR~ z, it has the logical expression: positive multiplicative complement of the negative value of y ~additive inverse of OR~ positive multiplicative complement of the negative value of z.

This rule has the equivalent logical expression: negative multiplicative complement of the positive value of y ~additive inverse of OR~ negative multiplicative complement of the positive value of z.

Likewise, instead of y ~AND~ z, the second rule, 2541607534880, has the logical expression: positive multiplicative complement of the positive value of y ~additive inverse of OR~ positive multiplicative complement of the positive value of z.

Similarly, this rule has an equivalent logical expression: negative multiplicative complement of the negative value of y ~additive inverse of OR~ negative multiplicative complement of the negative value of z.

Notice that both rules are a form of OR, whereas in the previous post one rule was OR and the other AND.

And the form for OR in the rules in this post is all the same. Namely, the additive inverse of the rule number for OR. This is gotten by subtracting from additive identity, which is 0, the digit expansion of the rule number for y ~OR~ z. And the subtraction is carried out modulo 3.

Also notice that the operands in the equivalent expressions merely swap signs for the variables along with signed types of complementation.

Finally, notice that the operands in the first rule have signed types of complementation opposite the signs of the variables. But for the operands of the second rule these are the same.

As examples, see the attached graphics. Figure 1 presents rule 1576494063937: (1 + y + z) the original phase, and figure 2 presents rule 2100313177833: (y - z), phase 4.

Since in figure 1 all cells are 0, 1, or 2, the use of RGBColor assignments did not present a problem. However, with figure 2, the decomposed cellular automata parts do not have any cells with 0, 1, or 2. Rather, all the cells of the decomposed parts are either 7625597484984 or 7625597484986. This is in contrast to the cell values for rule 2100313177833: (y - z), phase 4. They are 0, 1, or 2.

In an attempt to resolve this difference, I used magenta for cells with rule 7625597484984 and cyan for cells with rule 7625597484986. (Perhaps Darker[color, f] would have been a more consistent choice.)

This change to cell values at the end of the list of three-valued logic for two variables calls to mind another thread in which “flips” were discussed as horizontal and vertical rotations of rule number expansions that changed variables from one form to another. In that thread titled “Revised T5 = ({0, +1, x, y, -1}; +, -; 0, +1, -1) Part 1: Foundations”, the two operands of a “flip” were the same just as they are here for generating the decomposition.

Incidentally, the three-valued logic expressions for these cell contents are:

0: 0 (Additive identity)
1: NOR[x, y, z]
2: -NOR[x, y, z]
7625597484984: 1 – OR[x, y, z]
7625597484986: -1 (Negative multiplicative identity)

The recombined figures are not shown since they are the same as the figures before decomposition.

One final remark: The two decompositions for the first figure have exactly twice as many of one type of cell values as the other type. For the second figure it is only approximately twice as many. Moreover, the two parts of the decomposition for the second figure have slightly different counts from each other.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 02-24-2009 at 12:11 AM

Report this post to a moderator | IP: Logged