[ICAs for continual interaction with an external environment] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


ICAs for continual interaction with an external environment

(Click here to view the original thread with full colors/images)


Posted by: Jason Cawley

In the NKS Book, Wolfram discussed what he called a "non-deterministic Turing Machine" 766, which adds a bit of input at each step of the evolution. Effectively this amounts to a second sort of "initial condition", but one mapped through the time dimension and affecting the whole system. What I call an interactive CA or ICA for short applies the same idea to CAs rather than TMs. Todd Rowland from Wolfram Research wrote some nice code for the elementary version of these.

ICAStep[rule_, init_, choice_] :=
(Append[#, choice] & /@ Partition[init, 3, 1, 2]) /. rule


rlno[rn_] :=  MapThread
[Rule, {Tuples[{1, 0}, 4], IntegerDigits[rn, 2, 2^4]}, 1]


ICAEvolveList[rule_, init_List, interact_List] := 
FoldList[ICAStep[rule, #1, #2] &, init, interact]


Then a typical set up is of the form -

startcondition = Table[Random[Integer], {100}];


interactioncondition = Table[Random[Integer], {100}];


And then the function call itself - which produces the data, and you can wrap a display function around - runs -

ICAEvolveList[rlno[6118], startcondition, interactioncondition]


Notice that the length of interactioncondition is also your number of steps.

At first glance, they certainly do interesting things - though their behavior classes are similar to elementary CAs. They do show a wider variety of internal speeds, though. Probably because the external bit can effectively "nudge" them around.

There are 65536 of these, in the simplest version. Extensions to higher numbers of colors are obvious and easily implimented. Notice also that with appropriate choices of rule and a static external environment, a subset of these reduce to the elementary CAs.


Posted by: Jason Cawley

I scanned a few more of these and started playing around with the interaction condition and what it lets one do.

One thing I noticed immediately is another simple behavior that is not perfectly periodic. You get persistent line structures that move slowly and regularly (all the same, not interacting as a result). This is a response to continued variation in the interaction condition. It still gives simple overall behavior because of the uniformity of the effect on the limited, simple persistent structures in these rules. I consider these basically a form of class 2 behavior.

Rule 6118 is doing something more and looks 4-ish. That is why I included it in my previous as an example.

A more interesting behavior can be seen in rule 10028, that shows some of the characteristics of ICAs. For all 1 interaction condition, this behaves as a pure class 3 instrinsically random system (like rule 30 in the ECAs). But for all 0 it gives a simple behavior, a locked in stationary pattern. So the overall rule effectively acts as a GCA, but with the interaction condition providing the global "switching" decision, independently at each step.

If one then feeds 10028 a periodic interaction condition, the overall behavior changes as I change the portion of 1s and 0s in the repeated portion. Thus 1,1,1,1,0 gives class 3 looking behavior, but with some regions of repeating background. 1,1,1,0,0 gives a few persistent line like structures, with a couple of speeds. 1,1,0,0,0 is enough to "kill" the class 3 pattern. Effectively, the small scale structures do not have time to grow.

What is interesting about this is that the allowed switch to a simpler rule (in effect) from step to step, can slow down the uncontrolled information spread typical of class 3 rules. So much so, that it may be possible to program such an ICA. Showing any class 3 is programmable is an important NKS open problem. The intuition behind the idea is that control over information flow is the only barrier to programmability in class 3s.

The ICA set up is certainly allowing oneself more "wiggle room", and one can quibble over whether it "counts" as class 3 itself. It might also be easier to establish an emulation chain to a class 3 looking ICA from a higher color CA without interaction, that to a class 4 directly. So it would be a useful step toward a class 3 result.


Posted by: Jason Cawley

I wrote some routines to extend an ICA to range 2 and looked at a few of them. The space is enourmous, obviously. I found one interesting mix of behaviors in rule number -

8823825577124058

Using the rule numbering scheme -

rlno2[rn_] := 
 MapThread[Rule, {Tuples[{1, 0}, 6], IntegerDigits[rn, 2, 2^6]}, 1]

Note that Tuples is a combinatoric function to generate distinct subsets. It is equivalent to -

Tuples[list_, n_]:=
 Partition[Flatten@Outer[List, Sequence @@ Table[list, {n}]], n]


(There may be a more elegant way to do the same thing, but that will suffice).

The other functions needed for the range 2 case are -

ICA2Step[rule_, init_, choice_] := (Append[#, choice] & /@ Partition[init, 5, 1, 2]) /. rule

ICA2EvolveList[rule_, init_List, interact_List] := 
 FoldList[ICA2Step[rule, #1, #2] &, init, interact]

The data is generated by a function call like -

data = ICA2EvolveList[rlno2[175674346465], Table[Random[Integer], {200}],  Table[Random[Integer], {300}]];

...Then displayed with your favorite graphics function (wrapped around data, or the function call if you prefer).

Rule 88_ shows a variety of behavior, but each of them has been seen before in ECAs - just not so mixed. The interaction bit basically switches between a rule that produces overlapping triangles and a class 4 rule. Rapid periodic switching produces a class 2 striped pattern. With a random interaction vector, you get small dendritic looking structures, some triangular regions of regular background of varying sizes, and bands where the dendritic structures typically die out before starting again as the interaction condition moves on. You can control the behavior with various mixes of 1s and 0s in the interaction condition, repeated.

I can honestly say I haven't see that sort of mix before from a CA rule. And the flexibility is certainly amusing to play around with. But each sub-behavior is recognizable.

There are 18446744073709551616 rules of this type. Rather a lot, really. If that is not enough for you, you can always try 3 colors and range 1 again - there are 4.4x10^38 of those. Range 2 and 3 colors (including the interaction bit) gives 6.6x10^347 rules. Who needs infinities with possibility spaces like these?

Nevertheless, following Wolfram I'd predict you won't find anything fundamentally new in that whole Himalayan range of possible rules. A lot of them will be complicated and programmable in principle, a lot of them will look random, a lot of them will produce simple behavior. Different mixes certainly, and the sort of range one sees in the ECAs crammed into the most interesting single rules, with each "one" really a whole bunch of rules that can operate in series on the same data.

If anyone thinks the ECAs are too "stiff" for some system they are contemplating, these might convince them that has nothing to do with what CAs are capable of, in general. Worth investigation, certainly. I hope this is interesting.


Posted by: Jason Cawley

Looking at ICA 10089 in the range 1 case, I found some nice behaviors. I tried manipulating the distribution of 1s and 0s in the interaction condition, first through a wide range, then focused more on the region between .1 and .5. Many local structures akin to vortices in fluids appear, with a reasonably smooth transition to rule 30 ish behavior as the portion of 1s (effectively applying the class 3 portion of the rule) increases. If nothing else, ICAs are clearly a useful tool for investigating systems following multiple rules on different steps.


Posted by: Jason Cawley

Last night Kovas Bogata and I analyzed the behavior of an interesting ICA I had looked at before. It is rule number 34231, which is interesting because it shows branching structure and triangle patterns with mixed interaction condition (IC), but simple class 2 behavior for either of its component half-rules when fed all 1s or all 0s.

The behavior arises because the class 2 behavior includes small transients. These can interact. One of the half rules just alternates black and white, unless the cell is black and has no white neighbors, in which case it persists for one step. The other always resolves to simple stripes of black down the page, but does so by reducing any string of uniform black one cell at a time. From a random initial condition, this shows a transient of small uninteresting triangular black bits at the top of the pattern, which all evaporate in a few steps, leaving thin stripes that persist.

When the two switch, the first passes large lengths of black to the other on some steps. These can be offset from one another, so they do not span the entire pattern width. They take time to evaporate under the other rule, if it is the one used (IC constant) over the next several steps. Meanwhile in the other direction, resolved black stripes passed to the otherwise alternating rule persist for a step and thus create offsets between repeating bands under the other rule.

The small deviations from simplicity - ability to "change phase" for the alternator, and gradually evaporating black blocks in the striped - cannot persist or create any variety in either half of the rule taken separately. But operating on the same data in succession, they can and do give rise to surprisingly intricate structures.

The two component ECA behaviors for this ICA are 55 and 141. 141 from a simple initial has a left moving edge that leaves behind a pattern of simple black stripes. From random initials, these become the small evaporating triangles of black at the top of the pattern.


Posted by: Jason Cawley

ICA 10089, incidentally, is composed of ECA rules 86 - which is rule 30 with right and left switched - and 57 - which gives a fairly elaborate but symmetric pattern from a single black cell, and rule 184 style nesting with random initials.

ICA 10028 is 86 and 50 composed. 50 gives a checkboard from a single black cell, and alternating stripes from small transient, evaporating white triangles from random initials - the same periodic behavior involved in the 34231 case but with black and white switched, and composed with rule 30 style randomness.

You can get the 2 component ECA rules (0-255) from a range 1 ICA number (0-65535) - in an admittedly messy, inelegant way - by using -


componentrules[rlno_] := 
{FromDigits[First[Transpose[Partition[
IntegerDigits[rlno, 2], 2]]], 2],
FromDigits[Last[Transpose[Partition[
IntegerDigits[rlno, 2], 2]]], 2]}





Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings