Registered: Jan 2004
Posts: 350

Introduction

Attached is a notebook that has a logic calculator.
This calculator is a tool to help students and interested ones acquire an intuitive feel for doing what is the next step up from Boolean logic. It is consistent with the logic that lies behind the CellularAutomaton command for three color rules. It is designed to be played with and lead to discoveries of the relations among algebraic expressions, their rule numbers and cellular automatons.

Features

The attached notebook presents a group of mathematical manipulatives together with a grid showing disjunctive normal form (DNF) representations of their results and a cellular automaton plot of the rule number for the disjunctive normal form.

The manipulatives are presented by means of a TabView design and employ Manipulate statements using either PopupMenu or InputField constructs for data entry.

There are two sets of Manipulate statements: one set for three variable logic calculations and the other for two variable logic calculations. Each set includes modulo three product, sum, and difference as well as AND and OR logic operations.

There are six forms for each operation, selectable by means of the PopupMenu construct. The forms represent the operation and its negative, and then the two multiplicative complements of the operation and their negatives.

Variables input to the operations are also selected by means of PopupMenu constructs. Six forms are also presented for the variables. These forms follow the same representation as for the operations.

Whereas the PopupMenu input is in algebraic format, the result of a calculation is a rule number. This rule number appears in three places: at the bottom of the calculation frame and in InputFields at the top of the DNF grid and the cellular automaton plot.

There are also so called Free Form frames in which entries for operation and variables are rule numbers. In these frames there is also a Button labeled Map. When clicked, it produces the rule number result in the same manner as the PopupMenu frames.
The primary purpose of the calculator is to facilitate acquisition of skills in recognizing the relations between three valued algebraic logic expressions and their rule numbers. That is, in recognizing both simplified algebraic expressions and their disjunctive normal forms, and in recognizing the rule number associated with the DNF and the cellular automaton it generates.

The grid used to represent the DNF is designed so that it can be compared to the digit expansion of a rule number. To achieve this, there is a column in the grid for a checkbox character. When the corresponding digit of the digit expansion of a rule number is 1 or 2, the checkbox character is displayed. When it is a 0, there is no checkbox character displayed. Further, there is a column to the right of the checkbox character column that is used to indicate when the digit is a 1 and when it is a 2. When it is a 1, the row corresponding to the digit has a plus sign in the column. When it is a 2, the row corresponding to the digit has a negative sign in the column. This layout allows you to read the disjunctive normal form as a series of signed terms with the implied AND connective by starting with the top term as the leftmost term and continuing down the grid skipping the terms that do not have a checkbox character.
All the frames discussed up to this point are Deployed. That is, they are not editable. However, the InputFields in frames that have them are editable. This makes it possible to copy a result from one of the calculations from the InputField at the top of the grid of the DNF and paste it into an InputField of a Free Form frame. In this way you can construct any number of different mapped rule numbers. It is just that you will have to keep track of the corresponding algebraic expressions manually.
There are two frames not deployed. They are accessed through the tab labeled Help. The first frame is a collection of sample variables and operations together with their rule numbers. You can copy and paste one of the rule numbers into an InputField in the Free Form frames.
The second frame is a modified form of the DNF grid with two extra columns and accessibility to their contents. The column on the right lists the rule numbers when the DNF terms are positive. The column on the right lists them when the DNF terms are negative. Any of these rule numbers is accessible for copying and pasting into Free Form input fields.
There are now two columns of check boxes. One column is associated with positive DNF terms and the other with negative DNF terms. They are no longer merely characters. Rather they are interactive. If you check one or more of the boxes, the sum of the corresponding rule numbers is indicated in the InputField at the top of the grid. So you can make your own rule number and cut and paste it into a Free Form InputField.
Only one AppearanceElement is present within the frames, the ResetButton. Clicking on it gives you the initial settings for the frame. The one exception to this is that there are no AppearanceElements for the cellular automaton frame or for the Help frame.
Following the attachment is a figure that shows screen shots of the various tabs available through TabView.

Use

Some examples illustrating how useful the calculator is are listed below:
(1) Recognizing equivalent expressions: Many equivalent expressions can be found by comparing various PopupMenu settings of different frames and noticing that they result in the same rule number.

(2) Discovering simplification rules: DNF entries for a particular frame’s PopupMenu settings suggest how simplification rules might be written when converting a digit expansion to a simple algebraic expression. For example, the simplified expression in the AND frame for three variables, -1+AND[{-p, -q, -r}] results in a DNF that has all negative terms with one exception, the leftmost term: (-p˄-q˄-r), which is excluded. This suggests that a rule that checks the digit expansion with a low order 0 followed on the left by all 2s will go to the algebraic expression: -1+AND[{-p, -q, -r}].

(3) Exploring correlation between type of operation and complexity of cellular automaton: Rules for AND and OR generally will not produce complex cellular automata plots. But rules for modulo 3 operations may.

(4) Exploring correlation between DNF terms and cellular automaton complexity: When many check-boxed DNF terms for a rule are clustered adjacent to each other, the cellular automaton for the corresponding rule is likely to be less complex than for a rule with many clusters of adjacent terms interspersed among missing terms.

(5) Impact of changes to low order digit of DNF terms on complexity of cellular automaton: Sometimes changing the last digit of just one operand in a rule for AND and OR can result in a change of complexity in the cellular automaton. For example, when entering input in Free Form {p, r}, if the operation rule is 7625597483472: 1-AND[{p, r}], the first operand is 3812992433055: p, and the second operand is 4399383164415: r, then the result will be 7625597483472, which is identical to the operation InputField contents. Its cellular automaton plot appears at the projected scale to be a white triangle filled with rows of black dots on a black background. There are no gray cells at all. And this is consistent with the contents of the DNF grid, since all but three entries are minus signs. Those three entries without minus signs are missing.
Now, change operand 1 from 3812992433055: p to 3812992433052, by replacing the low order digit 5 with 2. The result is 7625597484984 and the DNF grid shows that all entries except the low order one at the bottom of the grid are signed negatively signed. The leftmost entry is missing. This seemingly incidental change simplifies the cellular automaton plot by removing the rows of black dots from inside the now completely white triangle.

Operating Instructions

Open the notebook and evaluate the cell in the Section labeled Manipulation.
You will be asked if you want to do "initialization". Say "Yes".
From then on use the PopupMenus and the mouse or cut and paste. But never use Shift-Enter.

Quirks

On the first selection (s) of the Cellular Automaton tab, the picture may still be the default. If so, return to the Logic Operations tab and change an operand in the frame in which you were working. But then change it back to what you wanted. Then select the Cellular Automaton tab, and the picture will be correct. Sometimes there might be a slight delay in rendering the cellular automaton. If this becomes a problem, you can always modify the code to a smaller ImageSize. This will eliminate the delay.

Take care not to copy and paste non-numeric data from the Help screen into a Free Form frame. If you do and then click the Map button, you will receive a large number of errors. But hit reset for the frame and it will get you back in play. (The real solution is to make all the InputFields be Number, but I could not figure out how to do it.)

Attachment: logic calculator.nb
This has been downloaded 341 time(s).

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Here are some screen shots.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

There are two tabs for the two variable logic operations.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Here is the second page.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Here are the cellular automaton screens for three and two variable rules.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

In the NKS Book on page 51-52 Wolfram describes his approach as similar to a naturalist, "exploring and studying the various forms that exist in the world of simple programs."

Using this approach he was able to examine many computer simulations and gain insight into classifications of their behavior. And go on to develop NKS.

That was in the mid-1990s. In September, 2011 it was announced that a group of U.S. gamers "playing a protein folding game called Foldit, ... successfully unlocked the structure of an AIDS related enzyme that scientists ... [had] been unable to unlock for a decade. And it took them less than ten days! (http://www.matchmove.com/news/article/foldit-gamers-solve-aids-puzzle)

Now if one very gifted person can use his spatial reasoning skills together with computer simulations, and many novices can play Foldit (written by Seth Cooper) to make such astonishing discoveries, perhaps there are other unsolved problems that might be laid to rest by similar methods.

This is what I have had in mind when trying to understand how a cellular automaton's behavior is related to the disjunctive normal form (DNF) terms of its rule number.

I am confident that some of you Mathematica users are nimble enough to recognize the simple rules required to do it.

So as a first step to writing a game, I am presenting a Manipulate program that simplifies the exploration of the effect of adding or subtracting DNF terms on cellular automaton behavior.

This tool lets you build your own cellular automaton rule from negative and positive (DNF) terms. Then you can view the cellular automaton plot, revise the rule and view the plot again, etc.

It is intended to help you become familiar with the role the DNF terms play in the behavior of the cellular automaton.

With this familiarity, perhaps you can be the one who discovers the simple rules required to predict vast amounts of cellular automaton behavior.

Rules might be envisioned as being in the form: "If I just include this one additional DNF term, the behavior of the cellular automaton changes instantly from one class to another."

Think of it as a mimic octopus instantaneously changing to resemble another sea creature. (http://en.wikipedia.org/wiki/Mimic_Octopus)

Features

Everything is presented in a TabView construct. There are two tabs:
(1) Make Rule and
(2) Cellular Automaton.

The Make Rule tab presents two Manipulate statements.

The first is two lists of rule numbers with check boxes separated by the list of disjunctive normal form (DNF) terms for three variable, three valued logic.

The list of rule numbers on the left corresponds to negative values of the DNF terms. The list on the right, to positive values.

Clicking on the check box next to a rule number causes it to be included. But clicking on both the negative side and positive side check boxes cancels out the selection.

Each clicked check box adds a term to the list of terms to be included.

The second Manipulate statement sums up the positive and negative terms modulo three and displays the result as a rule number in an InputField.

Below the InputField is a list of the negative and positive terms that go to make up the rule.

The Cellular Automaton tab presents the plot of the cellular automaton generated by the rule just made.


Quirks

The first time you click the Cellular Automaton tab, you may see the initialization rule and cellular automaton.

Go back to the tab, Make Rule, and change one of the check boxes. Then change it back again.

After this, you should be able to view the cellular automaton.

Unfortunately, there is no directive to automatically have all of the check boxes reset to unchecked, short of re-initializing the code.

So to uncheck all of the check boxes, either click on each checked box or re-initialize the code.
(Notebook attached)

Attachment: make rule.nb
This has been downloaded 261 time(s).

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Attached is a CDF file. It is essentially the same as the file attached in the previous post, but without the code and with some cosmetic differences.

So those without Mathematica can use it with the free CDF Player from the Wolfram Research web site: (http://www.wolfram.com/cdf/).

There are some minor improvements compared to the Mathematica notebook. For one thing, the cellular automaton displays in the same window as the DNF terms and checkboxes. This makes for rapid exploration of how adding or removing a DNF term impacts the cellular automaton.

And note that the cellular automaton is always run from simple initial conditions. This provides a common basis for comparing the effects on cellular automata behavior when adding and subtracting DNF terms.

The initial display is for rule 2970263127 which generates a cellular automaton that in many aspects is similar to Class 3 ECA 30. But the DNF terms check-boxed for this rule include one superfluous term. By removing the checks one at a time, while observing the impact this has on the cellular automaton, you can find the superfluous DNF term.

Here is another thing you can try. Check each box separately and see which DNF terms make the same cellular automaton.

I found that there are just four different cellular automata for all 54 rules representing the DNF terms. See if you come up with the same results as this:

Rules 2, 3, and 19683 are singletons. With rules 1, 6, and 39366 the cellular automaton display is a thick vertical line. The 48 remaining rules have the same cellular automaton display, a thin vertical line.

It is curious that rules 2, 3, and 19683 happen to generate unique cellular automata.

Rule 2: - ((-1+p)[And](-1+q)[And](-1+r)) generates a narrow, candy-cane-striped vertical cellular automaton.

Rule 3: + ((-1+p)[And](-1+q)[And]r) and

Rule 19683: + (p[And](-1+q)[And](-1+r)) generate black boxes with a single diagonal stripe.

In rule 3 the stripe goes from top right to bottom left.
In rule 19683 it goes from top left to bottom right.

Another improvement: You can now clear the check boxes by clicking on the buttons labeled "Reset Minus Boxes" and "Reset Plus Boxes".

I am still getting the hang of the CDF construct. When you open the CDF Player, you see a banner warning that Dynamics needs to be enabled. Click on the Enable Dynamics button. It should then come alive.

Finally, if your monitor is too small for this CDF file, you can use the CDF Player’s f-12 key to toggle to full screen. And if it still does not fit, use the percent magnification option in the lower right corner of the CDF Player to resize.

Also, to get a higher resolution for the cellular automata, used this same option together with the horizontal and vertical scroll bars.

Much has been said about rules and their properties: whether they are capable of universal computation under various initial conditions, etc.

But not much attention has been paid to why so many of the rules, given the same initial conditions, manifest the same behavior.

In fact, while there are over 7.6 trillion three color rules with three variables that can be generated, billions of these produce the same behavior.

Under what circumstances does adding or removing a single DNF term result in changes in cellular automata behavior, rather than a reproduction of the same behavior?

I hope this tool will help us find the answer.

Attachment: make ca rule.cdf
This has been downloaded 259 time(s).

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 12-01-2011 at 03:54 PM

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Attached is a screenshot of the initial screen for the CDF file.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

To put the previous post in perspective I have attached a CDF file that allows you to make ECA rules from Boolean DNF terms.

Several points worth noting:

There is only one column of check boxes. The reason: Although Boolean is a complemented system, it is not a signed system.

The DNF terms have \[Not] (variable), where the signed, three valued logic has either -1- (variable) or 1- (variable).

As with signed, three valued logic, there are four unique cellular automata behaviors for Boolean DNF term rules:

Rule 1: a column of dots flanked by to thin vertical lines.
Rule 2: a box with a diagonal of dots from top right to bottom left.
Rule 4: a thick vertical line.
Rule 16: the box from rule 2, but with the diagonal from top left to lower right.

All the remaining DNF terms have rules that make the same cellular automaton, a transparent vertical rod with a cork at the top.

Here is something to try out:

Check boxes for rules 2 and 16. These two rules alone result in the boxes with the diagonals mentioned above. But together they make the Sierpinsky triangle.

Now add rule 8. There is no change in the behavior although the rule number changes from 18 to 26. You can go on to make rules 82, 90, 146, 154, 210, and 218, all without changing the behavior.

Certainly, it is reasonable to conclude that rule 18 is the most simple of all eight rules. It would be interesting to explore these eight rules with different initial conditions, looking to see if rule 18 stands out in some way distinctive because it is the most simple of the eight rules.

Attachment: make eca rule.cdf
This has been downloaded 267 time(s).

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Here is the initial screenshot for the ECAs CDF.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Structure Among ECA Rules

On page 883 and 884 in the NKS Book we see that the 256 ECA rules are related to each other.

For example, on page 883 cellular automata for rules 110 and 124 are specified as mirror images of each other.

And on page 884, rule 60 is seen to be composed of rules 240 and 204 through the operation XOR.

Xor[p, q]
p = 240;
q = 204;
 FromDigits[Mod[IntegerDigits[240, 2, 8] + IntegerDigits[204, 2, 8], 2], 2]

p Xor q

60


ECA Families

But there is another example of how the ECA rules can be seen as related to each other.

If all rules, that have the same cellular automaton behavior when run with simple initial conditions, are grouped together, they will be seen to be related to each other when run with the same random initial conditions, even though their individual behavior is unique.

Let all the rules, having the same cellular automaton behavior when run with simple initial conditions, be call a family. And name each family after its least rule number.

Then we see that rule 18 names the family having members {18, 26, 82, 90, 146, 154, 210, 218}.

With simple initial conditions the cellular automaton of each member has the same appearance, as seen in attached Figure 1a. But, as seen in Figure 1b, the behavior for each rule is unique when run with the same random initial conditions.


Chiral Relations

However, the cellular automata in the first row of Figure 1b are related. Rule 26 generates right chiral behavior, rule 82, left chiral behavior, and rule 90, neutral chiral behavior. But rule 18 seems to be class 3 with inconsistent chirality.

And in the second row, rule 154 generates right chiral behavior, rule 210, left chiral behavior, and rule 218, neutral chiral behavior. But rule 146 seems to be class 3 with inconsistent chirality.

So the three rightmost rules on each row are related by virtue of their chiral properties.


Modulo Two Sum Relations

How are these related to the leftmost rule in each row?

Modulo two sum of rules with chirality, 26, 82, and 90, results in the class 3 rule 18.

xrow1 = 26;
yrow1 = 82;
zrow1 = 90;
FromDigits[ Mod[IntegerDigits[xrow1, 2, 8] + IntegerDigits[yrow1, 2, 8] + 
IntegerDigits[zrow1, 2, 8], 2], 2]

18

Similarly, modulo two sum of rules with chirality, 154, 210, and 218, results in the class 3 rule 146.

xrow2 = 154;
yrow2 = 210;
zrow2 = 218;
FromDigits[ Mod[IntegerDigits[xrow1, 2, 8] + IntegerDigits[yrow1, 2, 8] + 
IntegerDigits[zrow1, 2, 8], 2], 2]

146

So the last three rules in each row are related to the first rules by modulo two sum, which is identified with the operation Xor.

Moreover, modulo two sum of all four rule numbers on each row is zero.

We can present this in equation form as subtraction of rule 18 from the other three rules due to the fact that modulo two sum is the same as modulo two difference:

rule 18 == (rules 26 + 82 + 90)
(0 == (rules 26 + 82 + 90) - rule 18).

0 == FromDigits[Mod[(IntegerDigits[26, 2, 8] + IntegerDigits[82, 2, 8] +  IntegerDigits[90, 2, 8]) - IntegerDigits[18, 2, 8], 2], 2]

True

0 ==  FromDigits[Mod[(IntegerDigits[154, 2, 8] + IntegerDigits[210, 2, 8] + IntegerDigits[218, 2, 8]) - IntegerDigits[146, 2, 8], 2], 2]

True

So it is a zero-sum mechanism. On the one side of the equation is the class 3 rule. On the other side are the chiral components.

This brings to mind a comparison with the dynamics of physics, where there is the randomness of virtual particle plasma on one side of the equation and real particles with and without left and right handed spin angular momentum on the other side of the equation. This too is a zero-sum mechanism.

Cellular automaton behavior for rules {26, 82, 90} run with the same random initial conditions is analogous to particles with left, right, and no spin. And taken collectively, rules {26, 82, 90} are just another structural form of rule 18.

So rule 18 can manifest itself either as a sea of two kinds of cell values, boiling in apparently random class 3 fashion, or as three separate rules with definite chiral directions, none of whose behavior is at all random.

Incidentally, rule 18 has a very short existence as class 3. Run much more than the 50 time steps shown in figure 1b, it morphs to class 1.


And Half-complements

Taking it one step further, are rules in row 1 related to rules in row 2?

Modulo two sum of like-chiral pairs of rule numbers, one taken from each of the two rows, is always the same.

It is rule 128: (p And q And r).

wrow1 = 18;
wrow2 = 146;
FromDigits[Mod[IntegerDigits[wrow1, 2, 8] + IntegerDigits[wrow2, 2, 8], 2], 2]

128

xrow1 = 26;
xrow2 = 154;
FromDigits[Mod[IntegerDigits[xrow1, 2, 8] + IntegerDigits[xrow2, 2, 8], 2], 2]

128

yrow1 = 82;
yrow2 = 210;
FromDigits[Mod[IntegerDigits[yrow1, 2, 8] + IntegerDigits[yrow2, 2, 8], 2], 2]

128

zrow1 = 90;
zrow2 = 218;
FromDigits[Mod[IntegerDigits[zrow1, 2, 8] + IntegerDigits[zrow2, 2, 8], 2], 2]

128

Notice on page 884 of the NKS Book that rules 127 and 128 are the middle two rules in the list of all possible rules for the two color rules. In fact these two rules represent (p Or q) and (p And q) respectively. These are so called complements of each other.

Since the pairs of rules from row 1 and row 2 sum modulo two to 128, which is the And rule, let us call these pairs of rules from row 1 and 2 And half-complements.


Algebraic Expressions vs Rule Numbers

For the most part we have restricted our discussion to rule numbers. But on page 884 of the NKS Book we see that each rule number is associated with a unique Boolean algebraic expression.

Now, in dealing with rule numbers we refer to their digit expansions. These digit expansion values are ordered left to right by place values, which are powers of two:

{128, 64, 32, 16, 8, 4, 2, 1}.

For example, rule 17 has digit expansion {0, 0, 0, 1, 0, 0, 0, 1}.

The place values for 16 and 1 have digit 1. And modulo two sum of 16 and 1 is 17.

So we say that modulo two sum (Xor) is the operation that joins the place values of the digits to form the rule number.

On the other hand, when discussing Boolean algebraic expressions, we speak of the minterms, rather than the digits. One arrangement of the minterms is sum of products form, called disjunctive normal form (DNF).

The eight DNF minterms from left to right for the two color rules in variables {p, q, r} are:

128: (p And q And r),
64: (p And q And Not- r),
32: (p And Not-q And r),
16: (p And Not-q And Not-r),
8: (Not-p And q And r) ,
4: (Not-p And q And Not-r),
2: (Not-p And Not-q And r) ,
1: (Not-p And Not-q And Not-r)

These terms, when corresponding to a 1 digit of the digit expansion, are joined algebraically by the Or operation to form the algebraic expression for the rule.

For example, rule 18 corresponds to the Or of algebraic expressions for rules 16 and 2:

FromDigits[Boole[BooleanTable[Or[And[p, Not[q], Not[r]], And[Not[p ], Not[q], r]]]], 2] 

18


Coefficients of Minterms

More generally, this can be stated as: the digits in the digit expansion are coefficients of the corresponding minterms. Each coefficient is joined algebraically to its minterm by the And operation. The resulting terms are joined algebraically by the Or operation to form the algebraic expression of the rule.

Joining coefficients by the And operation drops the minterm when the coefficient is zero since (0 And n) is always 0, but retains the minterm when the digit is 1 since (1 And n) is always n.


Algebraic Substantiation – Class 3 Rules and Chirality

Now let us use this information to add substance to our discussion about chiral relations among cellular automata generated by rules of ECA family 18. We restrict our discussion to the first row in figure 1b. But same procedure can be carried out with the second row of rules: {146, 154, 210, 218}.

Recall that, with the same random initial conditions, chiral rules 26, 82, and 90 sum modulo two to class 3 rule 18.

Here are the algebraic expressions for these rules as given on page 884 of the NKS Book:

26: p Xor ((p And q) Or r)
82: (p Or (q And r)) Xor r
90: p Xor r
18: (p Xor q Xor r) And (Not-q)

Sum the first three algebraic expressions modulo two using the Xor operation.

Xor[(Xor[p, Or[(And[p, q]), r]]), (Xor[(Or[p, (And[q, r])]), r]), (Xor[p, r])]

The result is: Xor[(Or[p, And[q, r]]), (Or[And[p, q], r])].

Is this sum equivalent to the algebraic expression for rule 18, which is listed above as: (p Xor q Xor r) And (Not-q)?

Well, both algebraic expressions convert to rule 18.

FromDigits[Boole[BooleanTable[Xor[(Or[p, And[q, r]]), (Or[And[p, q], r])]]], 2]

18

FromDigits[Boole[BooleanTable[And[Xor[p, q, r] , Not[q]]]], 2]

18

So, rule numbers and their algebraic expressions are related. And in this instance the relation is such that the class 3 rule 18 is the modulo two sum of the three chiral rules: {26, 82, 90}.

This is illustrated by the plots of the rules in figure 1b. As we have seen, rule 26 generates right chiral behavior, rule 82, left chiral behavior, and rule 90, neutral chiral behavior. But it is premature to say that all class three rules are composed of a right, left, and neutral chiral rule.


Algebraic Substantiation – And half-complements

We saw above that rules in row 1 of figure 1b sum modulo two to 128 with rules in row 2 when the pair of rules are in the same column. So the pairs of rules summing modulo two to 128 are:

{18, 146}, {26, 154}, {82, 210}, {90, 218}.

Now we want to check that the algebraic expressions for these pairs of rules combine to make the algebraic expression for rule 128 which is (p And q And r).

We take the algebraic expressions of the pairs of rules from page 884 of the NKS Book.

First, the class 3 pair:

18: (p Xor q Xor r) And (Not-q)
146: (p Xor ((p Or r) And q) Xor r)

Sum them modulo two:

Simplify[Xor[And[Xor[p, q, r], Not[q]], Xor[p, And[Or[p, r], q], r]]]

The result is AND[p, q, r].

This corresponds to rule 128:

FromDigits[Boole[BooleanTable[Xor[And[Xor[p, q, r], Not[q]], Xor[p, And[Or[p, r], q], r]]]], 2]

128

Now for the right chiral pair:

26: p Xor ((p And q) Or r)
154: p Xor (p And q) Xor r

Sum them modulo two:

Simplify[Xor[Xor[p, Or[And[p, q], r]], Xor[p, And[p, q], r]]]

The result is AND[p, q, r].

Next the left chiral pair:

82: (p Or (q And r)) Xor r
210: p Xor (q And r) Xor r

Sum them modulo two:

Simplify[Xor[Xor[Or[p, And[q, r]],r], Xor[p, And[q, r], r]]]

The result is AND[p, q, r].

Finally, take the pair with neutral chirality:

90: p Xor r
218: p Xor (p And q And r) Xor r

Sum them modulo two:

Simplify[Xor[Xor[p, r], Xor[p, And[p, q, r], r]]]

The result is AND[p, q, r].


Conclusion

We illustrated through an example of one family of ECAs that a class 3 rule manifests behavior that is related to the behavior of triplets of rules within the same family. And that pairs of rules in the family are so called AND half-complements.

But the family we discussed is not the only family among the ECAs.
The 256 ECAs fall into 143 families, most of which have a single member.
But here are 24 families that have more than one member:

1. {1, 33}
2. {3, 35}
3. {11, 43}
4. {17, 49}
5. {28, 156}
6. {70, 198}
7. {81, 113}
8. {129, 161}
9. {139, 171}
10. {206, 238}
11. {220, 252}
12. {222, 254}

13. {6, 38, 134, 166}
14. {14, 46, 142, 174}
15. {20, 52, 148, 180}
16. {84, 116, 212, 244}

17. {18, 26, 82, 90, 146, 154, 210, 218}
18. {23, 31, 55, 63, 87, 95, 119, 127}
19. {50, 58, 114, 122, 178, 186, 242, 250}
20, {151, 159, 183, 191, 215, 223, 247, 255}

21: {0, 8, 32, 40, 64, 72, 96, 104, 128, 136, 160, 168, 192, 200, 224, 232}
22. {2, 10, 34, 42, 66, 74, 98, 106, 130, 138, 162, 170, 194, 202, 226, 234}
23. {4, 12, 36, 44, 68, 76, 100, 108, 132, 140, 164, 172, 196, 204, 228, 236}
24. {16, 24, 48, 56, 80, 88, 112, 120, 144, 152, 176, 184, 208, 216, 240, 248}

Notice that there are only four families the size of the one discussed here.

Obviously, what has been said is not the last word concerning how members of the families are related.

For instance it could never be said of members of the first 12 families that the leftmost three rules on a row summed modulo two to the first rule.

Figures 1a and 1b are attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

In the previous post I was led by the chiral properties to state that rules 26, 82, and 90 summed modulo two to rule 18. And I described rule 90 run with random conditions as having neutral chirality.

But if you look at the figure for rule 90 (figure 1b), you will see that it is hardly neutral in chirality. It is more like the class 3 rule 18.

This does not change the fact, that rule 18 is modulo two sum of rules 26, 82, and 90. But it does affect the analogy of the dynamics of subatomic particles.

So drop the analogy.

However, something greater is going on in the logic. Not only do rules 26, 82, and 90 sum modulo two to rule 18, but the relation is general: Any three of these rules sums modulo two to the fourth rule.

This holds true for both rows of figure 1b. It also holds true for the two sets of four rules for ECA families 23, 50, and 151. And it holds true for ECA families 6, 14, 20, and 84.

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Digging deeper I found that ECA families that have 8 members, (18, 23, 50, and 151), have this property as well:

Any seven of the rules in the family sum modulo two to the eighth rule.

Moreover, families that have 16 members, (0, 2, 4, and 16), have this property:

Any fifteen of the rules in the family sum modulo two to the sixteenth rule.

Here is code that tests the property for the families that have 16 members. It uses RotateLeft to test each possibility of having one member missing and finds it by summing modulo two the members that are known. This sum results in the missing member. Since modulo two sum is commutative and associative, there is no need to take different permutations.

 genFam16Members[rnums_] := Module[{genFamList, last15, fam},
  fam = rnums; genFamList = {};
  Do[last15 = Take[fam = RotateLeft[fam], 15]; 
   genFamList = 
    Flatten[{genFamList, 
      FromDigits[
       Mod[IntegerDigits[last15[[1]], 2, 8] + 
         IntegerDigits[last15[[2]], 2, 8] + 
         IntegerDigits[last15[[3]], 2, 8] + 
         IntegerDigits[last15[[4]], 2, 8] + 
         IntegerDigits[last15[[5]], 2, 8] + 
         IntegerDigits[last15[[6]], 2, 8] + 
         IntegerDigits[last15[[7]], 2, 8] + 
         IntegerDigits[last15[[8]], 2, 8] + 
         IntegerDigits[last15[[9]], 2, 8] + 
         IntegerDigits[last15[[10]], 2, 8] + 
         IntegerDigits[last15[[11]], 2, 8] + 
         IntegerDigits[last15[[12]], 2, 8] + 
         IntegerDigits[last15[[13]], 2, 8] + 
         IntegerDigits[last15[[14]], 2, 8] + 
         IntegerDigits[last15[[15]], 2, 8], 2], 2]}], {16}];
  Return[genFamList]]

Family

 fam16 = {16, 24, 48, 56, 80, 88, 112, 120, 144, 152, 176, 184, 208, 
   216, 240, 248};

Is tested by

 genFam16Members[fam16]

So there appears to be a self-repairing mechanism at work in the logic.

This seems to me to be significant. In fact, I find it hard to believe that I am not making a mistake somewhere.

I would appreciate any feedback.

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

At the top of this thread I attach a file that contains a three valued logic calculator. In this post I am referring to it as a calculator that does signed Boolean calculations.

While working with this calculator, trying to find the analog in signed Boolean logic to traditional Boolean logic’s first De Morgan law:

(!x) && (!y) = !(x || y),

I noticed an all pervasive error in the code.

Every time an expression contains -1- (Operator or operand) it executes as -1 + (Operator or operand).

-1- is an alternative expression for logical NOT.

This pervasive error has been corrected in the attached file.

My apologies.

Figure 1 in the next post illustrates how the calculator can be useful in identifying equivalent expressions in AND and OR. The darkened region in the figure shows three examples of the analog in signed Boolean logic to traditional Boolean logic’s first De Morgan law:
(!x) && (!y) == !(x || y)

Edited: 3/20/12
Has anyone else noticed? The frame labels for AND and OR on the screens that have two variables are switched. So if you want two variable AND use two variable OR, and if you want two variable OR use two variable AND.

Attachment: basic three valued logic calculator.cdf
This has been downloaded 229 time(s).

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 03-20-2012 at 12:55 PM

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

Attached is the screenshot from the signed Boolean calculator.

The darkened area illustrates the analog to De Morgan's first law.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged