A New Kind of Science: The NKS Forum > Pure NKS > Cellular automata with global control
Author
Stephen Wolfram
Wolfram Research
Boston, MA

Registered: Oct 2003
Posts: 13

Cellular automata with global control

I was having dinner this evening with Paul Davies (http://aca.mq.edu.au/PaulDavies/pdavies.html), and we ended up doing a Mathematica experiment that I thought people on the Forum might be interested in hearing about.

Paul's work on astrobiology had led him to wonder whether perhaps living systems might be characterized by having rules that somehow depend on global features of their state.

I suggested that we try a little experiment to look at some minimal pure NKS systems with this property.

The idea was to have a system in which there are two possible cellular automaton rules, with the first rule being applied at a given step if the total number of black cells at that step is even, and the second rule being applied if the total number of black cells is odd.

In Mathematica, the evolution function is then:

GCA[{r1_, r2_}, init_, t_] :=
NestList[CellularAutomaton[{r1, r2}[[Mod[Total[#], 2, 1]]], #,
1, {-1}][[1]] &, init, t]

(Note that this uses the Mathematica 5 function Total.)

Now define (this is rather klunky, but it is what I wrote at dinner, so I reproduce it here):

AllCases[list_] :=
Union[Sort /@
Flatten[Outer[List, ##] & @@ Table[list, {Length[list]}]
Length[list] - 1]]

and

RasterGraphics[list_] := Graphics[Raster[Reverse[1 - list]], AspectRatio -> Automatic]

Then start looking at things like:

Show[GraphicsArray[{RasterGraphics[
GCA[#, ReplacePart[Table[0, {200}], 1, 100], 200]] & /@
AllCases[{30, 150}]}]]

The middle of these three pictures shows the result of "mixing" rules 30 and 150. It's a somewhat interesting "decorated" nested pattern.

An obvious question is: are there rules where each individual rule is simple, but the combination is not.

I started doing an exhaustive search. Quite soon we saw the case {11, 28} --- i.e. the combination of rules 11 and 28.

Starting from a single black cell it produces a rather remarkable pattern. There is considerable randomness, but there are strange patches and bursts of order.

There is a background of stripes, with a black stripe occuring whenever rule 11 gets applied after rule 28.

We tried to figure out whether there was regularity in this background. There did not seem to be. The frequency of stripes seemed, however, to converge to about 0.28, with fluctuations following roughly a random walk.

We then looked at what happens with random initial conditions. With an even width of system, randomness seems to persist. But with an odd width, it usually seems to die out rapidly, leaving distinctly class 2 behavior.

That was as far as we got in the half hour or so that we spent on this.

There are several obvious things to do.

First, finish the exhaustive search. Perhaps start by looking just at the 16 k=2, r=1/2 rules, and see if any combinations of them lead to interesting behavior.

Next, try to analyse the {11, 28} case more carefully. Look at difference patterns with random initial conditions. Look at various simple initial conditions, seeing how much effect they have on the final pattern produced.

We noted a few other cases that looked interesting: {14, 22}, {14, 28}, {17, 28}, {18, 28}, {22, 25}.

How common is class 4 behavior in these globally-controlled rules?

What happens with other forms of global control? In which one chooses the rule on the basis of other quantities, say as discussed in the NKS book, page 1022R.

I'm not sure to what extent this will all illuminate Paul Davies's original question---on which I have definite views, as expressed in Chapter 12. But I think cellular with global control are interesting systems that deserve to be studied, and will no doubt have interesting applications.

Attached is a picture of the {11, 28} case, as well as the raw notebooks we generated. (The first notebook I quit after it got to 129 megabytes in size.)

Attachment: gca.zip

Last edited by Stephen Wolfram on 10-14-2003 at 11:57 PM

Report this post to a moderator | IP: Logged

10-14-2003 05:47 AM
Shih-Kung Lai

Registered: Oct 2003
Posts: 5

External intervention on cellular automata

Perhaps an equally interesting question would be: How does external intervention with certain rules that are imposed on the 1-D cellular automata would affect the evolution? More specifically, we are conducting 1-D CA experiments with the original rule 110 by imposing an intervention rule of Bayesian decision rule for each cell periodically with different ranges of consideration. The preliminary result shows that complexity as measured by entropy decreases with increase in the range and frequency where the Bayesian decision rule is applied, implying that planning or decision making as manifested by gathering information through the Baysian decision rule external to the 1-D CA decreases complexity.

Report this post to a moderator | IP: Logged

10-24-2003 12:32 PM
Seth J. Chandler
University of Houston Law Center
Houston, Texas, USA

Registered: Oct 2003
Posts: 20

Economies as a possible example of CAs with Global Control

1. Economies might also have features of a cellular automaton with global control. One's behavior, for example, might be a function of the state of one's neighbors but also a function of global parameters of the system such as the supply of some quantity or some market price. I wrote an article years ago for an International Mathematica Symposium that took a look at such a system in the context of land use decisions, although post-NKS I now realize it was horribly and needlessly complex.

2. Is there any relationship between the results of these CAs with global control and composed CAs in which one rule is deterministically applied after another regardless of the state of the automaton?

3. Also, while folks are playing around with these CAs with global control, one might try conditions other than "Even" for determining which CA rule to apply. (Granted fully that "Even" has the great virtue of simplicity). Just for the heck of it, however, I played around with the primality of the total (applying the first rule if it was prime and the second rule if it was not) and I got some attractive results (whose meaning is completely beyond me). The evolution of the system evolving from seed sometimes seems to take on very different characteristics, for example, depending on the width of the initial configuration.

GCA[{r1_, r2_}, init_, t_, f_:Function[Mod[Total[#],
2, 1]]] := NestList[CellularAutomaton[{r1, r2}[[f[#]]], #,
1, {-1}][[1]] &, init, t]

Table[Show[RasterGraphics[GCA[{145, 70}, ReplacePart[Table[
0, {systemwidth}], 1,
Ceiling[systemwidth/2]],
600, If[PrimeQ[Total[#]], 1, 2] &]]], {systemwidth, 139, 143}]

Report this post to a moderator | IP: Logged

10-24-2003 01:36 PM
Jim Propp
University of Wisconsin

Registered: Oct 2003
Posts: 2

Cellular automata with global control

Here's one sort of cellular-automaton-with-global-control that might be worth thinking about: two cellular automata running in tandem (call them A and B). Automaton A runs in the ordinary local fashion, and some global (or local) property of A is used as the extra bit that tells B which of two rules to apply.

A very special case of this (but one which I think has some theoretical interest) is to have A be rule 110, with the center bit serving as the global control for B, and to have the two rules for B be inverses of each other. Then if we just look at the behavior of B, it'll be doing a sort of (reversible) computation, but one in which the system "randomly" takes as many steps backwards as forwards.

I suggest this setup not because it will exhibit surprising behavior, but because it might require us to clarify (and perhaps enlarge) the notion of what it means to use a CA to answer a question, and to recognize when a computation has finished.

Report this post to a moderator | IP: Logged

10-26-2003 01:32 AM
Seth J. Chandler
University of Houston Law Center
Houston, Texas, USA

Registered: Oct 2003
Posts: 20

Global Control on Neighborhoods and not rules

Here's a musing on Wolfram's original post that might interest some. What if the global feature of the automaton doesn't affect the update rule but does affect the neighborhood over which the rule operates? Consider, for example, an k=2, r = 1/2 GCA that looks at itself and its left neighbor if the number of black cells is even but that looks at itself and its right neighbor if the number of black cells is odd. Now, I suppose that this may be functionally identical to a GCA with two k=2, r=1 rules that looks at the union of neighbors examined by any particular r=1/2 rule, but I think this alternative characterization of the automaton's update procedure might (a) be a simpler description for more complex cases and (b) correspond to intuition regarding some physical or economic phenomenon.

Anyway, here's some code that implements the idea and shows some pretty complex behavior that emerges from a GCA that deploys a k=2 r=1/2 rules. I've included the two "interesting" cases. I have no earthly idea what these GCAs are "computing," but it sure looks elaborate. I see lengthening cycles that move from what appears to be simple nesting to complexity and then suddenly move back to what appears to be simple nesting.

GCA[{r1_, r2_}, init_, t_, f_:Function[Mod[Total[#],
2, 1]]] := NestList[CellularAutomaton[{r1, r2}[[f[#]]], #,
1, {-1}][[1]] &, init, t]

Show[RasterGraphics[GCA[{{6, 2, {{0}, {-1}}}, {
6, 2, {{0}, {1}}}}, ReplacePart[Table[
0, {401}], 1,
Ceiling[401/2]], 10000]]]

Show[RasterGraphics[GCA[{{9, 2, {{0}, {-1}}}, {
9, 2, {{0}, {1}}}}, ReplacePart[Table[
0, {401}], 1,
Ceiling[401/2]], 10000]]]

__________________
Seth J. Chandler
Foundation Professor of Law
University of Houston Law Center
Houston, Texas 77204

Report this post to a moderator | IP: Logged

11-14-2003 09:41 PM
Seth J. Chandler
University of Houston Law Center
Houston, Texas, USA

Registered: Oct 2003
Posts: 20

Networked Global Cellular Automata

A global cellular automaton (GCA) is a cellular automaton in which the evolution of each site is a function not only of the values of the site's neighbors, but also of certain global features of the automaton. The notebook attached to this post explores an extension of GCAs in which each GCA is connected to other GCAs and each site of each GCA evolves not only according to the value of its local neighbors but also according to its own global features and those of its neighboring GCAs. The concept may be useful in thinking about the interaction of computing systems or complex agents. Composed cellular automata and GCAs of the sort originally described by Wolfram in this thread may be thought of as special cases of the more general approach taken in this notebook. This notebook provides a draft of ways in which this concept can be implemented in Mathematica. The code appears to be relatively speedy and almost as general as Mathematica's underlying CellularAutomaton function.

The ideas and implementation described here are in their infancy. Constructive comments welcome. My thanks to Jim Propp for his post to this forum, which stimulated my thinking on the issue.

Attachment: gcanetworks.nb

__________________
Seth J. Chandler
Foundation Professor of Law
University of Houston Law Center
Houston, Texas 77204

Report this post to a moderator | IP: Logged

12-09-2003 01:11 AM
Jim Propp
University of Wisconsin

Registered: Oct 2003
Posts: 2

Cellular automata with global control

It's worth mentioning that a much-studied class of discrete models, namely chip-firing or avalanche models, fits more naturally into the framework of CAs when a mechanism for global control is introduced. Such models typically have two sorts of states: unrelaxed and relaxed. A relaxed state, in the absence of any external stimulus, does not change at all from one time-step to the next. So to make things interesting one needs a global monitor-and-control mechanism that detects when the system has achieved a relaxed state and introduces a perturbation.

One of my favorite examples of this is the chip-firing game in which each site of an infinite two-dimensional lattice can accomodate any number of chips but "wants" no more than three: a site with four or more chips gives a chip to each of its neighbors. One can show that if the number of chips in the system is finite, it must eventually reach a relaxed state. What's interesting is what happens when you add lots of chips at one location in an initially empty system (adding a new chip each time the system becomes relaxed). To see what the system looks like after sixty thousand grains have been added, see the picture at www.math.wisc.edu/~propp/hidden/501.gif (created by Vishal Sanwalani). Many people would like to know the limiting behavior of the growing blob of occupied sites.

Another example is my "rotor-router aggregation model", in which the chips are routed through the system in accordance with rotating arrows associated with the individual sites (see http://www.mathpuzzle.com/29Jun2003.html for Ed Pegg's nice write-up). If you look at Ander Holroyd's picture of the rotor-router blob after 1,000,000 chips have added to the system, available at www.math.wisc.edu/~propp/million.gif , I think you'll agree that the blob is "trying" to be circular, but a rigorous proof has not been found. (You can learn more about this model at http://murl.microsoft.com/LectureDetails.asp?1050 ; if you have a high-speed link, you can view a video of a 50-minute lecture on this and related models. Or, if you'll be at the upcoming AMS/MAA meeting in Phoenix, you can hear me speak on this topic there on Jan. 7 at 5:15 p.m.: see http://www.ams.org/amsmtgs/2078_program_ss13.html#title.)

Report this post to a moderator | IP: Logged

01-02-2004 04:36 AM
Jonas Karlsson

Registered: Apr 2005
Posts: 1

other global quantities

It would be interesting to examine global cellular automata with other global quantities than the parity and primality of the number of black cells (with k=2). More realistic quantities (i.e., more likely to occur in real applications) include the number of cells with a certain value or the difference between the number of black and white cells (compare p. 432 in A New Kind Of Science). One would then have a critical value for the quantity in question, and apply different rules depending on whether or not the quantity exceeds the critical value. Clearly, both these choices are equivalent to taking the quantity to be the density of the configuration (defined as the fraction of black cells).

For the behaviour to be nontrivial, the rules and the critical density must be chosen so that both rules are applied. One possible case is to let the rules be the elementary rules number 110 and 20, and have a critical density around 0,5.

This kind of systems seem, as pointed out by Seth Chandler, suited to model economies and related systems. Is anyone aware of any work along this line?

Report this post to a moderator | IP: Logged

04-09-2005 06:42 PM
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.

I'll post a notebook on these shortly, for those who want to explore them themselves.

Report this post to a moderator | IP: Logged

04-11-2005 07:37 PM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Here is a notebook for working with ICAs.

Attachment: ica5.nb

Report this post to a moderator | IP: Logged

04-11-2005 07:47 PM
Seth J. Chandler
University of Houston Law Center
Houston, Texas, USA

Registered: Oct 2003
Posts: 20

Demonstration on GCA now available

I have put a demonstration of GCA (global control cellular automata) at http://demonstrations.wolfram.com/C...hGlobalControl/ . To interact with it, you will need to download the free Mathematica Player (http://www.wolfram.com/products/player . ) Once you have the Mathematica Player, you can also download the underlying Mathematica code, which actually accomodates somewhat more complex scenarios than those shown in the demonstration, including what has been termed an Interactive Cellular Automaton (ICA).

__________________
Seth J. Chandler
Foundation Professor of Law
University of Houston Law Center
Houston, Texas 77204

Report this post to a moderator | IP: Logged

05-12-2007 12:14 AM
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 103

I like Seth's demo.

It seems like the compositions (the diagram on the right)
have more structure to them than the ordinary evolutions.

Report this post to a moderator | IP: Logged

05-16-2007 10:04 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us