Embedded Files
Perfect Permutables (or just Permutable)
Let's think back to the definition of perfect permutable. A perfect permutable is defined as those CA (notice I didn't say ECA) that exhaust all possible permutations of n-space and n-state rules. Again, let's look at a 3-space 2-state ECA.
Figure 23.2a: Source: https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes/ Author: Stephen Wolfram
Notice that every possible combination of white and black cells has a rule defining what the output cell in the next array (midwise) will be. We can also create a perfect permutable with 2-space and 2-states. The image below demonstrates the 2-space, 2-state, leftwise rule for generating a Sierpinski triangle.
Figure 23.2b: Perfect Permutable 2-space leftwise binary elementary cellular automata
Below is an example of a permutable 1-space binary midwise ECA.
Note that for all ECA examples, the initial array is all 0s except for the center element which is set to 1.
Figure 23.2ba
Figure 23.2bb
Figure 23.2bc
Figure 23.2bd
The most complex behavior we can generate is an alternation of a vertical column.
2.4: Perfect Permutable 1-space Binary Midwise ECA
2.4: Perfect Permutable 1-space Binary Midwise ECA
We can continue and consider a 1-space 1-state permutable, but this won't reveal anything exciting. Either all states turn off or all states turn on. Those are the only possibilities for a 1-space, 1-state ECA. What about a permutable 1-space n-state where n > 2? It appears, again, that nothing remarkable happens. The most complex behavior that can be generated is only alternating patterns.
2.5: Perfect Permutable 1-space Ternary Midwise ECA
2.5: Perfect Permutable 1-space Ternary Midwise ECA
Figure 2.5a
Figure 2.5b
Figure 2.5c
Partial Permutables
I think it is safe to say at this point that complexity cannot arise with so few rules and with rules so simple. Remember that a 3-space binary rule is more complex than a 2 or 1-space binary rule because the 3-space rule needs to 'check' more cells than the latter two rules. It should be obvious at this point that the amount of rules are not the only important parameter, complex behavior also depends on the complexity of the rules themselves.
Finally, we can talk about imperfect permutables. An imperfect permutable is a class of CA that is perfectly permutable of one n-space but partial in some n-space where n can be positive or negative. We have worked our way down to the simplest ECA that have any behavior at all. The only way to go now is back up, but let's take a different path there...
Let's create an imperfect permutable that is perfect in 1-space but imperfect in 2-space. We will make this sub-elementary cellular automata (SCA) binary. Let me explain exactly what this SCA's rules will look like. We will explore all of its permutations, but for this first SCA, if it encounters a single 0, it will do something, if it encounters a single 1, it will do something [the SCA is now perfect in 1-space], [here is where it is imperfect in 2-space] if it encounters a 00, it will do something. Uh-oh! There's a problem here. Do you see it? It appears the order with which you apply the rules suddenly matters! Think about it, if we check for a 0, then check for a 1, we will never get to the case where we check for 00 because, by definition it is perfect in 1-space, so every possible configuration is accounted for. It would never be able to run the rule: check for 00, because it will either find a single 0 first or a single 1 first. Those rules which are imperfect should be run first in order to have the chance that they will run at all. Order Matters!
Let's refine the rules for this SCA - if it finds a 00, it will do something, if it find a 0, it will do something, then, if it finds a 1 it will do something. Notice that as long as the perfect permutable space rules run last, the rules in perfect permutable space can run in any arbitrary order, assuming they come AFTER imperfect space rules. Interestingly, it appears there is a kind of PEMDAS to rule order.
Let's take a look at what this imperfect permutable will do.
Take a look at the order of the if statement below. I know the variable names are bad, but R001 is the imperfect 2-space rule. Notice it is checking if the first element in the array is zero AND (Logical AND - &&) it checks if the following element is a zero as well. Only after this imperfect rule has been checked, will it start checking through the perfect permutable 1-space ruleset. The first else if(){} statement is checking if the first element, and only that element is a 0, if it is, set the element in the next timestep equal to whatever the user specified, and the second else if(){} tests if the element equals 1, and if it is, it will set the element in the next array equal to whatever the user specified. One last thing to note before we dive into behaviors of the imperfects, is the duality of the ruleset's nwise. For 1-space, unless otherwise defined, it is midwise, for 2-space, it is leftwise. You can imagine mixing up the nwise but if you do, just make sure to keep it consistent.
Figure 2.5.2
Let's look at what these rules do with varying inputs.
Ruleset Order
Ruleset Order
00->bit
00->bit
0->bit
0->bit
1->bit
1->bit
Figure 2.5.2aa
Figure 2.5.2ab
Figure 2.5.2ac
Figure 2.5.2ad
Hopefully you recognize some familiar faces in the outputs. Here are the if statements for the next iteration.
Figure 2.5.3
Ruleset Order
Ruleset Order
01->bit
01->bit
0->bit
0->bit
1->bit
1->bit
Figure 2.5.3a
Figure 2.5.3b
Figure 2.5.3c
Let's skip ahead to imperfect 2-space rule (11->bit) perfect 1-space
Figure 2.5.4
2.6:
2.6:
Ruleset Order
Ruleset Order
11->bit
11->bit
0->bit
0->bit
1->bit
1->bit
Figure 2.6a
Suffice it to say that the image above is the most complicated behavior from the last ruleset. Here is a link to the code if you want to play around with the rules. Lets add one more partial from 2-space rules. So, there is a total of 4 rules in the next ruleset.
Ruleset Order
Ruleset Order
11->bit
11->bit
01->bit
01->bit
0->bit
0->bit
1->bit
1->bit
Figure 2.6b
Figure 2.6c
Figure 2.6d
Look at that, it seems the Sierpinski triangle is back. Four rules allow for enough interaction to make this recursive fractal which was impossible with the 3-ruled systems we tried previously. Let's take it one step further. Let's add one more rule to the imperfect 2-space ruleset. In the if statement below, another rule has been added. It checks for a 1 in the current cell and a 0 in the proceeding cell. If it finds them in that order, it sets the state of the cell in the next time step to a 1 or a 0.
Figure 2.7
Ruleset Order
Ruleset Order
01->bit
01->bit
11->bit
11->bit
10->bit
10->bit
0->bit
0->bit
1->bit
1->bit
Figure 2.7a
Figure 2.7b
Figure 2.7c
I can tell we are almost there. We are hot on the trail of a ruleset demonstrating chaos with fewer than 8 rules. In the images below, you can see some new behaviors we haven't really seen yet (See bottom image and middle-left in group).
Ruleset Order
Ruleset Order
101-> bit
101-> bit
01->bit
01->bit
11->bit
11->bit
10->bit
10->bit
0->bit
0->bit
1->bit
1->bit
Figure 2.8a
Figure 2.8b
Figure 2.8c
Figure 2.8d
Figure 2.8e
Page updated
Report abuse