Fates of Finite Chaos

It’s been a slow start on this blog. There was at a point a plan I had for a series of articles, but perhaps it will be more productive if I simply start writing about topics in no especial order.

So, an observation on “chaotic” cellular automata. These are some of the less understood CA I think, for the simple fact that there’s no fixation point, no attractor pattern types that we can see emerging (and then catalogue and perhaps manipulate). The basic property that gives them this power is however the fact that patterns keep growing — faster than any pseudorandom churn within their active region manages to end up at any kind of stable points. But this does not mean that the rule is incapable of containing any stable points. Quite a few chaotic rules after all allow for some still lifes, oscillators or spaceships. Those that don’t, such as B1 rules, will be still likely to at least allow for agars, stable or oscillating.

Agars in mind, we can in particular consider, instead of patterns’ behavior in infinite space, also patterns’ behavior in finite space. This will necessarily tame any pattern into at least an oscillator. In principle, such an oscillator could be a chaotic loop around an astronominally large phase space (even something quite small like a 10×10 box will allow circa 2^100 different patterns). In practice, this does not seem to be what happens, though.

Consider the following 12×12 seed and its fate in some well-known chaotic rules:

x = 12, y = 12, rule = B2/S:T12,12
2obob3o2b2o$3bob2obo2bo$2bobo2b2o2bo$3bob
ob2o2bo$2o6b4o$2obobobo$obobob2obobo$bo2b
ob3o$b4o2b2o$3o2bo4b2o$bo3b3o2b2o$b4ob5o!

Seeds (B2/S): Stabilizes into 3 duoplet oscillators at gen 458,748.

x = 12, y = 12, rule = B2/S0:T12,12
2obob3o2b2o$3bob2obo2bo$2bobo2b2o2bo$3bob
ob2o2bo$2o6b4o$2obobobo$obobob2obobo$bo2b
ob3o$b4o2b2o$3o2bo4b2o$bo3b3o2b2o$b4ob5o!

Live Free Or Die (B2/S0): Completely dies off by gen 4. (Possibly a fluke — gen 1 already leads to the rule evolving into just a population of 6, in 2 clusters which both happen to be plus spark precedessors.)

x = 12, y = 12, rule = B234/S:T12,12
2obob3o2b2o$3bob2obo2bo$2bobo2b2o2bo$3bob
ob2o2bo$2o6b4o$2obobobo$obobob2obobo$bo2b
ob3o$b4o2b2o$3o2bo4b2o$bo3b3o2b2o$b4ob5o!

Serviettes (B234/S): Population hits a minimum of 5 at gen 54,501, evolution follows S2 symmetry from there on. Stabilizes as a mostly line-based p2 agar relatively soon afterwards, at gen 55,801.

x = 12, y = 12, rule = B3/S023:T12,12
2obob3o2b2o$3bob2obo2bo$2bobo2b2o2bo$3bob
ob2o2bo$2o6b4o$2obobobo$obobob2obobo$bo2b
ob3o$b4o2b2o$3o2bo4b2o$bo3b3o2b2o$b4ob5o!

DotLife (B3/S023): Stabilizes as two dots, dot on preblock, tub, and beehive at gen 313 (final pop. 16).

x = 12, y = 12, rule = B37/S23:T12,12
2obob3o2b2o$3bob2obo2bo$2bobo2b2o2bo$3bob
ob2o2bo$2o6b4o$2obobobo$obobob2obobo$bo2b
ob3o$b4o2b2o$3o2bo4b2o$bo3b3o2b2o$b4ob5o!

DryLife (B37/S23): Stabilizes as four blinkers at gen 144 (final pop. 12).

x = 12, y = 12, rule = B3/S45678:T12,12
2obob3o2b2o$3bob2obo2bo$2bobo2b2o2bo$3bob
ob2o2bo$2o6b4o$2obobobo$obobob2obobo$bo2b
ob3o$b4o2b2o$3o2bo4b2o$bo3b3o2b2o$b4ob5o!

Coral (B3/S45678): Completely dies off by gen 10.

x = 12, y = 12, rule = B34/S34:T12,12
2obob3o2b2o$3bob2obo2bo$2bobo2b2o2bo$3bob
ob2o2bo$2o6b4o$2obobobo$obobob2obobo$bo2b
ob3o$b4o2b2o$3o2bo4b2o$bo3b3o2b2o$b4ob5o!

34 Life (B34/S34): Pattern loses toroidal connectivity at gen 7,346 and evolves from there as a single cluster, which rapidly stabilizes as one p2 oscillator and one p4 oscillator by gen 7,363.

We see here some suggestions of trends already — highly aggressive B2 growth takes a lot longer to stabilize than any of our B3-based examples; B34 growth also takes longer to stabilize than growth based on B3.

(I do not count B7 as a “growth” condition since it is incapable of extending a pattern outside its initial bounds. B4, though insufficient for growth alone, by contrast does achieve this in tertiary / inter-intercardinal directions, as best demonstrated by the octagonal growth envelope of rules like B34/S3456, where B3 only creates new cells in the eight primary and secondary directions, and most of the pattern’s growth is driven by B4.)

Let’s consider increasing the playfield size. Here are the four last rules again, from the same seed and on an arena of 24×24 (for brevity I will only give the RLE once):

x = 24, y = 24, rule = B3/S023:T24,24
bob2o3bobob2o2bobo2b2o$b2ob3ob2o2bo3b2obob3o$3b3o2b4ob3o4b2o
$5obo3b3ob2ob2o4bo$3bo2b3obob2o2b2o2b4o$3obo3bob4o4b3o2bo$2o
bo2b3o2bo2b2ob2o2b2o$o3b2o3bo3bob2o3b3o$2o7bo2b3o2b2o3b2o$b3
ob2obobob2ob2o4b2o$2obob2o2bo2bo2b2obo3b2o$bobobo5bob2o2b2o2
b3o$o2b2ob3ob2o4bo2bo3bo$o2bobo3b2o2b3obo3b3o$2ob2ob3obo3bob
o6bo$3bobo3bob6ob2obo$4b2obob2o2bobobobo$b5ob5o2b2o3bob3o$2b
o3b2ob3obo4b2ob2o$3b3o2bo2bobob3obob2o$o2b5o4bobobobo4bo$o4b
2ob3obo2bo3bobo$4bo2bob3ob3ob4obo$b4obo2bob2obobo3b2o!

DotLife: Stabilizes at gen 789 (final pop. 35).
DryLife: Stabilizes at gen 665 (final pop. 23).
Coral: Stabilizes as a dense agar at gen 120 (final pop. 473).
34 Life: No stabilization after 8,000,000 generations.

Note the vast differences in what happens! The two Life variants take just 2–3× longer to stabilize and yield ash of about the same density. Coral stabilizes again fast, but now reaches the high-population attractor phase. 34 Life might be again able to stabilize eventually but it’s, off the cuff, anyone’s guess if it would do so in a couple million or couple billion generations more.

For some degree of a handle on the latter, I checked one 15×15 seed and found that it stabilizes into a single p2 at gen 3,090,990; again after loosing toroidal connectivity to overcrowding shortly before, at gen …944. About 500× longer for a playfield 3 cells wider in each direction, so very conservatively, perhaps we might be able to expect a 24×24 seed to stabilize by a couple hundred trillion gens at least? (Or maybe not.)

This result is also not at all related to growth rates. DotLife chaos eventually grows in cardinal directions at a rate of c/2 and diagonally at c/4, thanks to stable B-heptomino puffers, rather faster than 34 Life does. The difference we are seeing is in the internal structure of chaos. Zooming into DotLife or DryLife chaos, indeed, shows small voids, oscillators, still lifes persisting for many generations before some cloud of activity consumes them again and maybe soon recreates a different arrangement of ash.

In any case, this suggests some metrics that might be usable for characterizing chaotic rules:

• Typical finite seed lifetime as a function of seed size.
• Typical ash density.
• Typical stabilization mechanisms.

The first two are of course also applicable to non-chaotic rules; this time just also when let play out on an infinite empty field. Yet other metrics would be also possible, e.g. on a closer look into a rule’s dynamics rather than its ultimate evolution.

There is, lastly, I think, an interesting question this raises on the ultimate evolution of chaotic rules in open space. Is it possible that a rule that looks like it is producing infinite growth, but appears to not be amenable to being proven to create infinite growth… actually isn’t? Perhaps, after some truly Googological amount of evolution, a growing splotch of chaos in e.g. 34 Life still breaks apart into a group of spaceships and oscillators. (Perhaps a puffer or gun in there too among bazillions of decay results.) Sounds very improbable, but given infinite time, any possible improbability would be expected to still happen. And these finite experiments do seem to show that in many rules, “chaos” does not actually have infinite lifespan, typically eventually reducing to small objects, rather than loops-within-itself. It does feel there are heuristic reasons to predict this not to happen; but they are, indeed, heuristics, grown in a small human brain not practically accustomed to dealing with infinities.

I’m also inclined to think back to Conway’s original Game of Life group a bit here. If you have been tracking the evolution of the R-pentomino by hand for ca. 800 generations, the longest-living pattern you’ve found yet, would you have any reasons to think that the pattern will stabilize in just a few hundred more? As it turns out, that it does, though very little even hints at this fate until ca. generation 1000, when two major areas of activity suddedly die off, leaving a pattern with more ash than activity. Even then it takes an additional 100 generations before the third remaining area also narrows down towards stabilization. This was always a mathematical fact, even before anyone calculated it, not an experiment that could have gone otherwise. But there would be a universe where the late Conway begun to investigate some slightly different iterative system, and where some analogue of the R-pentomino, turns out to live not for a thousand generations, but much longer, maybe hundreds of thousands of gens; in any case some count not really calculable by either reasonable human effort or by the computers of the day for quite some while. From that PoV the automaton in question might look as immortal as some other rules look right now. Is there any way to tell the difference in advance, before we have the computing power to follow a sufficiently chaotic pattern for one googol or one googolplex generations? Sometimes clever proofs might be available to show that growth must be infinite for non-straightforward reasons, but at other times, perhaps not.