Further Still On A Very Cellular Process

| 0 Comments

My fellow students and I have lately been spending our spare time experimenting with cellular automata, which are simple mathematical models of single celled creatures such as amoebas, governing their survival and reproduction from one generation to the next according to the population of their neighbourhoods[1][2]. In particular, we have been considering an infinite line of boxes, some of which contain living cells, together with rules that specify whether or not a box will be populated in the next generation according to its, its left hand neighbour's and its right hand neighbour's contents in the current generation.
We have found that for many such automata we can figure the contents of the boxes in any generation that evolved from a single cell directly, in a few cases from the oddness or evenness of elements in the rows of Pascal's triangle and the related trinomial triangle, and in several others from the digits in terms of sequences of binary fractions.
We have since turned our attention to the evolution of generations from multiple cells rather then one; specifically, from an initial generation in which each box has an even chance of containing a cell or not.

We may represent the rules of our automata by listing the outcomes for the middle of three boxes from one generation to the next. For example, representing populated boxes with filled squares and unpopulated boxes with hollow squares, we might have
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
Now, substituting filled squares with ones and hollow squares with zeros gives
\[ \begin{align*} 0\,0\,0 &\rightarrow\, 0 & 0\,0\,1 &\rightarrow\, 1 & 0\,1\,0 &\rightarrow\, 0 & 0\,1\,1 &\rightarrow\, 0 \\ 1\,0\,0 &\rightarrow\, 1 & 1\,0\,1 &\rightarrow\, 0 & 1\,1\,0 &\rightarrow\, 0 & 1\,1\,1 &\rightarrow\, 0 \end{align*} \]
which, upon treating the left hand sides of the arrows as binary numbers and converting them to decimals, yields
\[ \begin{align*} 0 &\rightarrow\, 0 & 1 &\rightarrow\, 1 & 2 &\rightarrow\, 0 & 3 &\rightarrow\, 0 \\ 4 &\rightarrow\, 1 & 5 &\rightarrow\, 0 & 6 &\rightarrow\, 0 & 7 &\rightarrow\, 0 \end{align*} \]
Using them as the indices of digits of yet another binary number which, following the usual notation of ordering from right to left, is equivalent to the powers of two that they stand for and the values upon the right hand side of the arrows as the values of those digits we may specify the rules of an automaton with a single number between zero and two hundred and fifty five, known as Wolfram codes[3], in this case being
\[ 00010010 = 18 \]
Noting that the contents of a box in the next generation are only be affected by its immediate neighbours in the current generation and their contents are in turn only be affected by their immediate neighbours, its contents in the \(n^\mathrm{th}\) following generation will only be influenced by its \(n\) currently nearest neighbours to the left and right and we may consequently dispense with any beyond those when figuring the first \(n+1\) generations of an automaton commencing from an infinite line of randomly populated boxes, as demonstrated by deck 1.

Deck 1: A Manageable Infinitude

You will no doubt recall that of the two hundred and fifty six automata not all were unique with respect to their mirrors, in which the order of the boxes in the current generation is reversed, and their complements, in which populated boxes are replaced with unpopulated boxes in both the current and the next generation and vice versa, leaving the eighty eight automata
\[ \begin{matrix} \phantom{00}0 & \phantom{00}1 & \phantom{00}3 & \phantom{00}4 & \phantom{00}5 & \phantom{00}7 & \phantom{00}8 & \phantom{00}9\\ \phantom{0}11 & \phantom{0}12 & \phantom{0}13 & \phantom{0}15 & \phantom{0}16 & \phantom{0}18 & \phantom{0}19 & \phantom{0}20\\ \phantom{0}22 & \phantom{0}23 & \phantom{0}24 & \phantom{0}25 & \phantom{0}26 & \phantom{0}27 & \phantom{0}28 & \phantom{0}29\\ \phantom{0}30 & \phantom{0}32 & \phantom{0}33 & \phantom{0}35 & \phantom{0}36 & \phantom{0}37 & \phantom{0}40 & \phantom{0}41\\ \phantom{0}43 & \phantom{0}44 & \phantom{0}45 & \phantom{0}48 & \phantom{0}50 & \phantom{0}51 & \phantom{0}52 & \phantom{0}54\\ \phantom{0}56 & \phantom{0}57 & \phantom{0}58 & \phantom{0}60 & \phantom{0}62 & \phantom{0}72 & \phantom{0}73 & \phantom{0}76\\ \phantom{0}77 & \phantom{0}80 & \phantom{0}84 & \phantom{0}88 & \phantom{0}90 & \phantom{0}92 & \phantom{0}94 & 104\\ 105 & 108 & 112 & 116 & 120 & 122 & 124 & 126\\ 128 & 132 & 136 & 140 & 144 & 146 & 148 & 150\\ 152 & 156 & 160 & 164 & 168 & 172 & 176 & 178\\ 180 & 184 & 200 & 204 & 208 & 212 & 232 & 240 \end{matrix}\]
Now we cannot possibly hope to reckon formulae to represent the generations of automata evolving from infinite lines of randomly populated boxes as binary fractions, but we may nevertheless classify them according to their general behaviours.

Uniform Automata

For example, automaton number zero trivially leaves each and every box vacant after the first generation and is the simplest example of automata that eventually set the entire multitude of boxes to a uniform state, either all populated or all unpopulated.
A slightly less trivial example is automaton eight, which deck 2 shows retains no living cells beyond the second generation.

Deck 2: Automaton Eight

We can see why this is so by examining its rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which only allow a cell to survive if the box to its left is empty and the box to its right is not. It is consequently impossible for either of its neighbouring boxes to be populated in the following generation and so it too must subsequently die
\[ \begin{align*} \square\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \square\,\blacksquare\,\square \rightarrow\, \square\\ \square\,\square\,\blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\square \rightarrow\, \square\\ \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \square\,\blacksquare\,\square \rightarrow\, \square\\ \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\square \rightarrow\, \square \end{align*} \]
Automaton one hundred and twenty eight leaves each box unpopulated unless it and both of its neighbours were populated in the previous generation
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
so that the first and last of an unbroken line of cells must die in each generation until eventually none remain, as demonstrated by deck 3.

Deck 3: Automaton One Hundred And Twenty Eight

Note that you can delay the inevitable extinction by increasing the probability that a box will initially contain a cell, represented by p.

Similarly, automaton thirty two only populates a box if its neighbours were populated and it was not
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
This means that a line of alternately populated and unpopulated boxes, starting and ending with the former, will evolve into one in which the states of the boxes are swapped in the next generation, losing its first and last cells in the process. Such lines will therefore shrink and ultimately disappear just as the unbroken lines of automaton one hundred and twenty eight did, which you can confirm by changing n to thirty two in deck 3.

A rather more long-lived example is automaton one hundred and sixty eight which has the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
In this case a cell will only survive if the box to its right is occupied and will reproduce into an empty box to its right if there's another cell to that box's right. As a result, single empty boxes migrate leftwards through lines of cells until they reach the leftmost and it dies, whilst pairs of empty boxes expand leftwards killing the rightmost of lines of cells. Lines of boxes containing no empty pairs will thus be eroded rapidly upon the right and slowly upon the left from generation to generation, as shown by deck 4.

Deck 4: Automaton One Hundred And Sixty Eight

Constant Automata

Another class of automata are those whose populations settle upon states where populated and unpopulated boxes remain as they are from one generation to the next, the simplest example being number two hundred and four which leaves every box as it was at the outset.
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
A minimal example is automaton four which only allows isolated cells to survive
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
so that we find persistent vertical lines one cell wide when we chart the generations, as is done by deck 5.

Deck 5: Automaton Four

We may double the width of those lines by allowing cells to survive only if they have one living neighbour, as is done by automaton seventy two
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which you may see for yourself by changing n in deck 5.
Adding four to its number yields automaton seventy six which admits lines both one and two cells wide, whilst adding one hundred and twenty eight to its number gives automaton two hundred which allows lines of two or more cells to persist; adding both recovers the simplest constant automaton two hundred and four in which all cells survive.

A more complex example is automaton ninety two which, in addition to allowing single and pairs of cells to survive, permits the reproduction of a cell into an empty box to its right if that box is not neighboured by another
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
so that cells will propagate into empty boxes to the right until there are cells beyond them. It is consequently impossible for pairs of empty boxes to persist and so we find trails one or two cells wide that are separated by a single empty box, as shown by deck 6.

Deck 6: Automaton Ninety Two

Cyclical Automata

The populations of some automata enter into a cycle of states wherein the contents of every box in a generation are the same as they were two or more generations before. The most trivial of these is automaton fifty one which fills unpopulated boxes and empties populated ones at each step
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \blacksquare & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
Automaton number one is the minimal example of cyclical automata and has the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \blacksquare & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
by which the second generation will only contain cells in those boxes that were originally empty and neighboured by empty boxes. We shall therefore find alternating lines of empty and populated boxes with the former typically being shorter than the latter. In the third generation, the boxes that contained cells will be empty and those that did not will be filled, apart from the first and last in their lines on account of their having had populated neighbours. The chart of its generations consequently takes the form of alternating horizontal lines separated by vertical lines of empty boxes, as demonstrated by deck 7.

Deck 7: Automaton One

If we add the rules that a cell whose neighbouring boxes are empty will survive and that a cell may reproduce into an empty box that it neighboured by another cell then we recover the rather more complicated automaton number thirty seven
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \blacksquare & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
whose behaviour you may witness by changing n in deck 7.
Whilst I'm sure that you will concur that it appears that its generations consistently settle into something like those of automaton number one, we cannot assume that they must always do so. We can, however, trivially assert that they will if there are no isolated populated or unpopulated boxes since this means that the new rules will not come into play. The heart of the matter is consequently whether or not we shall find such boxes in advanced generations.

To examine the evolution of a cell neighboured by empty boxes over three generations we must consider the sixteen cases involving the two further boxes to its neighbours' left and right
\[ \begin{align*} \square\,\square\,\square\,\blacksquare\,\square\,\square\,\square &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\square\,\blacksquare \rightarrow\, \blacksquare\,\blacksquare\,\blacksquare & \square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\square\,\square \rightarrow\, \blacksquare\,\blacksquare\,\square \\ \square\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \blacksquare\,\square\,\square & \square\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square \rightarrow\, \blacksquare\,\square\,\square \\ \\ \square\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\square &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare \rightarrow\, \square\,\square\,\blacksquare & \square\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\blacksquare &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\square\,\square \rightarrow\, \square\,\square\,\square \\ \square\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \square\,\square\,\square & \square\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square \rightarrow\, \square\,\square\,\square \\ \\ \blacksquare\,\square\,\square\,\blacksquare\,\square\,\square\,\square &\rightarrow\, \square\,\square\,\blacksquare\,\square\,\blacksquare \rightarrow\, \square\,\blacksquare\,\blacksquare & \blacksquare\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\square\,\square \rightarrow\, \square\,\blacksquare\,\square \\ \blacksquare\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \square\,\square\,\square & \blacksquare\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\square \rightarrow\, \square\,\square\,\square \\ \\ \blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\square &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare \rightarrow\, \square\,\square\,\blacksquare & \blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square\,\square \rightarrow\, \square\,\square\,\square \\ \blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \square\,\square\,\square & \blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\blacksquare\,\square \rightarrow\, \square\,\square\,\square \end{align*} \]
Of these, only one leaves the cell and it neighbours as they were, four see it migrate to the left or to the right, two give it a populated neighbour and fully eight kill it off. In nine of the sixteen cases none of them can possibly be isolated.
We can similarly figure the evolution of an empty box with two populated neighbours
\[ \begin{align*} \square\,\square\,\blacksquare\,\square\,\blacksquare\,\square\,\square &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\blacksquare\,\square \rightarrow\, \square\,\square\,\square & \square\,\square\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \square\,\square\,\square \\ \square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square\,\square \rightarrow\, \square\,\square\,\square & \square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square\,\square \rightarrow\, \square\,\square\,\square \\ \\ \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\square \rightarrow\, \square\,\square\,\square & \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \square\,\square\,\square \\ \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \square\,\square\,\blacksquare\,\square\,\square \rightarrow\, \square\,\blacksquare\,\square & \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\square\,\square \rightarrow\, \square\,\blacksquare\,\square \\ \\ \blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\square\,\square &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square \rightarrow\, \square\,\square\,\square & \blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \square\,\square\,\square \\ \blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\square\,\square \rightarrow\, \square\,\square\,\square & \blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\square\,\square \rightarrow\, \square\,\square\,\square \\ \\ \blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\square \rightarrow\, \square\,\square\,\square & \blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \square\,\square\,\square \\ \blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \square\,\square\,\blacksquare\,\square\,\square \rightarrow\, \square\,\blacksquare\,\square & \blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\square\,\square \rightarrow\, \square\,\blacksquare\,\square \end{align*} \]
which leave all three empty in three quarters of the cases.
Given a randomly populated initial population, on balance of probability the number of isolated boxes will decrease over the generations and we shall ultimately be left with alternating populations much like those of automaton one.

My fellow students and I have also found cyclical automata that do not simply alternate between two states of the population. For example automaton ninety four has the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which deck 8 demonstrates can settle into local cycles of period three, although you may have to run it a few times to yield an example.

Deck 8: Automaton Ninety Four

The first thing to note is that its rules ensure that when an empty box is flanked by two cells they will all three persist from one generation to the next
\[ \begin{align*} \square\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\square\,\blacksquare& \square\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare\\ \blacksquare\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\square\,\blacksquare& \blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare \end{align*} \]
Similarly, if a pair of cells are neighboured by isolated empty boxes then all six will remain in the same state
\[ \begin{align*} \square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare& \square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\\ \blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare& \blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare \end{align*} \]
Furthermore, an empty box that has just one populated neighbour will itself become populated so that lines of empty boxes will shrink from one generation to the next until there are no more than one left unoccupied.

Next, a pair of empty boxes neighboured by immortal cells results in the alternating states
\[ \blacksquare\,\square\,\square\,\blacksquare \rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \blacksquare\,\square\,\square\,\blacksquare \]
and finally, a line of four unpopulated boxes flanked by persistent cells yields the observed period three cycles
\[ \blacksquare\,\square\,\square\,\square\,\square\,\blacksquare \rightarrow\, \blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare \rightarrow\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare \rightarrow\, \blacksquare\,\square\,\square\,\square\,\square\,\blacksquare \]
A dramatically more complicated example is automaton seventy three which has the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \blacksquare & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which my fellow students and I have put together in deck 9.

Deck 9: Automaton Seventy Three

Whilst it is not immediately obvious that the generations of this automaton are cyclical we can prove that they are with a relatively simple observation; that a pair of populated boxes neighboured by unpopulated boxes are persistent
\[ \begin{align*} \square\,\square\,\blacksquare\,\blacksquare\,\square\,\square &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square\\ \square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square\\ \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\square &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square\\ \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare &\rightarrow\, \square\,\blacksquare\,\blacksquare\,\square \end{align*} \]
and further that four empty boxes straddled by cells will enter into that persistent state
\[ \blacksquare\,\square\,\square\,\square\,\square\,\blacksquare \rightarrow\, \square\,\blacksquare\,\blacksquare\,\square \]
Given an infinitude of randomly populated boxes, it must therefore be the case that any line of boxes will ultimately be met by such barriers and, having but a finite number of possible configurations, will inevitably return to any given state and thereupon enter into a cycle.

Migratory Automata

A further species of automata evolve into populations that migrate to the right or to the left with passing generations. Of these, one of the simplest is number two hundred and forty which explicitly copies the contents of each box to its right
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
as demonstrated by deck 10.

Deck 10: Automaton Two Hundred And Forty

A minimal migratory automaton is number sixteen, in which the rightmost of any line of cells reproduces to its right and subsequently dies along with every other cell
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which you may observe by changing n to sixteen in deck 10.

Automaton fifty six adds the rules that a cell that only has a living neighbour to the right will survive and that an empty box will become populated if both of its neighbours are occupied
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
In addition to a cell propagating into an unoccupied box to its right, a line of four boxes in which all but the second contain cells will propagate to the left until they inevitably encounter a pair of boxes that are both populated or are both unpopulated
\[ \begin{align*} \square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\square \\ \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square \\ \blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\square \\ \blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare &\rightarrow\, \square\,\square\,\blacksquare\,\blacksquare\,\square \end{align*} \]
with the rightmost box necessarily being empty on account of the death of any cell neighboured to its left by another.
If they fail to reproduce then, whatever the contents of the box to the left, the pair of neighbouring cells will evolve into an isolated cell
\[ \begin{align*} \square\,\square\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \square\,\square\,\blacksquare\,\square \\ \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare\,\square\,\blacksquare\,\square \end{align*} \]
which shall thereafter propagate to the right.

Automaton one hundred and eighty is a rather more complicated example, having the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
which are exercised by deck 11.

Deck 11: Automaton One Hundred And Eighty

Those rules imply that the outermost of any run of two or more cells must die and that empty boxes will only become populated if their leftwards neighbours contain cells. An isolated cell neighboured upon either side by lines of several empty boxes cannot consequently persist for more than one generation. Whilst such lines of empty boxes become populated upon the left from one generation to the next they must therefore become vacant upon the right, forming impenetrable shifting barriers between which only a finite number of variations of occupied and unoccupied boxes might be found, so that they must eventually return to former configurations, albeit shifted to the right, much like automaton seventy three.

Random Automata

The penultimate category of automata are those whose populations do not settle into repetitive states, such as automaton ninety which is defined by the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
that my fellow students and I have realised with deck 12.

Deck 12: Automaton Ninety

To understand the behaviour of this automaton note that the first and last of any line of more than one empty box will become filled in the next generation. It is also the case that all but the first and last cells in a line of populated boxes will die off, as will those in lines of alternately occupied and unoccupied boxes. We are consequently met with the sudden apparition and subsequent erosion of lines of empty boxes which, crucially, are born from the left and rightwards migration of cells' offspring; offspring that arrive randomly upon account of their primal ancestors' thoroughly muddled residencies.

Automaton sixty behaves similarly, for much the same reason, albeit with cells only propagating to the right
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
as does automaton one hundred and fifty
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
in which lines of both populated and unpopulated boxes spring into existence and subsequently decline, both of which you may observe for yourself by changing n in deck 12.

Strange Automata

The final species of automata are those that are neither one thing nor the other, displaying both order and chaos in their evolution. For example, automaton one hundred and ten with the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \\ \blacksquare\,\square\,\square &\rightarrow\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
exhibits both cyclical and migratory behaviour, with such arrangements of cells interacting in complicated ways, as demonstrated in minute detail by deck 13.

Deck 13: Automaton One Hundred And Ten

The generations of automaton fifty four evolve in a similar, albeit markedly less pronounced, fashion with the rules
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\blacksquare\,\blacksquare &\rightarrow\, \square \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
My fellow students and I are especially interested in the former but I fear that our studies are calling and we must set our automata aside for the time being.
\(\Box\)

References

[1] On A Very Cellular Process, www.thusspakeak.com, 2020.

[2] Further On A Very Cellular Process, www.thusspakeak.com, 2020.

[3] Wolfram, S., Statistical Mechanics of Cellular Automata, Reviews of Modern Physics, Vol. 55, No. 3, American Physical Society, 1983.

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+