Jason Cawley
Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Posts: 712 |
No, it is not an example of programming a 4. That refers to changing only the initial condition used, not the rule itself.
What you are looking at is what I call an ICA - I for interactive - with a periodic interaction condition. An ICA is the "machine with input" form of a CA, with a bit (or more) fed in at each step that switches the rule it applies. This can be thought of as a more general rule with 2 halves of its rule table specified by the ECA rules, and an addition "vertical" or "global" bit that effects all cells on a given step, fed in by an outside sequence.
There are 65536 such basic ICA rules. You can readily generalize it to any number of rules - effectively allowing the external bit-stream to have any number of colors. Then you can treat the interaction condition - the sequence of global bits used - as a kind of separate initial condition.
In programming terms, instead of a NestList of repeated application of the same function to its prior results, you have a FoldList that feeds in an external variable at each step, as well.
There are a number of threads on the forum about ICAs and code for running them. In general they give the same classes of behavior as ECAs, but also many finer gradations between them. In particular, the ability of the interaction condition to "nudge around" even a class 2 behavior, makes it easier to mix class 3 or 4 rules with something stabler.
You get a much finer sense of gradation between behaviors, as you tune the portion of the interaction condition applying one rule, vs the other. For some mixes the IC is obvious, though - it makes alternating bands in a pattern that otherwise lacks them e.g.
You can find cases where the ICA cross of 2 class 2 rules is complex. That is the largest change I've seen in them, in rule class terms. It arises because there are many class 2 rules that have enough going on to support complexity, but don't "naturally" because they send previous steps to steps that lack the patterns needed to cause their more complicated behaviors.
That shows up as short transients where more seems to be going on, when started from random initials - but it then dies out. If, in the period of time the transients typically last, you switch to a different rule, you can send the next state to something that still has transient effects. So interleaving 2 such class 2 rules can sometimes give class 3 looking randomness.
You can also get a lot more stuff that looks 4-ish, from mixing stability via a 2, with more complicated behavior from a 3 or 4. You get local structures from the class 2 steps, but they are altered in complicated ways by the interleaved class 3 or 4 steps. As you tune the portion of 3 or 4 steps lower, you get something that looks 2 stable, but can be nudged around in minor ways.
There is little doubt that many ICAs are universal. Obviously they are, trivially, if one of the component rules is.
When the interaction condition is constrained to be exactly periodic with period 2, though, you won't reach the full range of ICA behaviors, that are possible with a general, unrestricted pattern of application of the first or second rule. Such rapid switching tends to make class 3 behavior more common.
ICAs were a generalization of the GCA idea, which also switches the rule on each step, but gets the bit to use from some function over the system's own previous state. G there stands for "global". The GCA set up was dreamed up by Wolfram and Paul Davies over dinner a few years ago, to explore different sorts of "emergence'.
The ICA set up was invented at the 2004 NKS summer school at Brown, in part to explore claims by Peter Wegner that interactive computation reaches fundamentally more than the space of classic computables. They are useful but I believe that extreme claim for them is inaccurate. It has precursors in the "non-deterministic Turing machine" set up, which Wolfram discusses in NKS but was doubtless around before, as well.
For every sequence of switches a GCA switch function might give rise to, there is an ICA sequence giving the same behavior externally. Since a GCA is constrained to be a single valued function of the system's previous state, the reverse is not true, and ICAs are a strictly larger space than GCAs. To see this notice that a GCA must cycle if it hits the exact same state, while an ICA might get an external 0 the first time around and an external 1 the next time around, and so fail to cycle.
GCAs are still a natural model for some systems, and ICAs are a quite flexible set up and a natural model for many others. The search spaces are larger because the dependence on the externals is more involved and there are more cross rules, rising as fast as increasing neighborhood size would.
You can also generalize the idea to have different rules applied at each (position, time) step in the evolution. This makes the interaction condition a whole array rather than a list of bits. A standard ICA then corresponds to feeding in uniform steps {0,0,0,...0} then {1,1,1,..,,1} etc. And a standard CA to feeding in {0,0,0...} at every step.
You can use that set up to implement a probabilistic CA as well, with all the "coin tosses" effectively "pulled out" and "pre-generated". Naturally it is easier to implement the last with a random call inside the step function, but the formal ability to separate them shows a direct correspondance between generalized ICAs and nondeterministic rules.
I hope this helps.
Report this post to a moderator | IP: Logged
|
06-09-2006 12:45 PM
