Further On A Very Cellular Process

| 0 Comments

You will no doubt recall my telling you of my fellow students' and my latest pastime of employing Professor B------'s Experimental Clockwork Mathematical Apparatus[1] to explore the behaviours of cellular automata[2], which may be thought of as simplistic mathematical simulacra of animalcules such as amoebas.
Specifically, if we put together an infinite line of imaginary boxes, some of which are empty and some of which contain living cells, then we can define a set of rules to determine whether or not a box will contain a cell in the next generation depending upon its own, its left and its right neighbours contents in the current one.

Enumerating Automata

By way of an example, we might decide that a cell will only survive if the box to its left is empty, but will reproduce into the box to its right if it and its right hand neighbour are both unoccupied.
Using a hollow square to represent an empty box and a filled square to represent a populated one, the contents of the middle box of three in the next generation would therefore be given by
\[ \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\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
Replacing the hollow squares with zeros and the filled squares with ones, we have
\[ \begin{align*} 0\,0\,0 &\rightarrow\, 0 & 0\,0\,1 &\rightarrow\, 0 & 0\,1\,0 &\rightarrow\, 1 & 0\,1\,1 &\rightarrow\, 1 \\ 1\,0\,0 &\rightarrow\, 1 & 1\,0\,1 &\rightarrow\, 0 & 1\,1\,0 &\rightarrow\, 0 & 1\,1\,1 &\rightarrow\, 0 \end{align*} \]
which, interpreting the zeros and ones upon the left hand side of the arrows as the digits of binary numbers and translating into decimals, gives us
\[ \begin{align*} 0 &\rightarrow\, 0 & 1 &\rightarrow\, 0 & 2 &\rightarrow\, 1 & 3 &\rightarrow\, 1 \\ 4 &\rightarrow\, 1 & 5 &\rightarrow\, 0 & 6 &\rightarrow\, 0 & 7 &\rightarrow\, 0 \end{align*} \]
Figuring those decimals as the indices of another binary number whose digits are the zeros and ones that lie upon the right hand side of the arrows, we have
\[ 00011100 = 28 \]
using the convention that we count the digits of numbers from the right to the left, starting at zero. Such numbers are known as the Wolfram codes[3] of cellular automata.

Now there are a couple of symmetries that we can exploit to reduce the number of automata that we need consider. Firstly, we can exchange the left and right hand side neighbours in the rules' previous generation's state. For our example automaton this yields
\[ \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\, \square & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which we can achieve by swapping its number's second and fifth, and fourth and seventh binary digits
\[ 28 = 0\bar00\dot1\bar11\dot00 \rightarrow 0\bar10\dot0\bar01\dot10 = 70 \]
Secondly, we can exchange empty and populated boxes in the automaton's rules
\[ \begin{align*} \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\square\,\square &\rightarrow\, \square \\ \square\,\blacksquare\,\blacksquare &\rightarrow\, \square & \square\,\blacksquare\,\square &\rightarrow\, \blacksquare & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\square\,\square &\rightarrow\, \blacksquare \end{align*} \]
which has the effect of reversing the binary digits in its number and then swapping its zeros for ones and its ones for zeros
\[ 28 = 00011100 \rightarrow 00111000 \rightarrow 11000111 = 199 \]
As a consequence there are just eighty eight of the two hundred and fifty six possible automata that may be considered unique.

If our automata commence with but a single living cell then those with a number that is wholly divisible by four are incapable of populating boxes to its left. My fellow students and I found notable the six such automata
\[ 28, 60, 92, 124, 188, 220 \]
which is to say that they yield patterns that are unique with respect to those transformations and are more complicated than a few dots or lines, which you can observe for yourself by changing n in deck 1.

Deck 1: One Sided Automata

Since all odd numbered automata populate the middle of three empty boxes with a cell and will consequently immediately fill almost all of those to the left and right of the first we restricted our focus to the remaining even numbered examples, of which
\[ 18, 22, 30, 50, 54, 62, 94, 126, 150, 158, 190, 222 \]
we found to be of interest, as you can see with deck 2.

Deck 2: Two Sided Automata

We have already figured that the one sided automaton number sixty and the two sided automaton number eighteen can be though of as representing the evenness or oddness of elements in Pascal's triangle, the \(r^\mathrm{th}\) element of the \(n^\mathrm{th}\) row of which, counting from zero, is the coefficient of the \(r^\mathrm{th}\) power of \(x\) in the expansion of the binomial \((1+x)^n\) and is given by the combination
\[ {}^nC_r = \frac{n!}{r! \times (n-r)!} \]
where the exclamation mark yields the product of every whole number in the inclusive range from one to that on its left, or one if it equals zero, known as the factorial.
For example, numbering the location of the first cell's box as zero, those to its left negatively and those to its right positively, we proved that the state of automaton eighteen's \(r^\mathrm{th}\) box in its \(n^\mathrm{th}\) generation, also starting at zero, is given by
\[ b_{n,r} = \begin{cases} \square & |r| > n \vee n+r \;\text{is odd} \vee {}^nC_{\frac{1}{2}(n+r)}\;\text{is even}\\ \blacksquare &\text{otherwise} \end{cases} \]
where the vertical bars stand for the magnitude of the term between them and \(\vee\) means or.

Having discovered this rule, my fellow students and I were naturally curious as to whether we could find tidy formulae to reckon the contents of boxes in any particular generation of other automata!

Enumerating Generations

If we again interpret empty boxes as zeros and populated boxes as ones we can represent a generation as a binary number whose digits are given by them. Following the usual convention of placing the most significant digits upon the left and the least upon the right, we might do so by treating those to the right of the first cell as fractional with
\[ c_n = \sum_{r=-n}^n b_{n,r} \times 2^{-r} \]
where \(\sum\) is the summation sign, by noting that cells can only propagate one box to the left or right at each generation and consequently those outside of the range \(-n\) to \(n\) must be empty. It must therefore also be the case that
\[ C_n = 2^n \times c_n = \sum_{r=-n}^n b_{n,r} \times 2^{n-r} \]
is an integer.

For example, the one sided automaton number two hundred and twenty has the rules
\[ \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\, \blacksquare \end{align*} \]
so that every cell survives and the rightmost reproduces in each generation, as demonstrated by deck 3.

Deck 3: Automaton Two Hundred And Twenty

We therefore have
\[ c_n = \sum_{r=0}^n 2^{-r} = \sum_{r=1}^{n+1} \left(\frac12\right)^{r-1} \]
which is but a simple geometric series and consequently evaluates to
\[ c_n = \frac{1-\left(\frac12\right)^{n+1}}{1-\frac12} = 2-\left(\frac12\right)^n \]
Writing out successive values as both regular fractions and as binary fractions with leading and trailing zeros yields

\(\boldsymbol{n}\)\(\boldsymbol{c_n}\)\(\boldsymbol{c_n}\)
\(0\)\(1\) \(\dots000000001.00000000\dots\)
\(1\)\(1\frac12\) \(\dots000000001.10000000\dots\)
\(2\)\(1\frac34\) \(\dots000000001.11000000\dots\)
\(3\)\(1\frac78\) \(\dots000000001.11100000\dots\)
\(4\)\(1\frac{15}{16}\) \(\dots000000001.11110000\dots\)
\(5\)\(1\frac{31}{32}\) \(\dots000000001.11111000\dots\)
\(6\)\(1\frac{63}{64}\) \(\dots000000001.11111100\dots\)
\(7\)\(1\frac{127}{128}\) \(\dots000000001.11111110\dots\)
\(\vdots\)\(\vdots\)\(\vdots\)

from the latter of which we can recover the generations of the automaton by replacing the zeros and ones with empty and populated boxes respectively, with the binary point serving merely as an indication of position.

Related to this is the two sided automaton two hundred and twenty two which 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\, \blacksquare \end{align*} \]
so that the leftmost cell also propagates, as shown by deck 4 until it runs beyond the bounds of its output.

Deck 4: Automaton Two Hundred And Twenty Two

This time we have the sum
\[ c_n = \sum_{r=-n}^n 2^{-r} \]
which, for \(n\) greater than zero, we may split into
\[ c_n = \sum_{r=-n}^{-1} 2^{-r} + \sum_{r=0}^n 2^{-r} = \sum_{r=1}^{n} 2 \times 2^{r-1} + \sum_{r=1}^{n+1} \left(\frac12\right)^{r-1}\\ \]
yielding a pair of geometric series so that
\[ c_n = 2 \times \frac{1-2^n}{1-2} + \frac{1-\left(\frac12\right)^{n+1}}{1-\frac12} = \left(2^{n+1}-2\right) + \left(2-\left(\frac12\right)^n\right) = 2^{n+1} - \left(\frac12\right)^n \]
serendipitously also holding true for \(n\) equal to zero. Writing down the fractions again, we have

\(\boldsymbol{n}\)\(\boldsymbol{c_n}\)\(\boldsymbol{c_n}\)
\(0\)\(1\) \(\dots000000001.00000000\dots\)
\(1\)\(3\frac12\) \(\dots000000011.10000000\dots\)
\(2\)\(7\frac34\) \(\dots000000111.11000000\dots\)
\(3\)\(15\frac78\) \(\dots000001111.11100000\dots\)
\(4\)\(31\frac{15}{16}\) \(\dots000011111.11110000\dots\)
\(5\)\(63\frac{31}{32}\) \(\dots000111111.11111000\dots\)
\(6\)\(127\frac{63}{64}\) \(\dots001111111.11111100\dots\)
\(7\)\(255\frac{127}{128}\) \(\dots011111111.11111110\dots\)
\(\vdots\)\(\vdots\)\(\vdots\)

clearly representing automaton two hundred and twenty two's generations.

Next, let us consider automaton twenty eight which has the rules
\[ \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\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which state that a cell will reproduce into an empty box to its right if that box does not have another neighbouring cell and survive if and only if the box to its left is empty. Together, these imply that the first cell will propagate to the right in every generation, leaving behind alternating populated and unpopulated boxes behind it as it does so, as we can see in the first eight binary fractions representing its generations
\[ \begin{align*} c_0 &= 1.0000000 = 1\\ c_1 &= 1.1000000 = 1\tfrac12\\ c_2 &= 1.0100000 = 1\tfrac14\\ c_3 &= 1.0110000 = 1\tfrac38\\ c_4 &= 1.0101000 = 1\tfrac{5}{16}\\ c_5 &= 1.0101100 = 1\tfrac{11}{32}\\ c_6 &= 1.0101010 = 1\tfrac{21}{64}\\ c_7 &= 1.0101011 = 1\tfrac{43}{128} \end{align*} \]
To ignore the rightmost cell we may subtract \(2^{-n}\) from \(c_n\) to yield
\[ \begin{align*} c^\prime_0 &= 0.0000000 = 0\\ c^\prime_1 &= 1.0000000 = 1\\ c^\prime_2 &= 1.0000000 = 1\\ c^\prime_3 &= 1.0100000 = 1\tfrac14\\ c^\prime_4 &= 1.0100000 = 1\tfrac14\\ c^\prime_5 &= 1.0101000 = 1\tfrac{5}{16}\\ c^\prime_6 &= 1.0101000 = 1\tfrac{5}{16}\\ c^\prime_7 &= 1.0101010 = 1\tfrac{21}{64} \end{align*} \]
which is but an accumulation of quarters and so for \(n\) greater than zero satisfies
\[ c^\prime_n = \sum_{i=1}^{\lceil n\div2 \rceil} \left(\frac14\right)^{i-1} \]
where the oddly shaped brackets represent the ceiling of the term between them, being the smallest integer that is greater than or equal to it. This is yet another geometric series, taking the value
\[ c^\prime_n = \frac{1-\left(\frac14\right)^{\lceil n \div 2\rceil}}{1-\frac14} = \frac43 \times \left(1-\left(\frac14\right)^{\lceil n \div 2\rceil}\right) \]
Noting that
\[ \left(\frac14\right)^{\lceil n \div 2\rceil} = \left(\frac12\right)^n - \frac14 \times \left(\frac12\right)^n + \frac14 \times \left(-\frac12\right)^n = \frac{3 + (-1)^n}{2^{n+2}} \]
we have
\[ c^\prime_n = \frac43 \times \left(1-\frac{3 + (-1)^n}{2^{n+2}}\right) = \frac13 \times \left(4-\frac{3 + (-1)^n}{2^n}\right) \]
and consequently
\[ c_n = \frac13 \times \left(4-\frac{3 + (-1)^n}{2^n}\right) + \frac{1}{2^n} = \frac13 \times \left(4-\left(-\frac{1}{2}\right)^n\right) \]
which also serendipitously holds for \(n\) equal to zero.

Deck 5 compares the results of our formula to values explicitly figured from the contents of the boxes in automaton twenty eight's first sixteen generations.

Deck 5: Automaton Twenty Eight's Generations

Automaton ninety two adds the rule that a cell will persist if either or both of its neighbouring boxes are unoccupied
\[ \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*} \]
with the effect that a pair of cells reproduce to the right ahead of the alternating boxes in every generation after the first
\[ \begin{align*} c_0 &= 1.0000000 = 1\\ c_1 &= 1.1000000 = 1\tfrac12\\ c_2 &= 1.1100000 = 1\tfrac34\\ c_3 &= 1.0110000 = 1\tfrac38\\ c_4 &= 1.0111000 = 1\tfrac{7}{16}\\ c_5 &= 1.0101100 = 1\tfrac{11}{32}\\ c_6 &= 1.0101110 = 1\tfrac{23}{64}\\ c_7 &= 1.0101011 = 1\tfrac{43}{128} \end{align*} \]
We can put these aside by subtracting \(3 \times 2^{-n}\)
\[ \begin{align*} c^\prime_1 &= 0.0000000 = 0\\ c^\prime_2 &= 1.0000000 = 1\\ c^\prime_3 &= 1.0000000 = 1\\ c^\prime_4 &= 1.0100000 = 1\tfrac14\\ c^\prime_5 &= 1.0100000 = 1\tfrac14\\ c^\prime_6 &= 1.0101000 = 1\tfrac{5}{16}\\ c^\prime_7 &= 1.0101000 = 1\tfrac{5}{16} \end{align*} \]
to yield the same accumulation of quarters, albeit delayed by a generation, so that for \(n\) greater than zero we have
\[ c^\prime_n = \frac13 \times \left(4-\frac{3 + (-1)^{n-1}}{2^{n-1}}\right) \]
and consequently \(c_n\) is is equal to one in the first generation and is thereafter given by
\[ \begin{align*} c_n &= \frac13 \times \left(4-\frac{3 + (-1)^{n-1}}{2^{n-1}}\right) + \frac{3}{2^n}\\ &= \frac13 \times \left(4-\frac{3 + (-1)^{n-1}}{2^{n-1}}\right) + \left(\frac12\right)^{n-1} + \left(\frac12\right)^n\\ &= \frac13 \times \left(4-\left(-\frac12\right)^{n-1}\right) + \left(\frac12\right)^n \end{align*} \]
as confirmed by deck 6.

Deck 6: Automaton Ninety Two's Generations

Automaton ninety four extends these rules still further by allowing a cell to also reproduce into the box to its left if it and its left neighbour are empty
\[ \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*} \]
so that in the second generation we have a line of three populated boxes and thus in the third the original cell dies leaving a pair of cells to propagate to the left and another to propagate to the right, both trailing alternating boxes
\[ \begin{align*} c_0 &= 00000001.0000000 = 1\\ c_1 &= 00000011.1000000 = 3\tfrac12\\ c_2 &= 00000110.1100000 = 6\tfrac34\\ c_3 &= 00001110.1110000 = 14\tfrac78\\ c_4 &= 00011010.1011000 = 26\tfrac{11}{16}\\ c_5 &= 00111010.1011100 = 58\tfrac{23}{32}\\ c_6 &= 01101010.1010110 = 106\tfrac{43}{64}\\ c_7 &= 11101010.1010111 = 234\tfrac{87}{128} \end{align*} \]
To figure the values of the generations it is convenient to consider the boxes to the left and right independently
\[ \begin{align*} c^\prime_1 &= 0000001 = 1 & c^{\prime\prime}_1 &= 1.000000 = 1\\ c^\prime_2 &= 0000011 = 3 & c^{\prime\prime}_2 &= 1.100000 = 1\tfrac12\\ c^\prime_3 &= 0000111 = 7 & c^{\prime\prime}_3 &= 1.110000 = 1\tfrac34\\ c^\prime_4 &= 0001101 = 13 & c^{\prime\prime}_4 &= 1.011000 = 1\tfrac38\\ c^\prime_5 &= 0011101 = 29 & c^{\prime\prime}_5 &= 1.011100 = 1\tfrac{7}{16}\\ c^\prime_6 &= 0110101 = 53 & c^{\prime\prime}_6 &= 1.010110 = \tfrac{11}{32}\\ c^\prime_7 &= 1110101 = 117 & c^{\prime\prime}_7 &= 1.010111 = \tfrac{23}{64} \end{align*} \]
so that
\[ c_n = \begin{cases} 1 & n=0\\ 3\frac12 & n=1\\ 2 \times c^\prime_n + \frac12 \times c^{\prime\prime}_n & \text{otherwise} \end{cases} \]
Those to the right evolve in much the same fashion as automaton ninety two and so we have
\[ c^{\prime\prime}_n = \begin{cases} 1 & n = 1\\ \frac13 \times \left(4-\left(-\frac12\right)^{n-2}\right) + \left(\frac12\right)^{n-1} & \text{otherwise} \end{cases} \]
Separating the reproducing pair of cells from those they leave behind on the left yields
\[ c^\prime_n = \begin{cases} 1 & n=1\\ 3 & n=2\\ 3 \times 2^{n-2} + \sum_{i=1}^{\lceil(n-2) \div 2\rceil} 4^{i-1} & \text{otherwise} \end{cases} \]
and we may find the value of the sum with the same line of reasoning as we used for that upon the right
\[ \sum_{i=1}^{\lceil(n-2) \div 2\rceil} 4^{i-1} = \frac{1-4^{\lceil(n-2) \div 2\rceil}}{1-4} = \frac13 \times \left(2^{n-2} + 2^{n-3} + \left(-2\right)^{n-3} - 1\right) = 2^{n-3} + \frac13 \times \left(\left(-2\right)^{n-3} - 1\right) \]
which also holds for \(n\) equal to two, and consequently
\[ c^\prime_n = \begin{cases} 1 & n=1\\ 7 \times 2^{n-3} + \frac13 \times \left(\left(-2\right)^{n-3} - 1\right) & \text{otherwise} \end{cases} \]
yielding
\[ \begin{align*} c_n = 2 \times c^\prime_n + \frac12 \times c^{\prime\prime}_n &= \left(7 \times 2^{n-2} + \frac23 \times \left(\left(-2\right)^{n-3} - 1\right)\right) + \left(\frac16 \times \left(4-\left(-\frac12\right)^{n-2}\right) + \left(\frac12\right)^n\right)\\ &= 7 \times 2^{n-2} - \frac13 \times \left(-2\right)^{n-2} + \frac13 \times \left(-\frac12\right)^{n-1} + \left(\frac12\right)^n \end{align*} \]
for \(n\) greater than one, which is verified by deck 7.

Deck 7: Automaton Ninety Four's Generations

The rules of automaton number fifty stipulate that no cell survives into the next generation but that they will always reproduce into an empty neighbouring box
\[ \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\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
so that once a box has become populated it will switch between being unpopulated and populated in each subsequent generation
\[ \begin{align*} c_0 &= 00000001.0000000 = 1\\ c_1 &= 00000010.1000000 = 2\tfrac12\\ c_2 &= 00000101.0100000 = 5\tfrac14\\ c_3 &= 00001010.1010000 = 10\tfrac58\\ c_4 &= 00010101.0101000 = 21\tfrac{5}{16}\\ c_5 &= 00101010.1010100 = 42\tfrac{21}{32}\\ c_6 &= 01010101.0101010 = 83\tfrac{21}{64}\\ c_7 &= 10101010.1010101 = 166\tfrac{85}{128} \end{align*} \]
creating a growing triangular checkerboard. We can enumerate each such generation with an accumulation of fours shifted to the right by a power of one half
\[ c_n = \left(\frac12\right)^n \times \sum_{i=0}^n 4^i = \left(\frac12\right)^n \times \sum_{i=1}^{n+1} 4^{i-1} = \left(\frac12\right)^n \times \frac{1-4^{n+1}}{1-4} = \frac13 \times \left(2^{n+2} - \left(\frac12\right)^n\right) \]
as shown by deck 8.

Deck 8: Automaton Fifty's Generations

Automaton fifty four adds the rule that a cell will survive if the boxes upon both its sides are empty
\[ \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*} \]
meaning that a single cell will become a line of three in the next generation which will all subsequently die, with the left and rightmost reproducing to their left and right respectively. This leaves a gap of three empty boxes between the offspring which is just enough room for the process to repeat without their triplets affecting one another.
\[ \begin{align*} c_0 &= 00000001.0000000 = 1\\ c_1 &= 00000011.1000000 = 3\tfrac12\\ c_2 &= 00000100.0100000 = 4\tfrac14\\ c_3 &= 00001110.1110000 = 14\tfrac78\\ c_4 &= 00010001.0001000 = 17\tfrac{1}{16}\\ c_5 &= 00111011.1011100 = 56\tfrac{23}{32}\\ c_6 &= 01000100.0100010 = 68\tfrac{17}{64}\\ c_7 &= 11101110.1110111 = 238\tfrac{119}{128} \end{align*} \]
The easiest way to enumerate these generations is to figure the even and odd numbered separately, noting that the former are accumulations of ones and the latter are accumulations of sevens
\[ \begin{align*} c_{2n} &= \phantom{\frac12 \times\;} \left(\frac14\right)^n \times \sum_{i=0}^n 1 \times 16^{\,i}\\ c_{2n+1} &= \frac12 \times \left(\frac14\right)^n \times \sum_{i=0}^n 7 \times 16^{\,i} \end{align*} \]
and therefore
\[ \begin{align*} c_{2n} &= \phantom{\frac72 \times \;}\left(\frac14\right)^n \times \sum_{i=1}^{n+1} 16^{\,i-1} = \frac{1}{15} \times \left(4^{n+2}-\left(\frac14\right)^{n}\right)\\ c_{2n+1} &= \frac72 \times \left(\frac14\right)^n \times \sum_{i=1}^{n+1} 16^{\,i-1} = \frac{7}{30} \times \left(4^{n+2}-\left(\frac14\right)^{n}\right) \end{align*} \]
Exploiting the similarity between these formulae, deck 9 determines whether the generation is odd or even to choose the constant of multiplication and deduce the appropriate value of \(n\).

Deck 9: Automaton Fifty Four's Generations

The rules of automaton one hundred and fifty eight are
\[ \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\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
so that a cell will survive unless the box to its left is populated and the box to its right is not, and will propagate to the left or right if that box isn't neighboured by another cell. Its first eight generations are consequently
\[ \begin{align*} c_0 &= 00000001.0000000 = 1\\ c_1 &= 00000011.1000000 = 3\tfrac12\\ c_2 &= 00000111.0100000 = 7\tfrac14\\ c_3 &= 00001110.0110000 = 14\tfrac38\\ c_4 &= 00011101.1101000 = 29\tfrac{13}{16}\\ c_5 &= 00111001.1001100 = 57\tfrac{19}{32}\\ c_6 &= 01110111.0111010 = 119\tfrac{29}{64}\\ c_7 &= 11100110.0110011 = 230\tfrac{51}{128} \end{align*} \]
which alternate between patterns of the form
\[ \blacksquare(\blacksquare\blacksquare\square\blacksquare)\ast \]
where the asterisk stands for zero or more repetitions of the squares in the braces preceding it, and
\[ \blacksquare(\blacksquare\blacksquare\square\square)+ \]
where the plus sign stands for one or more repetitions. It is therefore simplest to again figure the values of the even and odd numbered generations separately, the former being
\[ \begin{align*} c_0 &= 00000001.0000000 = 1\\ c_2 &= 00000111.0100000 = 7\tfrac14\\ c_4 &= 00011101.1101000 = 29\tfrac{13}{16}\\ c_6 &= 01110111.0111010 = 119\tfrac{29}{64} \end{align*} \]
and the latter
\[ \begin{align*} c_1 &= 00000011.1000000 = 3\tfrac12\\ c_3 &= 00001110.0110000 = 14\tfrac38\\ c_5 &= 00111001.1001100 = 57\tfrac{19}{32}\\ c_7 &= 11100110.0110011 = 230\tfrac{51}{128} \end{align*} \]
If we subtract \(2^{-n}\) from the even generations we recover the accumulations of sevens
\[ \begin{align*} c^\prime_0 &= 00000000.0000000 = 0\\ c^\prime_2 &= 00000111.0000000 = 7\\ c^\prime_4 &= 00011101.1100000 = 29\tfrac34\\ c^\prime_6 &= 01110111.0111000 = 119\tfrac{7}{16} \end{align*} \]
which, for \(n\) greater than zero, we can express as the geometric series
\[ c^\prime_{2n} = \left(\frac14\right)^{n-1} \times \sum_{i=0}^{n-1} 7 \times 16^{\,i} = 7 \times \left(\frac14\right)^{n-1} \times \frac{1-16^{\,n}}{1-16} = \frac{7}{15} \times \left(4^{n+1} - \left(\frac14\right)^{n-1}\right) \]
the solution of which also holds for \(n\) equal to zero. Adding back the trailing cell yields
\[ \begin{align*} c_{2n} &= \frac{7}{15} \times \left(4^{n+1} - \left(\frac14\right)^{n-1}\right) + \left(\frac14\right)^n\\ &= \frac{7}{15} \times 4^{n+1} - \frac{7}{15} \times 4 \times \left(\frac14\right)^n + \left(\frac14\right)^n\\ &= \frac{7}{15} \times 4^{n+1} - \frac{13}{15} \times \left(\frac14\right)^n \end{align*} \]
For the odd generations we can remove the leftmost cell by subtracting \(2^n\) to leave accumulations of threes
\[ \begin{align*} c^\prime_1 &= 00000001.1000000 = 1\tfrac12\\ c^\prime_3 &= 00000110.0110000 = 6\tfrac38\\ c^\prime_5 &= 00011001.1001100 = 25\tfrac{19}{32}\\ c^\prime_7 &= 01100110.0110011 = 102\tfrac{51}{128} \end{align*} \]
which we can evaluate with
\[ c^\prime_{2n+1} = \left(\frac12\right)^{2n+1} \times \sum_{i=0}^n 3 \times 16^{\,i} = 3 \times \left(\frac12\right)^{2n+1} \times \frac{1-16^{\,n+1}}{1-16} = \frac15 \times \left(2^{2n+3}-\left(\frac12\right)^{2n+1}\right) \]
giving
\[ \begin{align*} c_{2n+1} &= \frac15 \times \left(2^{2n+3}-\left(\frac12\right)^{2n+1}\right) + 2^{2n+1}\\ &= \frac15 \times 2^{2n+3} - \frac15 \times \left(\frac12\right)^{2n+1} + \frac14 \times 2^{2n+3}\\ &= \frac{9}{20} \times 2^{2n+3} - \frac15 \times \left(\frac12\right)^{2n+1}\\ &= 1\frac{4}{5} \times 2^{2n+1} - \frac15 \times \left(\frac12\right)^{2n+1} \end{align*} \]
upon replacing the leftmost cell.
Deck 10 compares the results of these formulae to the values of the generations explicitly reckoned from the contents of their boxes.

Deck 10: Automaton One Hundred And Fifty Eights's Generations

With automaton one hundred and ninety cells always reproduce into neighbouring boxes and survive unless the box to their left is occupied and the box to their right is not
\[ \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\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
so that empty boxes migrate leftwards through the population in successive generations
\[ \begin{align*} c_0 &= 00000001.0000000 = 1\\ c_1 &= 00000011.1000000 = 3\tfrac12\\ c_2 &= 00000111.0100000 = 7\tfrac14\\ c_3 &= 00001110.1110000 = 14\tfrac78\\ c_4 &= 00011101.1101000 = 29\tfrac{13}{16}\\ c_5 &= 00111011.1011100 = 59\tfrac{23}{32}\\ c_6 &= 01110111.0111010 = 119\tfrac{29}{64}\\ c_7 &= 11101110.1110111 = 238\tfrac{119}{128} \end{align*} \]
Once again dividing even and odd numbered generations, we have
\[ \begin{align*} c_0 &= 00000001.0000000 = 1\\ c_2 &= 00000111.0100000 = 7\tfrac14\\ c_4 &= 00011101.1101000 = 29\tfrac{13}{16}\\ c_6 &= 01110111.0111010 = 119\tfrac{29}{64}\\ \end{align*} \]
and
\[ \begin{align*} c_1 &= 00000011.1000000 = 3\tfrac12\\ c_3 &= 00001110.1110000 = 14\tfrac78\\ c_5 &= 00111011.1011100 = 59\tfrac{23}{32}\\ c_7 &= 11101110.1110111 = 238\tfrac{119}{128} \end{align*} \]
The former are precisely the same as those of automaton on hundred and fifty eight and so equal
\[ c_{2n} = \frac{7}{15} \times 4^{n+1} - \frac{13}{15} \times \left(\frac14\right)^n \]
whilst the latter are related to its transformed even generations by
\[ c_{2n-1} = \tfrac12 c^\prime_{2n} \]
so that
\[ c_{2n-1} = \frac12 \times \frac{7}{15} \times \left(4^{n+1} - \left(\frac14\right)^{n-1}\right) = \frac{7}{15} \times \left(2^{2n+1} - \left(\frac12\right)^{2n-1}\right) \]
Shifting \(n\) downwards by replacing it in this formula with \(n+1\) yields
\[ c_{2n+1} = \frac{7}{15} \times \left(2^{2n+3} - \left(\frac12\right)^{2n+1}\right) \]
and deck 11 confirms the veracity of it and the formula for the even generations.

Deck 11: Automaton One Hundred And Ninety's Generations

If we do not allow cells to reproduce to the left then we have automaton one hundred and eighty eight which has the rules
\[ \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\, \blacksquare \end{align*} \]
and so is a one sided automaton whose generations equal one added to the fractional parts of automaton one hundred and ninety's
\[ \begin{align*} c_0 &= 1.0000000 = 1\\ c_1 &= 1.1000000 = 1\tfrac12\\ c_2 &= 1.0100000 = 1\tfrac14\\ c_3 &= 1.1110000 = 1\tfrac78\\ c_4 &= 1.1101000 = 1\tfrac{13}{16}\\ c_5 &= 1.1011100 = 1\tfrac{23}{32}\\ c_6 &= 1.0111010 = 1\tfrac{29}{64}\\ c_7 &= 1.1110111 = 1\tfrac{119}{128} \end{align*} \]
If we define
\[ \begin{align*} c^\prime_0 & = 0.0000000 = 0 & c^{\prime\prime}_0&=00000001 = 1\\ c^\prime_1 & = 0.1000000 = \tfrac12 & c^{\prime\prime}_1&=00000011 = 3\\ c^\prime_2 & = 0.0100000 = \tfrac14 & c^{\prime\prime}_2&=00000111 = 7\\ c^\prime_3 & = 0.1110000 = \tfrac78 & c^{\prime\prime}_3&=00001110 = 14\\ c^\prime_4 & = 0.1101000 = \tfrac{13}{16} & c^{\prime\prime}_4&=00011101 = 29\\ c^\prime_5 & = 0.1011100 = \tfrac{23}{32} & c^{\prime\prime}_5&=00111011 = 59\\ c^\prime_6 & = 0.0111010 = \tfrac{29}{64} & c^{\prime\prime}_6&=01110111 = 119\\ c^\prime_7 & = 0.1110111 = \tfrac{119}{128} & c^{\prime\prime}_7&=11101110 = 238 \end{align*} \]
and label the generations of automaton one hundred and ninety with \(\hat{c}_n\) then we have
\[ \begin{align*} \hat{c}_n &= c^{\prime\prime}_n + c^\prime_n\\ c^\prime_n &= \hat{c}_n - c^{\prime\prime}_n\\ c_n &= 1 + \hat{c}_n - c^{\prime\prime}_n \end{align*} \]
Now \(c^{\prime\prime}\) repeatedly shifts in the binary digits of the number seven, one per generation, so that from the third generation onwards it may be defined by
\[ \begin{align*} c^{\prime\prime}_{4n+2} &= 0 + 1 \times \sum_{i=0}^n 7 \times 16^{\,i} = 0 + 1 \times \frac{7}{15} \times \left(16^{\,n+1}-1\right) = 0 + \frac{7}{15} \times \left(4^{2n+2}-1\right)\\ c^{\prime\prime}_{4n+3} &= 0 + 2 \times \sum_{i=0}^n 7 \times 16^{\,i} = 0 + 2 \times \frac{7}{15} \times \left(16^{\,n+1}-1\right) = 0 + \frac{7}{15} \times \left(2^{4n+5}-2\right)\\ c^{\prime\prime}_{4n+4} &= 1 + 4 \times \sum_{i=0}^n 7 \times 16^{\,i} = 1 + 4 \times \frac{7}{15} \times \left(16^{\,n+1}-1\right) = 1 + \frac{7}{15} \times \left(4^{2n+3}-4\right)\\ c^{\prime\prime}_{4n+5} &= 3 + 8 \times \sum_{i=0}^n 7 \times 16^{\,i} = 3 + 8 \times \frac{7}{15} \times \left(16^{\,n+1}-1\right) = 3 + \frac{7}{15} \times \left(2^{4n+7}-8\right) \end{align*} \]
Recalling that
\[ \begin{align*} \hat{c}_{2n} &= \frac{7}{15} \times 4^{n+1} - \frac{13}{15} \times \left(\frac14\right)^n\\ \hat{c}_{2n+1} &= \frac{7}{15} \times \left(2^{2n+3} - \left(\frac12\right)^{2n+1}\right) \end{align*} \]
we have
\[ \begin{align*} c_{4n+2} &= 1 + c^\prime_{4n+2} = 1 + \hat{c}_{4n+2} - c^{\prime\prime}_{4n+2}\\ &= 1 + \left(\frac{7}{15} \times 4^{2n+2} - \frac{13}{15} \times \left(\frac14\right)^{2n+1}\right) - \left(0 + \frac{7}{15} \times \left(4^{2n+2}-1\right)\right)\\ &= 1\frac{7}{15} - \frac{13}{15} \times \left(\frac12\right)^{4n+2}\\ \\ c_{4n+3} &= 1 + c^\prime_{4n+3} = 1 + \hat{c}_{4n+3} - c^{\prime\prime}_{4n+3}\\ &= 1 + \left(\frac{7}{15} \times \left(2^{4n+5} - \left(\frac12\right)^{4n+3}\right)\right) - \left(0 + \frac{7}{15} \times \left(2^{4n+5}-2\right)\right)\\ &= 1\frac{14}{15} - \frac{7}{15} \times \left(\frac12\right)^{4n+3}\\ \\ c_{4n+4} &= 1 + c^\prime_{4n+4} = 1 + \hat{c}_{4n+4} - c^{\prime\prime}_{4n+4}\\ &= 1 + \left(\frac{7}{15} \times 4^{2n+3} - \frac{13}{15} \times \left(\frac14\right)^{2n+2}\right) - \left(1 + \frac{7}{15} \times \left(4^{2n+3}-4\right)\right)\\ &= 1\frac{13}{15} - \frac{13}{15} \times \left(\frac{1}{2}\right)^{4n+4}\\ \\ c_{4n+5} &= 1 + c^\prime_{4n+5} = 1 + \hat{c}_{4n+5} - c^{\prime\prime}_{4n+5}\\ &= 1 + \left(\frac{7}{15} \times \left(2^{4n+7} - \left(\frac12\right)^{4n+5}\right)\right) - \left(3 + \frac{7}{15} \times \left(2^{4n+7}-8\right)\right)\\ &= 1\frac{11}{15} - \frac{7}{15} \times \left(\frac12\right)^{4n+5} \end{align*} \]
We may summarise these formulae with
\[ c_n = \frac{1}{15} \times \left(a_n - b_n \times \left(\frac12\right)^n\right) \]
where
\[ \begin{align*} a_{4n\phantom{+0}} &= 28\\ a_{4n+1} &= 26\\ a_{4n+2} &= 22\\ a_{4n+3} &= 29 \end{align*} \]
and
\[ \begin{align*} b_{2n\phantom{+0}} &= 13\\ b_{2n+1} &= 7 \end{align*} \]
which most pleasingly also correctly enumerate the first two generations
\[ \begin{align*} c_0 &= \frac{1}{15} \times \left(a_0 - b_0 \times \left(\frac12\right)^0\right) = \frac{1}{15} \times \left(28 - 13 \times 1\right) = \frac{1}{15} \times 15 = 1\\ c_1 &= \frac{1}{15} \times \left(a_1 - b_1 \times \left(\frac12\right)^1\right) = \frac{1}{15} \times \left(26 - 7 \times \left(\frac12\right)\right) = \frac{1}{15} \times 22\frac12 = 1\frac12 \end{align*} \]
Deck 12 uses them reckon the values of generations by assigning \(a_n\) and \(b_n\) according to the remainder of \(n\) divided by four.

Deck 12: Automaton One Hundred And Eighty Eight's Generations

Such enumerations of generations are not the only way in which we may think upon automata, but alas our studies must intervene before we shall have time to consider another.
\(\Box\)

References

[1] On An Age Of Wonders, www.thusspakeak.com, 2014.

[2] 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+