A New Kind of Science: The NKS Forum > Pure NKS > Three color, two variable CAs
Author

Registered: Jan 2004
Posts: 357

Three color, two variable CAs

Page 60 of the NKS book presents reasoning for introducing totalistic rules. Rules that involve three colors, rather than two, number over 7 trillion. However, this refers to three color rules in three variables.

If we restrict the variables to just p and q, the rules number 19,683. Although still large, this is manageable. The trick is to update each cell with input from the two adjacent neighbors. The previous value of the cell is not used in the calculation.

This is an extension of the Boolean system of rules. Whereas in Boolean the values are {0, 1}, here they are {0, 1, 2} with {2} acting logically as {-1}. The {0} covers additive identity, but the multiplicative identity splits into positive and negative identity.

Also, the minterms are products of variables having three states. For example, the variable p is present as (p), (1- p), and (!p). The last form corresponds to Boolean Not[p] and is related to negative multiplicative identity. The middle form is the new one, being related to the positive multiplicative identity.

When more than one minterm occurs in an expression, the minterms are summed modulo 3. This differs from traditional Boolean systems in which the minterms are ORed.

One other difference occurs when the coefficient is 2 rather than 0 or 1. The coefficient 2 acts as a (- 1) and is taken with the minterm to form a modulo 3 product.

Fortunately this logic can be performed on the rule numbers themselves using a mapping function rather than symbolically. Here is the mapping function.

Function to map from any two expressions into a third expression. The two operand expressions are the left and right hand neighbors of a cell in the CA. The operation is the rule. The third expression is returned as the updated value for the cell. Rule operation and operands and the result are all integer numbers in the range 0 through 19682. They correspond with the expressions for three valued, two variable Boolean logic.

map[operation_, operand1_, operand2_] : =
FromDigits[Reverse[IntegerDigits[operation, 3, 9]] [[ Dot[MapThread[List, {IntegerDigits[operand1, 3, 9], IntegerDigits[operand2, 3, 9]}], {3 ^0, 3 ^1}] + 1 ]], 3]

Attached is a graphic showing behavior of some of the more interesting rules.

For a more complete discussion of this extension of traditional Boolean logic see the following post on this forum that covers three variable, three valued logic: Reflections.

There is also a Mathematica notebook that you can download. It is called: three color three variable.nb.

Lawrence J. Thaden has attached this image:

__________________

Last edited by Lawrence J. Thaden on 05-13-2006 at 11:52 PM

Report this post to a moderator | IP: Logged

02-19-2006 05:35 AM

Registered: Jan 2004
Posts: 357

The previous post was edited because of rule 9503: (p + (- 1)), where + is modulo 3 sum and (- 1) is the negative multiplicative identity.

The lattice complement of any expression p is given by rule 11089. Here is the syntax:

map[11089, p, 9841] -> Not[p], where 9841 is positive multiplicative identity.

Here are some other useful rule numbers:

19305: p
10179: (- p) Complement of p with respect to additive identity: rule 0.
18967: (1 - p) Complement of p with respect to positive multiplicative identity: rule 9841.
377: Not[p] Complement of p with respect to negative multiplicative identity: rule 19682, the lattice complement.

715: (p + 1) Where + is modulo 3 sum.
9503: (p + (- 1)) Where + is modulo 3 sum and (- 1) is negative multiplicative identity.
19682: (p + Not[p]) -> (- 1)

15897: q
11355 (- q) Complement of p with respect to additive identity: rule 0.
14383: (1 - q) Complement of p with respect to positive multiplicative identity: rule 9841.
3785: Not[q] Complement of p with respect to negative multiplicative identity: rule 19682, the lattice complement.

5299: (q + 1)
8327: (q + (- 1))
19682: (q + Not[q]) -> (- 1)

6561: And[p, q]
6560: And[Not[p], Not[q]]

19681: Or[p, q]
13121: Or[Not[p], Not[q]]

8229: Modulo 3 sum
11502: Modulo 3 product

1557: Xor[p, q] Negative multiplicative complement Xor for any p and q, where 0 and 2 are complements and 1 is its own complement. This is the lattice complement form of Xor.
18125: Not[Xor[p, q]]

Minterms:

6561: And[p, q]
2187: And[p, (1 - q)]
729: And[p, Not[q]]
243: And[(1 - p), q]
81: And[(1 – p), (1 - q)]
27: And[(1 – p), Not[q]]
9: And[Not[p], q]
3: And[Not[p], (1 - q)]
1: And[Not[p], Not[q]]

Minterms with coefficient 2:
Formed by modulo 3 product of (- 1) and the minterm.

13122: - And[p, q]
4374: - And[p, (1 - q)]
1458: - And[p, Not[q]]
486: - And[(1 - p), q]
162: - And[(1 – p), (1 - q)]
54: - And[(1 – p), Not[q]]
18: - And[Not[p], q]
6: - And[Not[p], (1 - q)]
2: - And[Not[p], Not[q]]

****************

This post is edited to correct an error. In the minterms, (1 - p), (1 - q), and (1 - r) should read: Not[1 - p], Not[1 - q], and Not[1 - r].

****************

The symbolic expression for any rule is given by:

Apply[Plus, DeleteCases[IntegerDigits[anyrule, 3, 9] minterms, 0] /.{2 -> -1}]

However, it will not be in simplified form.

This logic is an extension of Boolean logic. It has all the properties of a Boolean algebra. And the mapping function has closure.

According to MathWorld there are 3072 three-valued logics. I don’t know which one of them this is. Maybe there are 3073. (Eric W. Weisstein. "Three-Valued Logic." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Three-ValuedLogic.html)

Attached is a graphic of some more interesting CAs. These were generated by rules with numbers towards the end of the list.

Lawrence J. Thaden has attached this image:

__________________

Last edited by Lawrence J. Thaden on 04-02-2006 at 05:19 AM

Report this post to a moderator | IP: Logged

02-24-2006 06:31 PM
R.P. van der Hilst
University of Utrecht
The Netherlands

Registered: Feb 2006
Posts: 3

Atlas

Hi Lawrence,

that set of rules definately generates quite diverse behaviour! I was wondering whether you also contribute your research (like these pics) to the Atlas of simple programs?

Report this post to a moderator | IP: Logged

02-27-2006 07:55 PM

Registered: Jan 2004
Posts: 357

These may not qualify as simple programs. Whereas the elementary and totalistic cell values are constrained to values representing the number of states (colors), these allow updated cell values to range over the entire rule space.

Possibly the elementary modulistic CAs that I posted previously are better candidates. They constrain the values of the updated cell to the number of states (colors) as do Wolfram’s elementary and totalistic CAs.

__________________

Report this post to a moderator | IP: Logged

03-02-2006 02:53 PM

Registered: Jan 2004
Posts: 357

Correcting the order of operands

There is an inaccuracy in the expressions for this three valued, two variable logic.
The order of the operands in the mapping function is the reverse of what it should be. For example And[p, q] should be And[q, p]. The proper order is consistent with the arrangement of the list of expressions, which has the variable p at the end of the list and q before p. Just as in the NKS book on page 884, where q is 204 and p is 240.

However, this inaccuracy does not affect the results shown because all of the examples presented are commutative operations.

I discovered this problem when searching for a cleaner way to find lattice complements. This involved an operation that is not commutative, and so the order of the operations was significant. Here is the operation for finding the lattice complement of p, and by the substitution principle, any expression replacing p.

Map[notp, anyrule, p]

The operation notp, rule number 377, is non-commutative and is the lattice complement operation. It finds the lattice complement of the second operand (p). Any rule number can be in the first operand. It does not matter. This does not work if p is used as the first operand.

You can find the operation notp by subtracting the rule number for p:19305 from 19682.

Or more formally by:

FromDigits[Mod[IntegerDigits[19682, 3, 9] - IntegerDigits[19305, 3, 9], 3], 3]

19682, the last rule number in the list, is the rule number for negative multiplicative identity. It corresponds to rule 255 in the NKS book on page 884.

An alternate way to find the complement is to use notq and the first operand:

Map[notq, q, anyrule]

__________________

Report this post to a moderator | IP: Logged

03-07-2006 02:02 AM
Jesse Nochella
WRI

Registered: Mar 2004
Posts: 132

CA's generating necklaces

Hi Lawrence,

In your second post here you attached a graphic that showed a group of sample 3 color, 2 variable CA's, 1 of which I remember viewing during a random sample of k=3 r=1 space a while back. I was not very sophisticated in my browsing at the time and never got the rule number for it and wasn't able to conceptually reproduce it, but I remembered the pattern.

The interesting property about these rules, 14997 and 16245 is that their diagonals themselves are repetitive, but they are all distinct from eachother. Maybe I'm nearsighted and there are actually many rules with this property. What's interesting about this property is that it can be viewed as taking a slice out necklace space as it runs without overlapping ever.

What would all the necklaces look like? could they be made with a cellular automaton?

A function could be made to compute the nth 14997 necklace by running the cellular automaton some number of steps relative to n and then extracting the appropriate diagonal (these diagonals are composed of two colors, although leaving them as they are or changing all the >0 cells to 1 or extracting just the 1 cells or 2 cells may yield sequences with the same kind of correspondence).

Just some thoughts.

By the way you can use CellularAutomaton alone to run these rules.

Just change the rule to a list with the number, then the number of colors, then a list of all of the nieghbors relative to the center cell, with {0} being the center cell.

CellularAutomaton[{16245, 3, {{-1}, {1}}}, {{2}, 0}, 300]

Cheers.

Report this post to a moderator | IP: Logged

03-07-2006 01:30 PM

Registered: Jan 2004
Posts: 357

Thanks Jesse. I had no idea.

Also, by providing me the standard (Wolfram’s CellularAutomaton), I was able to see that my mapping function had the error I referred to about the order of inputs.

For when I ran rule 16245 using CellularAutomaton I got upper left to lower right diagonals. But with my mapping function they were upper right to lower left.

With the following correction my mapping function produces the same results as CellularAutomaton.

map[operation_, operand1_, operand2_] : =
FromDigits[Reverse[IntegerDigits[operation, 3, 9]] [[ Dot[MapThread[List, {IntegerDigits[operand2, 3, 9], IntegerDigits[operand1, 3, 9]}], {3 ^0, 3 ^1}] + 1 ]], 3]

In the MapThread command operand1 and operand2 now have their proper places.

__________________

Report this post to a moderator | IP: Logged

03-07-2006 06:12 PM

Registered: Jan 2004
Posts: 357

Necklace Rules

Jesse, it appears that there are 4 different left-right pairs of necklace CA behavior among k = 3, r = 1 space with rules in the range 0 through 19682.

In the attached graphic note that most of the figures are generated by more than one rule.

There are also three pairs of rules that generate partial necklace behavior. By that I mean only a portion of the triangle is there. The rest is white. These are: {5448, 4248}, {5451, 4275}, and {17805, 16557}.

What I found interesting is that some of the necklace rules generate these partial or “torn” necklaces when you set the initial conditions to {{0}, 2} instead of {{2}, 0}. For example:

CellularAutomaton[{16245, 3, {{-1}, {1}}}, {{0}, 2}, 300]

But in this example it has a black background.

Similarly, rule 17805 gives partial or “torn” results with initial conditions {{2}, 0}. But full necklace behavior with {{0}, 2}. However, the full version has a black background.

I also found that, with this set of initial conditions, rule 16245 generates two, nearly identical and side by side, partial or “torn” necklaces:

{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,2}

I had to run it with my map function since I do not know how to set up these non-cyclic initial conditions with the CellularAutomaton command.

Lawrence J. Thaden has attached this image:

__________________

Last edited by Lawrence J. Thaden on 03-11-2006 at 03:55 AM

Report this post to a moderator | IP: Logged

03-11-2006 03:49 AM
Jesse Nochella
WRI

Registered: Mar 2004
Posts: 132

Funky stuff.

What's interesting that I notice is that we're kind of running a cellular automaton sideways...

From the 'right corner' where some definite termination 'happened' 'backwards' and 'to the left', but forever...

Kind of like having an infinite series of rule 225's starting from an infinitely back starting position, and you're computing the end of it.

What's even cooler at this point is that these funky starting points and computations have already been looked at, figured out, and been presented by no other than Eric Rowland, at the 2005 NKS Midwest conference, I now remember.

His presentation was about so-called 'Bijective Rules'. There's 'left-bijective' and 'right-bijective' rules that he looked at, and what it means is that if something is left bijective, then if you have a row of cells and one cell also sitting on top of that row of cells, as a determined predecessor, then all the cells to one side, say to the left, can also be determined automatically just from that information. Rule 30 is like that, and so called 'left-bijective'.

When you look at rule 30 from a single black cell to the right-hand edge you will see triangles that keep getting bigger. The proposal that Eric made and what he was able to do was compute rule 30 from the bottom-right of a triangle like those, but infinitely large, up, just from the facts that there would be an infinite row of black cells at the bottom of one of these infinitely large triangles, and that the right hand edge or rule 30 on a white background would always be a black diagonal no matter how far down you chose to start going up from.

It comes to mind that every single one of these bijective rules can be used to compute necklaces, including rule 30. Because there is only one sequence that could terminate the whole thing at the bottom / where to start up from in reverse, and that there can only be one unique pattern that can ever make that terminating pattern, and that there can only ever be one pattern that makes that one and so on—and that all of these reverse/bijective computations can be made to run forever to compute an infinite number of unique necklaces (possibly distinct necklaces can be used again but with a different offset, actually).

And on top of all that, at the very end of Eric's presentation notebook, which I have attached below, is an example of the exact kind of necklace CA's we have been studying existing in your outer k=3 r=1 space that we haven't even found yet.

I hope this is interesting.