Jason Cawley
Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Posts: 712 |
Yes, I have looked at them. I wanted less random cases, where the same rule is applied for large blocks of steps. I was thinking of models of phase transitions.
The obvious test controls are density as a threshold or as an average of the pattern width to that point. I looked at those and can tell you what I basically found. Then I will discuss a bit how I thought about them and the ICA set up I moved to next.
With a single threshold and 2 rules, one typically gets one of a few simple behaviors. Either the initial condition and initial rule never reach the threshold, or they cross it after some period of "unitary evolution" according to the initial rule. Then, often the rest of the evolution stays in the second rule. You just go, once, from rule 1 to rule 2. The second rule winds up starting from an "initial" condition typically produced by the previous rule. After that, it looks much like the second rule typically does. For a given threshold, as you vary initials you typically get a "all first rule" set and then a "1->2 and stays there" set.
Not too interesting. One can get other behaviors. A common one is when the rules effectively "point" in "different directions" in density tendency, with the initial rule headed toward the threshold. Then you typically resolve to rapid switching style randomness. The system can't spend long in either pure state without drifting across the threshold, and back it goes. The long run evolution winds up looking about like the mod 2 switch rule or random switching at each step - thoroughly mixed class 3 looking stuff dominates.
To find a case where the change isn't so instant, you need at least one of the rules to allow large changes in density from step to step (for this threshold and 2 rules etc, mind). Rule 90 is a case in point. It can show arbitrarily large drops in number of black cells, after reaching the bottom of one of its triangle structures, aka one of those large white triangles forms. That can drop you through the threshold without staying close to it. Then it can take a while to come back to 90, if the rule you go tends to fill in these white areas. (An example is rule 90 and rule 146).
Another effect here is that small changes in the threshold sometimes make no difference, while larger ones do - due to the size of features in rule 90. As you dial through threshold levels, the pattern stays the same, stays the same, then ding there is a discrete change this far down, the size of one little gasket. The rule has switched to 146 for so and so many steps, where at the previous threshold level it stayed in 90.
You can get cases that meander back and forth this way, but the underlying rule used can be described (up to exact step number, to be sure, which depends on initials and threshold etc) as some simple finite state machine going 1->2->1->2... I suppose one might look for cases - rule pairs, thresholds, and initials - in which the sequence of times in each is complicated and occasionally long.
Another way to try to find more interesting rule switching behavior is to make the threshold a more complicated function. Clearly, the even or odd version described in the first post above makes it nearly random (in the typical NKS-ee, deterministic way). A single density usually makes it quite simple - point attractor or simple cycle in rule applied. So you can try more complicated thresholds, bands to stay within e.g. You can also try adding a third and fourth rule, to support more elaborate switching cycles etc.
What I found looking at this - relatively briefly I must say, there is still plenty to do exploring them - is that most obviously simple thresholds gave simple or random switch behavior. While I could get more elaborate switching, I was basically programming it in, by using known features of particular CA rules and the details of the threshold tests. For instance above I used the fact that density can drop far, fast, in rule 90. One can use the fact that density tends to .5 in rule 30, with heavily damped, small fluctuations. And tends to more like 0.57 in rule 110. To "use" them, I then wind up figuring out some inequalities for thresholds that point them the right ways etc.
Another way to get slightly more elaborate cycles of the rule applied with more than 2 rules, relatively simply, is to have the next rule depend on the current one, or in other words have the transition test increment the rule used rather than assigning it to exactly rule #2. Then you aren't close to the same threshold and the same rule pair each time.
While I was thinking about schemes for threshold functions, it occurred to me to consider them generally, and that connects to the ICA set up. A switch test defines a GCA if there is some deterministic, single valued mapping from the CA state at a step to the next rule to use (or the first difference of rule to use). As long as the exact same internal state goes to the same rule or makes the same rule transition (+1 e.g.), it qualifies as a GCA.
If I want to find a threshold function that from this initial gives the rule application sequence, exactly {0,0,0,1,1,1,1,0,0,1,1,1,0}, then I just want any function that maps CAstate[t1] to 0, t2 to 0, t4 to 1, etc. Since there is far more information in the states (100 cells wide at each time step say) than I am mapping them to (a choice out of a handful of rules), there is tons of freedom to go find one - it just won't in general be simple.
GCAs are a proper subset of the ICAs, the latter being defined just by being giving their rule to use at each step explicitly and externally, regardless of their internal state. Suppose I want one of the GCA evolutions that starts at rule 0, crosses a threshold at step n, and then stays at rule 1. Then I need any threshold function that maps steps 1 to n-1 into 0, and steps n to infinity to 1. An ICA given an interacting sequence of 0...0 n-1 times followed by 1s gives the same evolution. The GCA works out what n is "inside". But you could work out the answer, and build an ICA interaction sequence based on it.
GCAs are not equivalent to ICAs (proper subset, ICAs a larger set) because there are possible ICA sequences of rule applications that are not possible GCA sequences. Because a GCA needs to be a deterministic function of the state at the previous time step, which is single valued. Therefore, the same exact internal configuration must give the same rule application result. But an ICA can, but need not, do this. An ICA that just happens not to assign different next rule numbers to equivalent internal states, is thus formally equivalent to a GCA with some threshold function - but perhaps an extremely elaborate one.
I do think the GCAs are a more natural model for certain sorts of systems. The ICA set up is meant to be a machine with input, a system in some sort of ongoing interaction with an external environment. You can make that environment internal rather than external, if you want, and thus view GCAs as a proper subset of ICAs. But the GCAs with particularly simple thresholds aka switch conditions, are in a way a much simpler set to explore. The more you complicate the threshold conditions (pushing for elaborate switching cycles etc), the closer you are going to get to the full switching control of an ICA, in effect.
I have since mostly looked at the ICAs. I wanted to look in particular at the sorts of direct array behavior (rather than rule switch behavior) I could get by fully controlling "how much" of rule X I mixed with rule Y. I found things like crosses between 2 class 2 rules that give complex behavior by exploiting the interaction of normally short transients - among other things.
Here is an old thread explaining ICAs, in brief.
http://forum.wolframscience.com/sho...s=&threadid=500
I'll post a notebook on these shortly, for those who want to explore them themselves.
Report this post to a moderator | IP: Logged
|
Attachment: 
10-14-2003 05:47 AM
Attachment: 
