Analyzing simple systems

Øyvind Tafjord, Wolfram Research

Outline of talk:

What's an experiment in NKS about?

Consider your typical experiment on a system in the natural sciences:

1)  Decide what property of the system to study
	2)  Design apparatus with study goal in mind
	3)  Collect data
	4)  Analyze data, with particular emphasis on possible sources of unwanted noise
	5)  Draw conclusions
	
Now, what's different about an experiment on a system in the computational world, the world of NKS ?

1)  Start by doing lots of simple, visual experiments without worrying too much about what you're looking for
	2)  Keep an open mind and visually sift through the result, looking for interesting features
	3)  Study the interesting features more closely, even quantitative if possible
	4)  Never worry about experimental noise, the results are exact
	5)  Draw as general conclusions as possible, build intuition about what simple programs can do.

Selecting a system to study

There are basically two motivations for studying simple programs:

	1)  Try to come up with a model for a specific system in Nature
	
	2)  Study a simple program for its own sake, NKS "basic research"

In both cases the same principle applies: choose your system as simple as possible - then make it simpler. No fluff!

If your simple system then turns out to always have trivial behavior (but make sure!), you have a lower bound on how simple it can be, and you can go from there.

Example: Cellular automata with 2 colors and 2-cell neighborhoods (A New Kind of Science, page 885). These can give nested behavior, but nothing more. Move to 3-cell neighborhoods, and ta da!, the level of complexity explodes and we've got rule 30 and rule 110 and all their friends.

CellularAutomaton[ ]

Once you have a system to study, you need code to run it. Mathematica is perfect for writing such code quickly and efficiently.

But if you're just starting out poking around in the computational world, why not get your feet wet with a cellular automaton system or two. They are so rich, with much unexplored territory among them. Better yet, they're efficiently implemented in Mathematica 4.2 and later, so you can quickly do big experiments without worrying about making your code faster.

Let's do a quick tour of some cellular automaton systems, and sticking to the virtue of simplicity, we'll stay in one dimension:

Here's how you elementary CA rule 30, starting from a single black cell, for 5 steps

CellularAutomaton[30, {{1}, 0}, 5]

Black is represented by 1 and white by 0. The first list in the above array shows the initial condition as 5 0's followed by a 1 and then 5 more 0's. That is, a black cell surrounded by all white. CellularAutomaton[ ] has automatically chopped off the sides to fit the evolution perfectly. To display this, we need an auxilliary function, something like

RasterGraphics[state_, colors_:  2, opts___] := 
      Graphics[Raster[Reverse[1 - state/(colors - 1)]], opts, 
        AspectRatio -> Automatic]

Show[RasterGraphics[CellularAutomaton[30, {{1}, 0}, 5], 2]]

The general form of the function is CellularAutomaton[rule, init, steps, showregion], where the showregion part is optional. In our case above, rule is simply 30, signifying an elementary CA. The initial condition can be of two types: fixed width or fixed background. In the case above, {{1},0} means a black cell in a fixed background of 0's. Let's try another initial condition:

Show[
      RasterGraphics[CellularAutomaton[30, {{1, 1, 0, 1}, 0}, 5], 
        2]]

More steps:

Show[RasterGraphics[CellularAutomaton[30, {{1}, 0}, 50], 2]]

Here's a fixed width, random initial condition:

Show[
      RasterGraphics[CellularAutomaton[30, Table[Random[Integer], {80}], 50], 
        2]]

Or what about rule 110:

Show[
      RasterGraphics[
        CellularAutomaton[110, Table[Random[Integer], {300}], 150], 
        2]]

Now let's venture out to some other friends from A New Kind of Science. Some of the more spectacular pictures in the book come from 3-color totalistic rules. Let's try one:

Show[
      RasterGraphics[CellularAutomaton[{1635, {3, 1}}, {{1}, 0}, 10], 
        3]]

Now the rule part is more complicated. {1635,{3,1}} means code 1635, 3 colors and a totalistic rule. Let's do some more steps!

Show[
      RasterGraphics[CellularAutomaton[{1635, {3, 1}}, {{1}, 0}, 400], 
        3]]

Wow! Isn't that something. Now this picture isn't as nice as the one in the book, mostly because the pixels on the screen are not correlated with the cells in the CA. Here's a little trick to fix that:

NiceRasterGraphics[state_, colors_:  2] := 
      With[{dim = Reverse[Dimensions[state]]}, 
        Graphics[Raster[Reverse[1 - state/(colors - 1)]], 
          AspectRatio -> Automatic, 
          PlotRange -> {{0, dim[[1]]}, {0, dim[[2]]}}, 
          ImageSize -> dim + 1]]

Show[
      NiceRasterGraphics[CellularAutomaton[{1635, {3, 1}}, {{1}, 0}, 400], 
        3]]

The optional showrange argument to CellularAutomaton can be used to restrict which cells to show, both in the time and space directions:

Show[
      NiceRasterGraphics[
        CellularAutomaton[{1635, {3, 1}}, {{1}, 0}, 
          600, {All, {-200, 200}}], 3]]

This showed all steps in the time directory, but only range {-200, 200} in the space direction (where position 0 is the location of the initial cell).

Finally, let's look at a 2-color, range-2 totalistic CA:

Show[
      RasterGraphics[CellularAutomaton[{6, {2, 1}, 2}, {{1}, 0}, 20], 
        2]]

These guys can grow really fast horizontally. The fact that they're range-2 is coded in the third argument of the rule {6,{2,1},2}. A really cool one is code 20:

Show[
      NiceRasterGraphics[
        CellularAutomaton[{20, {2, 1}, 2}, Table[Random[Integer], {400}], 
          200], 2]]

Let's experiment!

OK, let's do some experiments with the 2-color range-2 cellular automata. Come to think of it, why don't we make it even simpler and look at the 2-color range-1 guys... Can there be anything interesting to learn from them?

These automata take three neighbors and return a new cell based on the sum of the three neighbors. Since this sum can be 0, 1, 2, or 3, we need to specify four numbers (0 or 1) to give the rule, so there are (2^4) = 16 such rules. Let's check out one of them:

Show[
      RasterGraphics[
        CellularAutomaton[{10, {2, 1}}, {{1}, 0}, 10]]]

IntegerDigits[10, 2, 4]

So this rule specifies that the new cell is black whenever the sum of the three neighbors is equal to 1 or 3.

The first step in any NKS experiment is to look at the behavior of a large range of rules. In this case there are only 16 of them, so it's easy to look at them all:

Show[
      GraphicsArray[
        Partition[
          Table[RasterGraphics[
              CellularAutomaton[{i, {2, 1}}, {{1}, 0}, 30, {All, All}], 2, 
              PlotLabel -> i], {i, 0, 15}], 4]]]

We see some nested patterns, but nothing much beyond that. An interesting exercise would be do derive explicit formulas for each of these patterns.

Another obvious thing to do is show the evolutions from random initial conditions:

Show[
      GraphicsArray[
        Partition[
          Table[RasterGraphics[
              CellularAutomaton[{i, {2, 1}}, Table[Random[Integer], {100}], 
                60], 2, PlotLabel -> i], {i, 0, 15}], 4]]]

I wonder if something interesting happens if we start with fewer or more black cells in the initial condition (maybe there are phase transitions...)? Let's try 20% black:

Show[
      GraphicsArray[
        Partition[
          Table[RasterGraphics[
              CellularAutomaton[{i, {2, 1}}, 
                Table[If[Random[] <  .2, 1, 0], {100}], 60], 2, 
              PlotLabel -> i], {i, 0, 15}], 4]]]

And 80% black:

Show[
      GraphicsArray[
        Partition[
          Table[RasterGraphics[
              CellularAutomaton[{i, {2, 1}}, 
                Table[If[Random[] <  .8, 1, 0], {100}], 60], 2, 
              PlotLabel -> i], {i, 0, 15}], 4]]]

Code 4 has at least one type of persistent structures, perhaps it has more?

Show[
      NiceRasterGraphics[
        CellularAutomaton[{4, {2, 1}}, Table[Random[Integer], {400}], 
          100]]]

Looks like they're always two pixels wide... (Exercise: can you figure out why by looking at the actual rule?)

Anyway, I kind of like code 5, let's look at it again:

Show[
      RasterGraphics[
        CellularAutomaton[{5, {2, 1}}, {{1}, 0}, 30]]]

This is kind of neat. It looks nested, but a bit unusual. The fact that the background flips on every second step is a bit distracting, let's try to invert the colors on every other step:

Show[
      RasterGraphics[
        MapIndexed[If[Mod[#2[[1]], 2] == 0, 1 - #, #] &, 
          CellularAutomaton[{5, {2, 1}}, {{1}, 0}, 30]]]]

Hey, that looks awfully familiar - it looks like code 10!

Show[
      RasterGraphics[
        CellularAutomaton[{10, {2, 1}}, {{1}, 0}, 30]]]

Wonder if they could actually be the same thing, after doing the color-flipping thing... Let's try the random initial condition:

Show[
      RasterGraphics[
        MapIndexed[If[Mod[#2[[1]], 2] == 0, 1 - #, #] &, 
          CellularAutomaton[{5, {2, 1}}, Table[Random[Integer], {100}], 
            60]]]]

Show[
      RasterGraphics[
        CellularAutomaton[{10, {2, 1}}, Table[Random[Integer], {100}], 
          60]]]

Looks qualititavely similar, how can we do better? Use SeedRandom!

SeedRandom[1234]; 
    Show[RasterGraphics[
        MapIndexed[If[Mod[#2[[1]], 2] == 0, 1 - #, #] &, 
          CellularAutomaton[{5, {2, 1}}, Table[Random[Integer], {100}], 
            60]]]]

SeedRandom[1234]; 
    Show[RasterGraphics[
        CellularAutomaton[{10, {2, 1}}, Table[Random[Integer], {100}], 
          60]]]

Yup, they look identical. To make sure, let's have Mathematica check:

(SeedRandom[1234]; 
        MapIndexed[If[Mod[#2[[1]], 2] == 0, 1 - #, #] &, 
          CellularAutomaton[{5, {2, 1}}, Table[Random[Integer], {100}], 
            60]]) === (SeedRandom[1234]; 
        CellularAutomaton[{10, {2, 1}}, Table[Random[Integer], {100}], 
          60])

So we have discovered something! Code 5 and code 10 are identical, after inverting the colors on every second step in one of them! We could now try to give a formal proof of this equivalence. If must be related to the details of the rules:

IntegerDigits[5, 2, 4]

IntegerDigits[10, 2, 4]

Aha... A clear pattern here... 

Exercise: figure out the condition on the rules for them to be equivalent when inverting the colors on alternate steps. 
Answer: If the 4 digits in a rule is {x,y,z,w}, then one of the rules must have the form r1={x,y,1-y,1-x} and the other must be the inverse, r2=1-r1. We see that 5 and 10 satisfy this, is there another pair? Yes, {1,1,0,0} and {0,0,1,1}, i.e., codes 12 and 3. Let's check:

SeedRandom[1234]; 
    Show[RasterGraphics[
        MapIndexed[If[Mod[#2[[1]], 2] == 0, 1 - #, #] &, 
          CellularAutomaton[{3, {2, 1}}, Table[Random[Integer], {100}], 
            60]]]]

SeedRandom[1234]; 
    Show[RasterGraphics[
        CellularAutomaton[{12, {2, 1}}, Table[Random[Integer], {100}], 
          60]]]

Yup!

Advanced exercise: Figure out the same equivalences for the 2-color, range-2 totalistic cellular automata. Use a theoretical approach or an experimental approach (or both!), as suits your preferences.

Advanced exercise 2: Find similar equivalences for the elementary cellular automata. Use your answer to show that the 88 "fundamentally inequivalent" rules (A New Kind of Science, page 57) can in fact be reduced to 82.

Summary

We saw how looking at even the simplest of systems could lead to new discoveries. So just remember:

1) Even the simplest systems can be interesting to study.

2) Just follow your nose, make lots of pictures, look for interesting stuff, and dig in.

3) Once you're on track of something that seems interesting, focus on it, make more pictures, form hypotheses and test them.

4) Draw conclusions, figure out theoretical proofs or quantitative results if possible.

5) Have fun as your roaming around in this vast computational world. You might even be the first human ever in that corner of it!