CA Growth Rates: A Live Experiment

Posted to the NKS Forum March 29, 2005
Read Forum Thread

A few weeks ago I spent a week doing another small burst of lecturing. I was supposed to be visiting architecture schools (which was rather interesting, but that's a different story). But a lot of other venues got added too...

The last talk on the last day was a mathematics colloquium at Rutgers. And being quite tired, I wanted to do something envigorating. So I decided to try a live computer experiment.

The topic I picked was one I'd been curious about for a while: what rates of growth can patterns produced by 1D cellular automata have?

Something like rule 30 grows by one cell on each side at each step. Rule 45 effectively grows by half a cell on the left. And, at least with k colors, it's fairly easy to find rules that grow at fixed rational rates of n/k cells/step.

The "power" cellular automaton on page 614 (corresponding to taking powers of 3 in base 6) grows at Log[6, 3] cells/step. And I expect that various logs of algebraic numbers and so on should appear in CA growth rates.

But looking through the book, one also sees examples of rules that grow sporadically, sometimes eventually stopping altogether (e.g. the k=3, r=1 totalistic code 1599 on pages 70 and 740; see also page 754).

But what about rules that go on growing forever? What forms of growth can they have?

It's easy to see that for a range-r rule, the maximum distance reached after t steps is r t, corresponding to growth at a fixed rate of r cells/step. But other cases are certainly possible.

For example, rule 225 (see page 58) has Sqrt[t] growth.

It's fairly easy to see that the minimum rate at which the pattern from a k-color cellular automaton can grow is Log[k, t]. (I think this was first pointed out to me by Richard Phillips at the 2003 NKS Summer School.)

But I suspect there are all sorts of growth rates possible.

So what are they?

Well, following standard NKS methodology, the first thing is to do an experiment. And the obvious first experiment is to look through the simplest cellular automata, and see what growth rates they have.

And this is what I embarked on doing at my Rutgers live experiment.

Before I got started someone asked "how could this not have been investigated before; it's such an obvious thing?". "Well", I said, "that's something great about NKS: there are so many obvious questions that have never been investigated before". I went on to try to explain that coming up with obvious questions may not be quite as easy as it seems. It requires clear thinking to come up with something that's really simple---and the right thing to investigate.

Still, with this out of the way, we got down to experimenting.

It was an interesting dynamic. The room was full mostly of older math professors---for whom this was a very alien experience.

In general, academic mathematicians tend to avoid saying anything unless they can prove that what they're going to say is correct. So the live experiment started with a rather silent---and in some cases rather skeptical---audience.

I started off looking at the elementary cellular automata.

I defined:
LHEdge[ru_, t_] := If[Length[#] > 0, #[[1, 1]], 0] &[Position[#, 1, 1, 1]] & /@   CellularAutomaton[ru, {{1}, 0}, t, {All, All}]

as a way to pick out the position of the left-hand edge of the pattern.

Then I did:
Union[Table[-Differences[LHEdge[i, 20]], {i, 0, 255, 2}]]
to look at all elementary cellular automata that leave the background invariant.

The result was a list of 6 elements, all corresponding to either no growth, or growth at exactly 1 cell/step.

OK, so now the question was: what should we look at next?

I decided to keep the number of colors fixed at 2, but to increase the number of neighbors: in effect to look not at k=2, r=1 CAs, but instead at k=2, r=3/2 ones.

There are 2^2^4, or 65536 of these.

I decided to live dangerously, and just look at all of them.

So I typed:
Union[Table[-Differences[LHEdge[{i, 2, {{-1}, {0}, {1}, {2}}}, 20]], {i, 0,    2^16 - 1, 2}]]
At first, I was getting a little worried, and I started to tell a distracting story to pass the time. But before too long my laptop did its thing, and a result came back.

The list was of length 595.

I started explicitly plotting some of the elements of the list.

Most showed one or another kind of periodicity.

The first one that didn't was rule 10008.

And that one looked remarkably complicated.

A plot of the edge (10008edge.gif) looked quite jagged. And the whole cellular automaton evolution (10008evol.gif) looked pretty random---like rule 30.

Well, at this point the audience was starting to get a lot more interested. People were really surprised that we could find such irregular behavior so easily.

And I would have been surprised too, had I not been doing these kinds of experiments for 25 years...

Well, as always happens, people couldn't believe that what they were seeing was really random. So they kept on asking about one kind of regularity or another.

We did a fit, and found that the growth rate was on average around 0.10 cells/step.

Someone thought they saw periodicity in the pattern. So we did a Fourier transform. Nothing.

Someone thought they could figure out what was happening by looking directly at the underlying rule. I displayed it for them. But after a few minutes they agreed that, no, they really couldn't tell anything directly from the rule.

People seemed to be getting a little bit of the idea of what one can find in the computational universe. And they seemed to be getting fairly excited about it.

Well, after a few more minutes looking at 10008, I decided to see what other kinds of growth we could find.

Out of the 595 distinct edge patterns, it seemed as if a lot were just repetitive in some way. I wanted to filter those out. So as a coarse way to do that, I did the following:
Select[Range[0, 2^16 - 1, 2], Length[Union[      Partition[-Differences[LHEdge[{#, 2, {{-1}, {0}, {1}, {2}}}, 50]], 2,       1]]] > 6 &]

Just around that time my host (Doron Zeilberger) asked whether this was really a show---or whether I really didn't know what was going to happen. I explained that no, this really was exactly as advertised---a live experiment where I had no idea what was going to happen.

Meanwhile the computation above was still running. And someone asked how many rules I thought would survive the filter. I guessed about 200.

So then I was a little embarrassed when the number ended up being 161. I was surprised I'd managed to guess so well. And I quickly explained that I've been doing experiments like this for a long time---and I've gotten fairly good at estimating these things.

Well, the results were quite interesting. A very varied collection of patterns of growth (growths.gif).

With some complex forms of periodicity. But quite a lot of rules that show very 10008-like behavior.

Well, I didn't expect that there would be much traditional math that we could successfully do on that kind of behavior. And since the audience was mathematicians, I really wanted to show them a case where their methods could make some progress.

I looked through the pictures of growth patterns, and found one rule that seemed more promising: 43940.

Looking at the pattern produced by this rule, one can see nice nesting (43940evol.gif).

But what's the actual rate of growth? I was just about to figure this out ... but the hour (or so) ran out, and I had to stop.

By this point, though, I had the impression that the audience was quite into the whole process. People were offering all sorts of suggestions, and some of them seemed rather disappointed that we had to stop.

I had to leave fairly quickly, but had a chance to talk to a few people.

One of them was an older math professor who asserted indignantly that what I'd been doing was "recreational mathematics". My initial, flippant, answer was: "yes, it's fun; math can be that". But his more serious (and reasonable) question was: "What's the point of studying all this stuff? What is it connected to?".

Well, of course that's what a lot of the NKS book is about : showing that studying the computational universe is connected to many many things. So that "pure NKS" really is worthwhile. (Unfortunately the individual who asked the question hadn't come to the general NKS talk I'd given a few hours earlier.)

I've done a few live experiments before, but in most cases to rather NKS-attuned audiences. This was an experiment with a rather different kind of audience. And at least my impression was that it went well.

And, most of all, we actually discovered something pretty neat: that there are k=2, r=3/2 CAs with irregular growth.

One of the features of live experiments is that (if you set the correct notebook options) you can tell exactly when you discover things. So I know that rule 10008 was first seen at 5:02 pm ET on February 18, 2005.

We're sending the Rutgers math department a big printout of rule 10008, with a little caption saying that it was discovered at their colloquium.

I had fun with all this, and I'm hoping there'll be lots more "live experiment artefacts" generated over the coming years.

Actually, we have a plan that I may do some webconferenced live experiments for the NKS community on a regular basis---but that should be the subject of another post.

There's also a lot more to discover about irregular growth in simple cellular automata, and I hope other people will work on this too.