Type 1: Immediate, Eventual or Statistical Death?

The most challenging topic in CA classification is probably developing clear definitions of “chaotic” and “complex” behavior — the two are very intertwined if looked at closely. However, the other two classes of the 1983 Wolfram classification, the “dying” and “shrinking” behaviors, have ambiguities to them as well. Some discussion of these probably makes for a good smaller starting case study. — As a general note before continuing further, I will be generally discussing Life-like CA on this blog. This well-studied space of 2¹⁸ CA still has some some limits on its details of behavior, but seems to readily provide examples of all relevant large-scale phenomena.

There are, of course, cellular automata that can be proven to evolve towards vacuum. As a trivial case, any rule with no birth and no survival (“B/S” in the usual notation), on any cell grid and any neighborhood, accomplishes this in one timestep. Rules with only very weak birth conditions exist also, which may drag this out to some finite number of additional timesteps but no more. Consider B8/S: all live cells immediately die off in this rule, and new cells will be only born in dead locations that were surrounded by eight live cells. In the next generation, all newborn cells will be thus surrounded by eight dead cells. They will of course themselves die off, but moreover, since none of these live cells can be adjacent to one another, no new cells will be born in the next generation. Therefore all patterns evolve to vacuum by the 3rd generation. ∎

B7/S and B78/S share the same property, though the proof is very slightly more complicated. The second generation can now contain also pairs of newborn cells. Triplets are, however, impossible. This suffices to again prove that no neighborhood sufficient for the birth of a yet new cell can arise in the 3rd generation, which is therefore again guaranteed to consist of vacuum.

---

The simplest rule with some arguable ambiguity in its behavior is B/S8, the rule with no birth and no survival, except of cells that are completely surrounded by other live cells. This rule allows exactly one pattern that does not evolve towards vacuum: the fully filled-in plane of live cells (I call this the antivacuum), which can be considered a stable agar. The presence of even a single dead cell yields a bubble of vacuum, growing at the rate of one cell per generation — the “speed of light”, as it is known in the field.

The behavior of any finite patterns in this rule is still simple to track or predict. “Landlocked” cells, those not exposed to vacuum, will survive, while all cells on the exterior will die. A cell therefore needs to be nth-degree landlocked to survive for n timesteps before dying. When using the Moore neighborhood, the degree of landlockedness of any given cell is easy to determine: if the largest square centered on the cell that only contains live cells has an edge length of 2n+1, then the cell has a landlockedness degree of n. A pattern containing a filled square 7 cells wide, for example, will have the central cell of this square survive at least three timesteps = to the 4th generation (though usually we start counting generations from zero and hence call the generation after three timesteps generation #3.)

Infinite patterns are however less obvious to characterize (is anything ever simpler with infinity?). Consider a pattern comprising a live halfplane and a dead halfplane, with a dividing line at any angle, though for simplicity we may consider an orthogonal line as the most basic example. The dead halfplane will advance by one cell every generation, clearly enough, and any given live cell will eventually die. On the other hand, our half-plane of live cells is still infinitely deep, and as such it contains cells that will remain alive for arbitrarily long. There is no generation at which the pattern will have evolved into pure vacuum.

For that matter, this pattern seems to fit a part of the definition of a spaceship or a wave! Individual cells may keep dying, but considered overall, the pattern is no smaller for this (it’s infinite after all) and rather, it appears to move away from the vacuum at the speed of light. If the dividing line is simple enough, orthogonal or at various (all?) rational slopes, the pattern also maintains its shape in each generation, and our “infinite spaceship” has a well-defined period of 1. We could conceive a research programme on what other periods of “halfplane spaceships” exist. We don’t even need an entire half a plane; e.g. any sector bounded by two lines will do just as well. Such patterns will now be definitely infinite spaceships, not waves: they have not just a velocity but also a well-defined direction, since the pattern has no translation symmetry. It seems that we could construct a spaceship with a wide range of rational slopes in this fashion. Two simple examples are the orthogonal quarterplane, with a slope (1,1), and the diagonal quarterplane, with a slope (1,0). I suspect that any rational slope is in fact possible. For that matter, sufficiently narrow sectors can prove to have superluminary speeds — the diagonal quarterplane already has speed 2c. A fairly interesting result for a mere “dying” CA (and we have not even begun to investigate what exact slope–speed–period combinations are possible), showing that even these rules can have behavior that is hardly trivial.

Further research potential yet can be identified too. We could consider patterns with more tattered decaying edges, perhaps giving rise to additional periodicity; or patterns with some generations of non-periodic evolution before an edge has been smoothed close enough to a line or some other stable shape (e.g. a parabola or hyperbola ought to work). And even, we can wonder if some kind of a 1D cellular automaton could be emulated with a suitable decaying edge. In some cases even universal computation could prove to exist within a strictly “dying” pattern, if we allow for patterns with infinitely many live cells.

---

But really I digress. The Wolfram classification is, and any potential successor should be, of course more concerned with the typical behavior of a CA than with exceptional engineered patterns. Infinitely many “plane sector spaceships” might exist in B/S8, but they are a marginal case and they require the existence of filled-in areas of any arbitrarily large size. Not only is this not possible for finite patterns, this is not expected to occur either for any “random” starting pattern of a density less than 100%.

Still we can ask: is B/S8 a “dying” or a “shrinking” rule? These days the community standard software for operating Life-like CA is Golly, which if asked to “randomly fill” an area, defaults to a density of 50%. Running one of these at B/S8 indeed rapidly develops to a population of zero. Testing out twenty such soups of a size of about 2300 by 1300 cells, with a starting population of about 1.5 million, only one of them left any alive cells by generation 2; clearly “dying” behavior. But suppose we started instead with a much higher density, e.g. around 99.999%? Now we would expect to find only about 30 dead cells in our field of about 3 million cells, enough to leave quite large areas of antivacuum, and it would probably take several hundreds of generations to see such a seed shrink to oblivion entirely. Such long lifespans could be argued to be instead a sign of a “shrinking rule”.

The lesson is clear, I think. The way in which “random” patterns develop depends on their starting density. “Shrinking” and “dying” are strictly speaking different pattern behaviors, not necessarily characteristics of every or even “every random” pattern in the rule. Rules that are instable from all starting densities, the likes of B8/S, are very few indeed. For most we could at most define a range of densities that they will comfortably support. Such ranges can have both an upper and a lower limit, too. Whenever a rule does not feature survival-at-8-neighbors, sufficiently high densities will be increasingly more likely to die out from overpopulation, no matter how the rule might behave at lower densities. This could of course still leave behind a number of “seeds” next to dead cells, that perhaps could then proceed to sprout into areas of more “rule-typical” density.

Worth noting though is that there is still a reason to privilege a density of 50%. If we wish to rigorously define “a random pattern”, we could ask e.g. for the modal behavior among all patterns of a given size. The average density of all of these is indeed 50%. Secondly, it’s even the case that this will show the most diversity in local densities. Some other global density like 60% would be more likely to show patches of other still higher densities like 70%; but also much less likely to show lower densities like 10%. However, this is probably not the case if we consider densities on a logarithmic scale… Densities of 99% and 99.99% are much more likely to show different behavior than densities of 49% and 49.99%.

In any case, instead of lumping various different rules all as simply “dying” / “type 1”, we can hence already map even their typical behavior more closely: time to die off as a function of density. The first could be considered to additionally depend on soup size (other things being equal, a larger random soup has better chances to contain slow-dying regions); or possibly should be measured rather as a rate of dying off.