Registered: Aug 2003
Posts: 712

An email asked about this managable rule space. It is interesting, with a few examples of behavior as complicated as seen in any rule class, along with many cases of nesting or particle-like class 2 behavior.

First to explain the rules and the size of the rule space. Range 1/2 means a cell and its immediate left-hand neighbor matter, while the cell on the right does not. This means the pattern can grow only to the right, at a maximum speed of one cell per step.

Totalistic means that all patterns with the same total of the 2 cells must behave the same. Since each can be {0, 1, 2}, the total ranges from 0 to 4, thus there are 5 distinguishable patterns on the prior step. Since each of these could go to any of {0, 1, 2} again, the total number of rules is 3 ^ 5 = 243. Making it slightly smaller than the ECA rule space. There are also symmetries of color rotation which reduce the effective rule space size somewhat further.

The rule form needed to specify one of these in Mathematica is e.g. -

CellularAutomaton[{38, {3, 1}, 1/2}, {{1}, 0}, {50, All}]


- where 38 is the rule number, {3,1} says 3 color totalistic, and 1/2 specifies the range. The {{1}, 0} part says start with an initial condition of a single "1" on a background of "0"s, and the {50, All} says run this rule-init pair for 50 steps and show the results at all space locations that might have been reached in that number of steps.

The two most interesting behaviors are seen in rules 38 and 61. Because of color rotations, there are other rules with the same basic behaviors. You can see the basic behaviors from simple and random initial conditions by asking for -

rules = {38, 61}; inits = {{{1}, 0}, RandomInteger[{0, 2}, 200]};
Grid[Table[
  ArrayPlot[
   CellularAutomaton[{rules[[j]], {3, 1}, 1/2}, 
    inits[[i]], {200, All}], 
   ColorRules -> {2 -> Black, 1 -> Red, 0 -> Yellow}, 
   PixelConstrained -> 2, 
   PlotLabel -> "Rule " <> ToString[rules[[j]]]],
  {j, 2}, {i, 2}]]


Clear class 3 randomness in the random initial case. That in an interior region with some simpler bands in the simple case for one, uniform class 3 for the other.

A Manipulate interface to scan through the behavior from simple initials for all 243 rules is -
Manipulate[
 ArrayPlot[
  CellularAutomaton[{rulenumber, {3, 1}, 1/2}, {{1}, 0}, {100, All}], 
  ColorRules -> {2 -> Black, 1 -> Red, 0 -> Yellow}, 
  PixelConstrained -> 4], {rulenumber, 0, 242, 1}]


I hope this is interesting...

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

A few more observations...

Rule 106 shows simple particle behaviors from simple initials - but can make particles with 2 different speeds depending on the seed it starts from. From random initials, you see sparse but fairly intricate particle interactions among these.

Rule 100 from some simple initials makes a single simple particle - from others, a simple cone of repeating pattern with more uniform borders. From random initials, you get a much more complicated looking pattern, with zones of the same repeating background, others of verticle strips, etc.

Simple nested structures are common. From random initials, these produce overlapping class 3 looking randomness, much like rule 90 in the ECAs.

I have submitted a Demonstration to allow people to explore these using Mathematica Player, but it has not yet been published on the site. I'll post here again when it is and let you know.

Report this post to a moderator | IP: Logged

Registered: Nov 2007
Posts: 16

Interesting! It seems that the phenomenology in this class is richer than in ECAs.

For rule 38, I have found that with initial conditions (including background) made only of blocks {0,1,1} and {1,1,1}, you get nested rule-90-like patterns. The reason seems be that the rule almost emulates the 2-color XOR rule.

For rule 100, with a 0 background, it apparently always yields an ever-expanding {0,0,2,1} region with some stable inclusions of other patterns (mostly {0,0,2,1,2}). Seed {1,1,0,1} has a long transient.

With a {0,0,2,1} background, transients are typically shorter. In contrast, with {0,0,2,1,2} transients can be very long, long enough that it's not clear that they are indeed transients. With seed {1, 1, 1, 1, 0}, for instance, the pattern keeps evolving up to t=3000, and I haven't looked further.

A technical note: the code Jason wrote is valid only in Mathematica 6. With Mathematica 5, you must write the slightly more complicated code:
CellularAutomaton[{38, {3, 1}, {{-1}, {0}}}, {{1}, 0}, 50, All]

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

There is now a Demonstration at the Wolfram Demonstration Project site that explores these rules. This lets anyone see how they behave, whether you have a Mathematica or not.

The link is here -

http://demonstrations.wolfram.com/T...llularAutomata/

I hope this is interesting.

Report this post to a moderator | IP: Logged

Registered: Nov 2007
Posts: 16

I have started a systematic exploration of this rule space. Actually, since its definition does not respect the symmetries of the complete space of 2-cell neighbourhood, 3-state CA ((2,3) CA), I consider the space of symmetric rules. Though there are 729 of them, instead of 243 totalistic rules, there are only 129 equivalence classes, of which 91 have at least one totalistic member.

Obviously, it is not possible to prove automatically that a given rule has complex behaviour. However, there are many ways in which a rule's behaviour can be reduced to a known simple rule. So my strategy is to succesively weed out rules that simplify in that way.

First, if one of the states cannot be produced, a 3-state rule behaves as a 2-state rule after the first step. There are 32 such cases, bringing down the total of rules under consideration to 97, of which 63 are totalistic.

Then, I look at direct emulations of 2-state rules, where there is a one-to-one correspondence between cells. The state assignments of the 3-state rule can have the types {0}->0, {1,2}->1 or 0->0, 1->1. The first case I call refinements and the second extensions. Extensions are not necessarily simple, but refinements are: the distribution of cells in state 0 is simple, since it is the same as in the 2-state rule, and though one may think the respective distributions of states 1 and 2 could be complex, it is clear that (2,2) rules are simple enough that it is not the case.

Checking explicitly for all possibilities amongst the 97 rules, it turns out that 28 are refinements. Visually interesting cases are for instance rules 2462(totalistic code 32), 4098(48) or 7441(97).

If one looks at every other step of the evolution, (2,3) CA become (3,3) CA. Can they be refinements of (3,2) CA (a.k.a. ECA)? The answer is yes and there are 6 additional cases:
851(14)-> 236, 2432(29)-> 0, 3281(41)-> 254 and 128, 6621(87)->72, 9891->236 and 200,
11481(141)-> 72 and 36.
As all emulated ECA are simple, these 6 CA are simple.

Last edited by RLamy on 02-17-2008 at 12:33 AM

Report this post to a moderator | IP: Logged

Registered: Nov 2007
Posts: 16

After a hiatus, I'm resuming this study. I will now consider extensions of 2-state rules. In contrast with refinements, the fact that a 3-state rule is an extension of a 2-state one gives in general no definite determination of the rule's overall behaviour. It is however a useful classification.

So, amongst the 63 remaining symmetric CA under consideration, 29 are extensions of a (2,2) rule. Their behaviour depends on which rule they extend: there are 4 (equivalence classes of) (2,2) CA, rule 0, rule 1 (NAND), rule 6 (XOR) and rule 8 (AND).

It seems that extensions of NAND can only have very simple particle dynamics, with only static walls and possibly a uniform state spreading on a background. For extensions of 0 and AND, the situation is less clear, but it seems that they are all simple with the exception of rules 5709(66) and 5710(67). These two rules are extremely similar and produce chaotic networks.

XOR extensions are more interesting. These are rules 1668(21), 3966, 4047, 4068(45), 4128(51), 4890(57), 6528(75), 12240(144) and 17190(207). All of them can have nested and chaotic behaviours, possibly simultaneously - see the attached image of the evolution of rule 12240 with initial condition {{1, 1, 1, 2, 2, 2, 0, 0, 1}, {1, 2, 2}}. Also, in the case of rules 1668, 3966 and 4128, the third state can "penetrate" domains evolving according to the XOR rule giving rise to dynamics that can probably described in terms of percolation.

Report this post to a moderator | IP: Logged

Registered: Nov 2007
Posts: 16

Sorry, I failed to attach the image accompanying my last post. Here it is.

RLamy has attached this image:

Report this post to a moderator | IP: Logged