Commentary

Richard's commentary pertaining to each slide can be found by clicking the triangular icons (such as that to the left here) seen throughout the presentation.

Introduction & Overview

Even some of the simplest cellular automaton rules can produce patterns as intricate as any pattern we expect to be possible in nature.

Here we look at how the overall shapes produced by these simple rules grow.

There are many possibilities besides the familiar triangular shape.

We include investigations of many initial states, such as those that are made by changing a small group of cells on a periodic background pattern.

We will also look at the more specific question of what boundary growths are possible in theory, and find some useful answers.

Look at the patterns made by some simple cellular automata, and you can see all sorts of complicated features.

Some interesting elementary cellular automata:

Some of these features are quite intricate, and we can imagine measuring them in various ways. Perhaps we might count which sorts of features occur, and how often. But in the spirit of trying to do easy measurements first, what can we look at?

Well, one very easy thing to measure is the growth of the boundary of the pattern.

The Question:

What are the possible rates of growth for a given abstract system?

Look at patterns in the simplest cellular automata — one can see all sorts of complicated features.

However, one easy thing to measure is the growth of the boundary.

It is not immediately obvious what should be happening, and you end up getting some prettty
interesting behavior if you look far enough.

This question of what happens to the boundary, is one example of a very general question: "What are the possible rates of growth for a given abstract system?".

And this question is most interesting to ask when we use very simple rules, but otherwise make as few assumptions about the underlying rules as possible. Of course, cellular automata and other systems in NKS fit this description perfectly!

I should mention that another particularly relevant type of system, are the substitution systems, of Chapter 3 of the NKS book.

Before looking at results I should quickly clarify what I mean by the boundary of a pattern.

The "boundary" is defined for simple starting patterns only:

I just mean the left and right edges of the pattern produced, when the colors of a few cells are changed in an otherwise uniform "background" of cells.

As the second picture shows, it is a harder problem to try to talk about boundaries between parts of a pattern when we start from randomness. So I'll stick to looking at patterns like the one on the left.

If the background is a repeating pattern of cells, then just like for the uniform background, it is easy to define a boundary. The boundary points are simply the leftmost and rightmost cells that are different in color to what we otherwise expect the background to look like at those points.

So we can start with simple seed states on periodic backgrounds too.

Periodic background patterns

In both pictures the background settles down into a pattern different to the pattern it started in, but the boundary is still well defined.

And of course it helps to remember that if a pattern dies out, then the boundary does not exist.

-

Lets look at all the elementary cellular automata rules. These are the simplest possible rules, so they are a good starting point.

What do we find when we run each of them from a single black cell, on a background of white cells?  Here are some examples.

Some Elementary rules:

Even when we start from a uniform white background the background may change, making it harder to identify the boundary. So instead I like to plot the cells at which the pattern is different to the background, as the following slide shows.

Difference of patterns from backgrounds:

Knowing these pictures we can easily measure the widths of the pattern at each step. Note that if the pattern dies out, the width is defined to be zero.
Plotting the widths versus the number of steps gives the following pictures.

Widths of patterns:

What cases occur? There are basically four different cases that occur.

Firstly, the pattern can just die out, and the boundary disappears.

Secondly, the pattern can form a stationary or moving particle, and remain essentially constant. I say "essentially" constant, because there is often a small serated edge to these patterns. Although sometimes they are truly constant.

It is interesting to note that some of these rules tend to form very wide particle structures even from narrow initial seeds, like for rule 41. But the values of the width still settle down to essentially constant values.

Thirdly, the pattern can grow in an essentially linear way, like for rules 30 and 50
It is interesting to note that despite the fact that rule 30 has a complex internal pattern, it's edge is very simple, and there is a simple reason too.

Rule 30:

As you can see, any black cell on a white background must end up growing to the left. And similarly on the right side. So despite rule 30's complexity it's growth in this case is trivial.

Linear growth of rule 30

Finally, in exactly two of the 256 cases, the pattern is much more interesting.
These are rules 169 and 225. Both form a nested structure that grows proportional to the square root of the number of time steps. The following slide shows a skewed form of 225 showing the nesting better.

Rule 225 nested pattern

(Rule 225 skewed).

How often do these various cases occur?

About one in six, or 16% of the cases die out.

Half of the rules - the clear majority - are particles. By the way, I don't think for a minute there is any significance that this number is exactly one-half.  Lots of number in NKS seem to be essentially accidents of nature.

About one in three rules form the well-know triangular patterns. These linear growing patterns include six cases of combinations of slopes on each side. The pattern may not grow on one side, or it may grow at one cell or half a cell per step.

Finally the two rules 169 and 225 make less than 1% of the total. In fact the two rules are essentially the same, and are related by exchanging left and right.

What about wider simple seed patterns, but still on a white background?  Maybe things are more interesting?

We do find that often rules that either died, formed a particle, or formed a triangle, will tend to typically do one or more of the other of these things in latter initial conditions.

So I suppose it helps not to make detailed assumptions about a rule on the basis of it's first initial condition. Nevertheless, having seen the first few initial conditions we can almost always tell what a rule will always do.

But the only really new thing we see, is again for rules 169 and 225, and now the two other rules also equivalent to it, 106 and 120.

In their later initial conditions they often form complex looking patterns, rather than the nested structure we saw earlier.

Rule 225, complex growth

What about looking at periodic background patterns.

For each rule we can enumerate possible backgrounds and initial conditions are run the rule for each one. I tried all combinations of the first 30 initial conditions and 30 backgrounds for each rule. It includes all cell patterns up to a width of four cells in each case.

That means running 900 cases for each rule, which doesn't actually take long on todays computers.

A nice side-effect of this experiment is that you can ignor rules equivalent under left-right reflection and interchange of black and white, so only the 88 minimally-numbered inequivalent rules are considered.

To get a sense of all possible outcomes, even with so much data, we can just superimpose the line-plots for all cases for a rule onto one plot.

What do we find?

Two of the 88 cases, rules 0 and 8 always die out very quickly.

26 rules - that's about 30% - form particles but do nothing more. For some states some rules die out too.

Rule 1:

This is rule 1.

Rule 2:

And this is rule 2.

In the majority of the cases, that's 55 of the 88 rules, we get some linear growth, and most often also some of the initial conditions stay as particles.

Rule 6:

35 of the rules have a single linear growth rate, but 12 have two growth rates and there are single cases of 3 and even four separate growth rates.

Rule 54:

This is rule 54.

Rule 168:

And 168.

Then there are the really suprising cases.  Five rules end up doing rather interesting things.

Rule 30:

Rule 30 shows both order and disordered growth.

Rule 41:

Rule 41 shows linear growth. The band of growth in the middle is interesting. It seems to allow for a range of slopes.

Rule 45:

Rule 45 has long disorder transients onto linear growth.

Rule 106:

Rule 106 is just equivalent to rule 225. But it suprised me to see that it also allows linear growth as well as disordered growth.

Rule 110:

And here is rule 110.

I'd like to end by saying a little bit about what is theoretically possible. In other words what can we work out without doing computer experiments. Every CA evolution on an infinite line of cells must either die out, reach a cycle of states - and therefore never grow - or grow forever.

If the pattern does grow forever then what are the maximum and minimum growth rates?

The maximum rate of growth is just linear growth at one cell per step.  That is obviously just a consequence of the definition of cellular automata.

Maxiumum growth is linear

A nice example is rule 254.

The minimum growth rate is logarithmic.

Minimum growth rate is logarithmic

Why?

Because if we visit every state we grow as slowly as possible, and that happens to be logarithmic growth.

It's easy to see why that is.  The key thing is to recognise that if a cellular automaton ever reaches a state it has already been in then as I just mentioned it will get stuck in a cycle and never grow.

So a pattern that does grow forever may never visit the same state twice.

The "worst case" slowest growth possible would therefore be to visit every state exactly once, the narrow states and then the wide ones.

Last year at the NKS summerschool when I did some of this work, I was really excited to realize this.

And obviously such a sequence of states will grow logarithmically. I don't believe any actually CA can visit every state, but there are logarithmically growing CAs.

Some constructions: Binary counter CA

This one is just a binary counter. It's construction is similar to the circuits you find in every computer chip.

And in fact you can apply the same reasoning even to a finite amount of growth.

As for other growth rates. Well it turns out various constructions show that polynomial growth -- like the square root or the cube root of the number of steps is trivial to achieve.

Other growth rates:

Polynomial growth rates:
   Easy to get even in the "wild" of CAs.

Irrational growth rates: Matthew Frank's work.
   Fibonacci CA. An example of irrational growth.
   To many irrational numbers to get all of them, but we can do the algebraic numbers.

And Matthew Frank at the 2003 NKS summer school invented a CA based on the Fibonacci sequence that has irrational limiting growth.

See Matt's poster later at the conference for his latest work, which I think is very interesting.

But of course not all irrational numbers are possible, because there are an uncountable number of them, and only a countable number of CAs and their initial states.

But what is the fundamental reason that disordered looking boundaries are possible. Well the boundary cannot really generate it's own randomness - it just has too few cells!

So the real reason we can see disordered looking bondaries is that the main body of the pattern generates intrinsic randomness, and some of that randomness is transmitted to the boundary creating the irregularity.  It is interesting to notice that whenever the boundary grows as fast as possible it outruns the body of the CA and remains simple.

Undecidability and irreducibility

Whether or not a patterns grow forever or die out is in general undecidable, and that is a direct consequence of computational irreducibility.

Because the boundary is connected to the computation occuring in the body of the pattern, in general whether or not infinite growth occurs should be undecidable.

Summary

A few specfic things occur:

The results are that you end up with a small class of simple behaviors, and few complex things. With the simple things you can understand them completely, but the others may be connected to intrinsically hard computations.

Lessons learned:

The most interesting things found, were found by experiments alone.

Need to make general experiments to avoid coming to the wrong conclusions.

The results are that you end up with a small class of simple behaviors, and a few suprising complicated things.  With the simple things you can understand them completely, but the others will be tough.

And sure enough, I discovered it really is best to do experiments.  Most of the interesting things I would not have found without doing experiments.

Questions and Answers Time

Boundary Growth in Simple Cellular Automata