Growth and Decay in Life-Like Cellular Automata

If I haven't been posting much here in the last couple of weeks, it's because too much of my writing energy has been going into writing actual papers. Here's one of them: Growth and Decay in Life-Like Cellular Automata, arXiv:0911.2890. The aim of the paper is to predict which two-dimensional cellular automaton rules will behave similarly to Conway's Game of Life. But a large part of the difficulty in making this sort of prediction is finding the right definition of "similarly".

A standard method for classifying automata, due to Wolfram, is to look at the behavior of the automaton on random initial conditions. Very roughly speaking, four outcomes are possible: the field can go from random to uniform, it can develop scattered still life and oscillator patterns but without any persistence of long-term complex behavior, it can remain random, or something else can happen. That "something else" supposedly describes Life, although really it seems that Life develops scattered still lifes and oscillators but just does it more slowly than some other rules.

From my point of view, I'm not so concerned with random inputs. There are interesting things to say about Life's behavior on random initial conditions, but it's the non-random inputs that more fascinate me, the ones with some structure to them like the caterpillar and metapixel that are far too big to be found in practice by a random search (despite the theoretical truth that every possible pattern happens in a large enough random field). From this point of view Wolfram's classification is unsatisfying: these large structured patterns with interesting behavior can be found in many different rules that have very different behavior on random inputs. It's also overly subjective (why is Life Class IV and not Class II?) and unpredictive — it doesn't tell you in advance how a rule is going to behave, it only serves to describe the behavior you've already observed.

So a large part of the new paper describes a very crude classification that despite its crudity works better for my purposes: automata are grouped into four classes according to whether they support patterns that can grow beyond any bounding box enclosing them, and whether they support patterns that can die out completely. The interesting rules are likely to be the ones for which both answers are yes, and we can classify the vast majority of rules without having to look at the individual behavior of each one.

After defining this classification and using it to map out the rule space, the rest of the paper catalogues a collection of rules that support the complex patterns I'm looking for. One standout here is B013468/S02, which supports many small spaceships and oscillators and has a glider gun much smaller than the one in Life. It's also interesting from the Wolfram random-start point of view: when seeded with a random field (best with 46% live cells and 54% dead ones), it develops into large regions of cells alternating at each step between being alive and dead, each crisscrossed by large numbers of gliders, puffers, and other patterns sent out from the chaotic boundaries between regions of different phases. Because these boundaries gradually lose their curvature over long time scales, the number of steps before this system stabilizes to scattered oscillators is much higher than it is in Life.

(See also)

Comments: