Lawrence J. Thaden
Registered: Jan 2004
Posts: 357 
Predicting ECA Behavior Using Venn Diagrams of ECA Rule Numbers
Is Prediction Possible in NKS?
The NKS book on page 6 states:
"One can always in principle find out how a particular system will behave just by running an experiment and watching what happens. But the great historical successes of theoretical science have typically revolved around finding mathematical formulas that instead directly allow one to predict the outcome. Yet in effect this relies on being able to shortcut the computational work that the system itself performs."
"And the Principle of Computational Equivalence now implies that this will normally be possible only for rather special systems with simple behavior. For other systems will tend to perform computations that are just as sophisticated as those we can do, even with all our mathematics and computers. And this means that such systems are computationally irreducible  so that in effect the only way to find their behavior is to trace each of their steps, spending about as much computational effort as the systems themselves."
Does this mean that it is impossible to predict any aspect of the behavior of computationally irreducible systems? No, for Wolfram introduces cellular automata in chapter 1, illustrating the computational irreducible nature of rules 30 and 90. But on page 883 in the notes for chapter 3 he shows, under the subheading "Rule equivalences", that rule 30 has behavior that is also found in rules 135, 86, and 149 and that rule 90 has behavior that is also found in rule 165.
Now, if that equivalent behavior is only observable by comparing the outputs from running the cellular automata, then there is no prediction involved. But if it can be shown that the equivalence will be observed before the cellular automata are run, then there is the element of prediction at work.
The attached notebook demonstrates that such predictions can be made just by an inspection of the binary digit expansion of the rule numbers.
Five Predictable Aspects in ECA Behavior
In fact there are at least five aspects in the behavior of the ECAs that are predictable. This does not detract from their irreducible property. It is still necessary to let them run out to see their complete behavior.
This post and the attached notebook invites exploration of these five predictable aspects of the ECAs using Venn diagrams for the disjunctive normal form (DNF) minterms of the ECA rules.
The first predictable aspect is the appearance of the background of the ArrayPlot for an ECA rule.
The second aspect is the chirality of the ArrayPlot.
The third is predicting when a rule will have an ArrayPlot that turns completely into the background just after it begins.
The fourth is predicting which ArrayPlots will unfold exclusively within the left or right side of the ArrayPlot. Rule 110 is one of these. It unfolds within the left side of the ArrayPlot.
The fifth is a complex phenomenon, which I am not yet able to fully explain. It predicts what will happen when an even numbered rule’s minterms interact with the minterm which is the intersection of (Notp, Notq, Notr). The result of this interaction is recorded in the subsequent odd numbered rule’s ArrayPlot.
Rule Numbers, Binary Digit Expansions, Place Values, Minterms, and Venn Diagram Plot Regions
We begin with a review of the relation between rule numbers and minterms for the Boolean expressions of the rules.
The binary digit expansion of an ECA rule number is a list of 0 s and 1 s which represents the coefficients of disjunctive normal form (DNF) minterms for the Boolean expression of the rule.
Whenever a coefficient has the value 1, the region in the Venn diagram representing the minterm appears colored.
Examining the pattern of colored regions for a rule leads to an understanding of certain features in the corresponding ArrayPlot for the ECA. That is, it allows us to predict certain aspects of the behavior of the ECA.
Plot regions in the Venn diagram are numbered 128, 64, 32, 16, 8, 4, 2, and 1. These are the decimal place values for the digit expansions of the rules.
For example, rule 110 has the binary digit expansion: {0, 1, 1, 0, 1, 1, 1, 0}. Aligning these digits under the place values gives:
128, 64, 32, 16, 8, 4, 2, 1
…0…1…1…0..1..1..1..0
Since place values 64, 32, 8, 4, and 2 have 1 s, rule 110 has Venn diagram plot regions 64, 32, 8, 4, and 2 colored. And the sum of these plot region numbers is 110, the rule number.
Plot Region Groupings
The plot regions are grouped in one of two ways. The first grouping assigns four plot regions to each of the three variables: p, q, and r. This grouping has overlapping assignments for the plot regions. For example, each of the variables includes plot region 128. In addition to these overlapping assignments this first grouping also includes background plot region 1.
The other grouping does not have overlapping plot regions. This grouping has four parts:
(1) Background: plot region 1
(2) Exclusive minterms for the three variables: plot regions 16, 4, and 2
(3) Intersecting minterms for pairs of variables: plot regions 64, 32, and 8
(4) Intersecting minterm for all three variables: plot region 128
How to Predict the Background of an ECA ArrayPlot
When the low order digit of the rule number’ s base 2 digit expansion is 1 but the high order digit is 0, the ECA ArrayPlot has alternating horizontal black and white stripes for a background. In the Venn diagram plot region 1 is colored and plot region 128 is uncolored. (See figure 1.)
When the low order digit of the rule number’ s base 2 digit expansion is 0 and the high order digit is either 0 or 1, the ECA ArrayPlot has a white background. Venn diagram plot region 1 is uncolored and plot region 128 is either uncolored or colored. (See figure 2.)
When the low order digit of the rule number’ s base 2 digit expansion is 1 and the high order digit is also 1, the ECA ArrayPlot has a black background. Both Venn diagram plot regions 1 and 128 are colored. (See figure 3.)
How to Predict the Chirality of an ECA ArrayPlot
Righthanded chirality shows up in the ArrayPlot of an ECA as a right to left slant. This corresponds with colored minterms exclusively within Venn diagram circles q, plot region 4, and/or r, plot region 2, so long as the minterm in the background of the diagram, plot region 1, and the one exclusively within circle p, plot region 16, are uncolored. There may also be other minterms colored. (See figure 4.)
Lefthanded chirality shows up in the ArrayPlot of an ECA as a left to right slant. This corresponds with colored minterms exclusively within Venn diagram circles q, plot region 4, and/or p, plot region 16, so long as the minterm in the background of the diagram, plot region 1, and the one exclusively within circle r, plot region 2, are uncolored. There may also be other minterms colored. (See figure 5.)
A lack of chirality shows up in the ArrayPlot of an ECA as a vertical line. This corresponds with a colored minterm exclusively within Venn diagram circle q, plot region 4, so long as the minterm in the background of the diagram, plot region 1, and those exclusively within circles p, plot region 16, and r, plot region 2, are uncolored. There may also be other minterms colored. (See figure 6.)
Bidirectional chirality shows up in the ArrayPlot of an ECA as an overall triangular shape. This corresponds with colored minterms exclusively within Venn diagram circles p, plot region 16, and r, plot region 2, and optionally with colored minterm exclusively within Venn diagram circle q, plot region 4, so long as the minterm in the background of the diagram, plot region 1, is uncolored. There may also be other minterms colored. There are 27 ECAs of this description. (See figure 7.)
But when plot region 1 is colored, there are 6 more ECA ArrayPlots with bidirectional chirality. And when both plot region 1 and 128 are colored, there are 14 more. But these 20 additional cases are explained below as the effect of interaction with the background. They do not have Venn diagrams matching the above description for bidirectional chirality.
How to Predict When an ECA ArrayPlot Will Turn into the Background Right After Startup
The ArrayPlots for some ECAs stop right after starting. That is, they appear uniformly white, horizontally striped, or black after the first steps. What arrangement of minterms explains this behavior? There are 15 rules each that turn white or black and 11 which turn striped.
Aside from rule 0, those rules that have ArrayPlots that turn white have all possible combinations of one or more of the following plot regions colored: 128, 64, 32, 8. And they all have plot regions 16, 4, 2, and 1 uncolored. (See figure 8.)
Those that turn striped have this in common: All have plot region 1 colored and plot region 128 uncolored. And all have two or more of the following plot regions colored: 16, 4, and 2. Six may also have one or two of the following plot regions colored: 64, 32, and 8. Finally, one has plot regions 16, 4, and 2 as well as 64, 32, and 8 colored. (See figure 9.)
Those that turn black have this in common: All have plot region 128 and 1 colored. Seven have plot regions 16, 4, and 2 colored and may also have none, one, or two of the following plot regions colored: 64, 32, and 8. In contrast seven have plot regions 64, 32, and 8 colored and may have none, one, or two of the following plot regions colored: 16, 4, and 2. Finally, one has plot regions 16, 4, and 2 as well as 64, 32, and 8 colored. (See figure 10.)
Note that plot regions 16, 4, and 2 identify minterms exclusively associated with one of the variables p, q, or r while plot regions 64, 32, and 8 identify minterms associated with the intersection of two of the three variables.
How to Predict When an ECA ArrayPlot Will Unfold Completely on One Side of the Plot Area
Some ECA ArrayPlots such as that for rule 110 occupy either the left or right half of the plot. What arrangement of minterms explains this behavior? There are 16 ECA rules of this kind. All of them have plot region 1 uncolored. Eight have plot region 128 uncolored and eight have it colored. The chirality determines which half of the ArrayPlot is occupied. Each has a pair of exclusive minterms colored, one of which is associated with variable q. No pair is associated with p and r. In addition one or more of plot regions 64, 32, and 8 may be colored. (See figures 11a and 11b.)
How to Understand What Effect the Venn Diagram Background Will Have on Chirality
Every odd rule number has the minterm in the background of the Venn diagram, plot region 1, colored. When this is the case, the chirality of the Venn diagram for the preceding even rule number is considered as altered in the subsequent odd rule number. These alterations can be characterized as producing the following effects in the ECA ArrayPlots:
(1) Switching of chirality from right to left or left to right. (See figures 12a and 12b.)
(2) Switching from right or left to a lack of chirality. (See figures 13a and 13b.)
(3) Switching from right or left or lack of chirality to bidirectional. (See figures 14a and 14b.)
(4) Switching from a lack of chirality to right or left or bidirectional. (See figures 15a and 15b.)
(5) Switching from bidirectional to right or left or a lack of chirality. (See figures 16a and 16b.)
(6) Adjustment to the angle of the slant without changing its direction. (See figures 17a and 17b.)
(7) Sometimes there is no change in chirality. (See figures 18a and 18b.)
These 7 observations are manifest with the aid of the Venn diagrams. Looking only at the ArrayPlots of the ECAs gives no clue as to what is happening.
And yet, even with the Venn diagrams of the even numbered rules, it is a strange thing to see what happens when the minterms of the even numbered rule interact with the "background" minterm. This minterm is the intersection of (Notp, Notq], Notr). But the situation is not the same as an interaction with rule 0, which expresses an absence of all minterms.
I believe these complex relations between the even numbered rules and the "background" minterm will be adequately explained one day. And that is why I list them with predictable aspects of cellular automata.
Lawrence J. Thaden has attached this image:
__________________
L. J. Thaden
Report this post to a moderator  IP: Logged
