On A Very Cellular Process


Recently my fellow students and I have been spending our free time using Professor B------'s remarkable calculating engine[1] to experiment with cellular automata, being mathematical contrivances that might be thought of as crude models of the lives of those most humble of creatures; amoebas. In their simplest form they are unending lines of boxes, some of which contain a living cell that at each generation will live, die or reproduce according to the contents of its neighbouring boxes. For example, we might say that each cell divides and its two offspring migrate to the left and right, dying if they encounter another cell's progeny.
Representing a box containing a living cell with a filled square and an empty box with a hollow one, the possible fates of the middle of three boxes are consequently
\[ \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*} \]

Sundry Triangles

Noting that this can be summarised as the middle box being empty in the next generation if its current neighbours are either both empty or both not and containing a cell otherwise, deck 1 plots the evolution of this cellular automaton from a single living cell with each generation on successive lines.

Deck 1: Our Cellular Automaton

This bears a most striking resemblance to the Sierpiński triangle, being an infinitely detailed geometrical figure that is the eventual result of dividing an equilateral triangle into four equal and similarly equilateral parts, removing the centremost of them and then repeating the procedure upon those remaining, as demonstrated by deck 2.

Deck 2: The Sierpiński Triangle

Another interesting property of our automaton is its relation to Pascal's triangle, the \(n^\mathrm{th}\) row of which contains the coefficients of the powers of \(x\) in the expansion of \((1+x)^n\), counting from zero. For example
\[ \begin{matrix} (1+x)^0 & = & 1\\ (1+x)^1 & = & 1 + x\\ (1+x)^2 & = & 1 + 2x + x^2\\ (1+x)^3 & = & 1 + 3x + 3x^2 + x^3\\ (1+x)^4 & = & 1 + 4x + 6x^2 + 4x^3 + x^4\\ \vdots & = & \vdots \end{matrix} \]
To figure the elements in each row we need simply add together those to its left and right in the previous row, setting those at their starts and ends to one, according to which its first eight rows are given by


Now if we replace the odd numbers in the table with solid squares and the even numbers with hollow ones, we have


which, upon filling the empty places between them and to their left and right with hollow squares, yields


This certainly looks like the results of our automaton, but to be sure we must prove it!

Let us begin by numbering the box containing a living cell in the first generation zero, those to its left negatively and those to its right positively. It is consequently trivially the case that every odd numbered box is empty.
In the second generation, the neighbours of every even numbered box are odd numbered and were therefore empty, meaning that they must now be empty too.
In the third generation every odd numbered box is neighboured by even numbered boxes and, by the same reasoning, must be empty.
It must therefore be the case that in even numbered generations every odd numbered box is empty and in odd numbered generations the even numbered boxes are, accounting for the empty boxes that we used to fill the gaps in Pascal's triangle.
The remaining boxes correspond either to places outside of it or to elements within it, the latter of which can only be odd if one of the elements upon its left and right in the previous row is odd and the other is even, and the former of which we treat as containing zeros. This is exactly the same as our automaton's rule that a box will contain a living cell in one generation if and only if one and only one of its neighbours in the previous generation did so.
And with that we have our proof!

Now, the \(r^\mathrm{th}\) entry in the \(n^\mathrm{th}\) row of Pascal's triangle is given by the combination
\[ {}^nC_r = \frac{n!}{r! \times (n-r)!} \]
where the exclamation mark stands for the factorial, being the product of every number from one up to and including that upon its left with the convention that the factorial of zero is one.
To prove this we first note that it yields the first and last entries of each row with
\[ \begin{align*} {}^nC_0 = \frac{n!}{0! \times (n-0)!} &= \frac{n!}{1 \times n!} = 1\\ {}^nC_n = \frac{n!}{n! \times (n-n)!} &= \frac{n!}{n! \times 1} = 1 \end{align*} \]
and then, by induction, show that it recovers the rest with
\[ \begin{align*} {}^{n-1}C_{r-1} + {}^{n-1}C_r &= \frac{(n-1)!}{(r-1)! \times (n-r)!} + \frac{(n-1)!}{r! \times (n-1-r)!}\\ &= r \times \frac{(n-1)!}{r! \times (n-r)!} + (n-r) \times \frac{(n-1)!}{r! \times (n-r)!}\\ &= (r+n-r) \times \frac{(n-1)!}{r! \times (n-r)!} = n \times \frac{(n-1)!}{r! \times (n-r)!}\\ &= \frac{n!}{r! \times (n-r)!} = {}^nC_r \end{align*} \]
We may consequently figure the state of the box at position \(r\) in the \(n^\mathrm{th}\) generation with
\[ 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, as done in deck 3.

Deck 3: Using Combinations

Alas, we find ourselves pushing Professor B------'s engine beyond its capabilities; it simply hasn't enough gears to accurately calculate the factorials required for advanced generations!
Fortunately, we need only know whether the combinations are even or odd which we can reckon by counting the multiplicities of two in each of the terms in their factorials; if their numerators and denominators have as many of them as each other then they must be odd, a fact that is exploited by our fourth deck which does so by repeatedly dividing each term by two until it becomes odd.

Deck 4: Counting Twos

You may recall that we have previously figured[2] a trick for counting the number of factors of a prime \(p\) in factorials with
\[ \sum_{j=1}^\infty \lfloor n \div p^j\rfloor \]
where \(\sum\) is the summation sign and the oddly shaped brackets are the floor of the term between them, being the greatest integer that is no greater than it. This works because there are precisely \(\lfloor n \div p^j\rfloor\) multiples of \(p^j\) between one and \(n\) and so for \(j\) equal to one we count those that are once divisible by \(p\), for \(j\) equal to two those that are also twice divisible by it and so on and so forth.
Deck 5 employs this trick to efficiently determine the evenness or oddness of the combinations.

Deck 5: Counting Twos Efficiently

To understand why the generations of this automaton resemble Sierpiński triangle we may first show that \({}^{2^k-1}C_r\) is odd for all \(r\) between zero and \(2^k-1\). This is most easily done by working in binary in which each of the \(k\) digits of \(2^k-1\) is a one and, because there is no carrying of digits, those of \(r\) and \(2^k-1-r\) are mirror images of each other. For example
\[ \begin{align*} 2^8-1 &= 255 = 11111111\\ r &= 105 = 01101001\\ 2^8-1-r &= 150 = 10010110 \end{align*} \]
Now, in binary, to divide by \(2^j\) and drop fractions we simply remove the last \(j\) digits and so our trick for counting the number of twos in the denominator of the combination yields
\[ \sum_{j=1}^\infty \lfloor r \div 2^j\rfloor + \sum_{j=1}^\infty \big\lfloor \left(2^k-1-r\right) \div 2^j \big\rfloor = \sum_{j=1}^\infty \lfloor r \div 2^j\rfloor + \big\lfloor \left(2^k-1-r\right) \div 2^j \big\rfloor = \sum_{j=1}^\infty \big\lfloor \left(2^k-1\right) \div 2^j \big\rfloor \]
since the results of the divisions at the \(j^\mathrm{th}\) step of the two sums must also be reflections of each other. Given that the final sum is equal to the number of factors of two in the numerator, the combination must be odd and so our formula for the state of the boxes simplifies to
\[ b_{2^k-1,r} = \begin{cases} \blacksquare & r \; \text{is odd} \wedge |r| \leqslant 2^k-1\\ \square & \text{otherwise} \end{cases} \]
where \(\wedge\) means and. The neighbours of all but the boxes before the first and after the last of those containing cells are consequently in the same state, and so we also have
\[ b_{2^k,r} = \begin{cases} \blacksquare & |r| = 2^k\\ \square & \text{otherwise} \end{cases} \]
In the next \(2^k-1\) generations we create two copies of the first \(2^k\) generations starting at the two boxes containing living cells and ending at generation \(2^{k+1}-1\) which must again consist of alternating states, leaving an empty inverted triangle of equal size between them.

Numbering Automata

If we replace empty boxes with zeros and filled boxes with ones, we can represent the rules of our automaton with
\[ \begin{align*} 0\,0\,0 &\rightarrow\, 0 & 0\,0\,1 &\rightarrow\, 1 & 0\,1\,0 &\rightarrow\, 0 & 0\,1\,1 &\rightarrow\, 1 \\ 1\,0\,0 &\rightarrow\, 1 & 1\,0\,1 &\rightarrow\, 0 & 1\,1\,0 &\rightarrow\, 1 & 1\,1\,1 &\rightarrow\, 0 \end{align*} \]
Reading the triples of ones and zeros as binary numbers gives us
\[ \begin{align*} 0 &\rightarrow\, 0 & 1 &\rightarrow\, 1 & 2 &\rightarrow\, 0 & 3 &\rightarrow\, 1 \\ 4 &\rightarrow\, 1 & 5 &\rightarrow\, 0 & 6 &\rightarrow\, 1 & 7 &\rightarrow\, 0 \end{align*} \]
and, by treating the number on the left of the arrows as indices of binary digits from right to left, we can define our automaton with the eight digit binary number \(01011010\) which, upon conversion to decimal, yields ninety and is known as its Wolfram code[3].
Deck 6 interprets the rules by associating the left hand box with four, the middle box with two and the right hand box with one, adding together the numbers of the boxes containing cells to yield an index \(k\) and determining whether that digit is zero or one in the automaton's rule number \(n\) by testing whether
\[ \lfloor n \div 2^k \rfloor \]
is even or odd respectively.

Deck 6: Automaton Ninety

Note that we produce the same output for rules eighteen, twenty six, eighty two, one hundred and forty six, one hundred and fifty four, two hundred and 10, and two hundred and eighteen which you can see for yourself by changing the rule number in deck 6.
Writing these out in binary yields
\[ \begin{align*} 18 &= 00010010\\ 26 &= 00011010\\ 82 &= 01010010\\ 90 &= 01011010\\ 146 &= 10010010\\ 154 &= 10011010\\ 210 &= 11010010\\ 218 &= 11011010\\ \end{align*} \]
which we can represent with \(\ast\ast01\ast010\), where the asterisks stand for those digits that might be either zero or one. This implies that the rules of the automata are
\[ \begin{align*} 0 &\rightarrow\, 0 & 1 &\rightarrow\, 1 & 2 &\rightarrow\, 0 & 3 &\rightarrow\, \ast \\ 4 &\rightarrow\, 1 & 5 &\rightarrow\, 0 & 6 &\rightarrow\, \ast & 7 &\rightarrow\, \ast \end{align*} \]
\[ \begin{align*} \square\,\square\,\square &\rightarrow\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\blacksquare\,\square &\rightarrow\, \square & \square\,\blacksquare\,\blacksquare &\rightarrow\, \ast \\ \blacksquare\,\square\,\square &\rightarrow\, \blacksquare & \blacksquare\,\square\,\blacksquare &\rightarrow\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \ast & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \ast \end{align*} \]
which makes clear the reason why three of the rules don't matter; they represent states that cannot be reached from an initial generation with a single cell by the remaining rules and so are never exercised!

A related automaton is number sixty, 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\, \square \end{align*} \]
that place a cell in a box if one and only one of it and its left hand neighbour contained a cell in the previous generation. The boxes containing cells consequently again represent odd elements of Pascal's triangle, although in this case the \(r^\mathrm{th}\) element of each row of the latter is assigned to the \(r^\mathrm{th}\) box to the right of the first cell, as demonstrated by deck 7.

Deck 7: Automaton Sixty

Note that it is trivially the case that any automaton whose number is wholly divisible by four will never contain cells in boxes to the left of the first cell.

Another is number one hundred and fifty, having 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\, \square & \blacksquare\,\blacksquare\,\square &\rightarrow\, \square & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \blacksquare \end{align*} \]
by which a cell survives if both or neither of its neighbouring boxes are populated and reproduce into its left or right neighbouring box if both they and their next neighbours are unpopulated, which is fashioned by deck 8.

Deck 8: Automaton One Hundred And Fifty

This automaton is related to the elements of a generalisation of Pascal's triangle, known as the trinomial triangle and containing the coefficients of the powers of \(x\) in the expansion of \(\left(1+x+x^2\right)^n\)
\[ \begin{matrix} (1+x+x^2)^0 & = & 1\\ (1+x+x^2)^1 & = & 1 + x + x^2\\ (1+x+x^2)^2 & = & 1 + 2x + 3x^2 + 2x^3 + x^4\\ (1+x+x^2)^3 & = & 1 + 3x + 6x^2 + 7x^3 + 6x^4 + 3x^5 + x^6\\ (1+x+x^2)^4 & = & 1 + 4x + 10x^2 + 16x^3 + 19x^4 + 16x^5 + 10x^6 + 4x^7 + x^8\\ \vdots & = & \vdots \end{matrix} \]
If we label the coefficient of \(x^k\) in \(\left(1+x+x^2\right)^n\) with \(a_{n,k}\) then, noting that the coefficient of a power of \(x\) that does not appear in a particular expansion trivially equals zero, the \(k^\mathrm{th}\) term of \(\left(1+x+x^2\right)^{n+1}\) must be
\[ a_{n+1,k} \times x^k = a_{n,k} \times x^k \times 1 + a_{n,k-1} \times x^{k-1} \times x + a_{n,k-2} \times x^{k-2} \times x^2 \]
and we consequently have
\[ a_{n+1,k} = a_{n,k} + a_{n,k-1} + a_{n,k-2} \]
We may therefore recover the coefficients by constructing a triangle whose elements in the \(n^\mathrm{th}\) row are the sum of those to its left, above it and to its right in the previous row, treating places outside of it as containing zeros, to yield


Again replacing odd elements with filled squares, and even elements and spaces beyond the triangle's bounds with hollow squares results in


which exactly follows the rules of this automaton for the simple reason that an element can only be odd if just one or all three of the elements used to figure it are themselves odd.

Mirrors And Complements

A simple transformation of an automaton is to reverse the order of the boxes to the left of each arrow, creating what is known as its mirror. For example, reflecting the rules of automaton sixty 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\, \blacksquare & \blacksquare\,\blacksquare\,\square &\rightarrow\, \blacksquare & \blacksquare\,\blacksquare\,\blacksquare &\rightarrow\, \square \end{align*} \]
which is equivalent to swapping the second binary digit with the fifth and the fourth with the seventh, in this case yielding automaton one hundred and two
\[ 60 = 0\bar01\dot1\bar11\dot00 \rightarrow 0\bar11\dot0\bar01\dot10 = 102 \]
which deck 9 shows yields generations that are reflections of the former's, consequently never populating boxes to the right of the first cell.

Deck 9: Automaton One Hundred And Two

Another is to exchange populated for unpopulated boxes, and vice versa, on both sides of each arrow to yield the complement of an automaton. For example, the complement of automaton sixty has the 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\, \square & \square\,\square\,\blacksquare &\rightarrow\, \blacksquare & \square\,\square\,\square &\rightarrow\, \blacksquare \end{align*} \]
which is equivalent to reversing its binary digits and swapping its zeros for ones and its ones for zeros
\[ 60 = 00111100 \rightarrow 00111100 \rightarrow 11000011 = 195 \]
although in this case, of course, the digits are symmetrical and so reversing them has no effect.
Deck 10 begins with every box except one containing a cell, plotting the generations upon a black background to highlight the empty boxes, clearly showing that it yields the same results as swapping the contents of the former's.

Deck 10: Automaton One Hundred And Ninety Five

Given that the results of the mirror, complement, complement of the mirror and the automaton itself are equivalent under trivial transformations we can count the number of unique automata by firstly preferring the even numbered to the odd numbered ones, then those wholly divisible by four to those not and, finally, the lesser numbered to the greater. Deck 11 uses this scheme to filter the two hundred and fifty six automata to eighty eight that are unique under those transformations.

Deck 11: Unique Automata

A Catalogue Of Automata

My fellow students and I have spent the last of our free time cataloguing cellular automata with non-trivial outcomes, which is to say more complex than a few points or lines and unique under the mirror and complement transformations.

Firstly, we examined those whose numbers are wholly divisible by four and consequently do not populate boxes to the left of the first cell, amongst which we discovered the following automata of interest
\[ 28, 60, 92, 124, 188, 220 \]
which you may experiment with yourself by changing the value of n in deck 12.

Deck 12: One Sided Automata

Of these, we found automaton number one hundred and twenty four to be of particular note, with its having triangles scattered about with no discernible regularity!

Secondly, we proceeded to work through the remaining even numbered automata, ignoring the odd numbered on account of their putting a living cell in the middle of three empty boxes and consequently filling all but a few of the boxes to the left and right of the first cell. Of those we found
\[ 18, 22, 30, 50, 54, 62, 94, 126, 150, 158, 190, 222 \]
to exhibit complex behaviour, which you may employ deck 13 to confirm.

Deck 13: Two Sided Automata

Once again, we see the peculiar combination of regular and irregular behaviour in automaton number thirty!

Unfortunately our studies must intrude for the present, but we have every intention of revisiting our automata as soon as time allows.


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

[2] On The Hydra Of Argos, www.thusspakeak.com, 2019.

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