Finally On A Very Cellular Process

| 0 Comments

Over the course of the year[1][2][3] my fellow students and I have been utilising our free time to explore the behaviour of cellular automata, which are mechanistic processes that crudely approximate the lives and deaths of unicellular creatures such as amoebas. Specifically, they are comprised of unending lines of boxes, some of which contain cells that are destined to live, dive and reproduce according to the occupancy of their neighbours.
Most recently we have seen how we can categorise automata by the manner in which their populations evolve from a primordial state of each box having equal chances of containing or not containing a cell, be they uniform, constant, cyclical, migratory, random or strange. It is the latter of these, which contain arrangements of cells that interact with each other in complicated fashions, that has lately consumed our attention and I shall now report upon our findings.

Recall that our automata operate by rules which specify whether or not a box will contain a living cell in the next generation according to whether or not it and its immediate neighbours do so in the current generation. Using black squares to represent occupied boxes and white squares to represent unoccupied boxes, an example of such rules are
\[ \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*} \]
whereby a box will only contain a cell if it was empty in the previous generation and just one of its neighbours was not.
If we replace the empty squares with zeros and the filled squares with ones then we can represent these rules as mappings between binary numbers
\[ \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 translate to those between the decimal and binary digits
\[ \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*} \]
Treating the former as indices of the digits of another binary number, counting from the right, and the latter as the values of those digits, we recover \(00010010\) which is equal to eighteen. Such numbers are known as the Wolfram codes[4] of cellular automata and precisely specify the two hundred and fifty six sets of rules, of which eighty eight are unique with respect to the symmetries of exchanging left with right and populated with unpopulated boxes.

It has been automaton one hundred and ten that has commanded our attention these last few months, having 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*} \]
which my fellow students and I have put together deck 1 to demonstrate in intricate detail.

Deck 1: Automaton One Hundred And Ten

Strikingly, there are several conglomerations of populated and unpopulated boxes, which we have come to think of as creatures called gliders, that over the generations swoop through fields of boxes whose evolution yields a history of small empty triangles, at least until they encounter one another.
In the absence of such creatures those fields are stable, in the sense that an infinite repetition of the pattern of the fourteen occupied and unoccupied boxes
\[ \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare \]
will enter into a migratory state, as demonstrated by deck 2 which, reading from right to left, represents it with the binary number
\[ 10010001111101 = 9341 \]
and uses the position of each box modulo fourteen to index its digits.

Deck 2: The Fertile Field

A Catalogue Of Creatures

An especially diligent student of our acquaintance[5] has made a catalogue of every such creature that arises spontaneously from random initial populations. Of these, the simplest are
\[ \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\blacksquare\,\phantom{\square}\, \square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\\ \blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\\ \square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\\ \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\blacksquare\,\phantom{\square}\, \square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square \]
and
\[ \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\\ \blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\\ \square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\square\,\phantom{\square}\, \blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\\ \square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\blacksquare\,\square\,\phantom{\square}\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\\ \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare \]
denoted \(A\) and \(B\) respectively. We can represent their generations with ordered quadruples representing the number of initial boxes from the field to their left, the number of final boxes from it to their right, the number of boxes from which they are comprised and the binary number formed by the latter in the same fashion as that of the field
\[ \begin{align*} A &= \{\phantom{0}0,\, \phantom{0}3,\, \phantom{0}3,\, \phantom{0}5\} \rightarrow \{\phantom{0}4,\, 13,\, \phantom{0}3,\, \phantom{0}7\} \rightarrow \{10,\, \phantom{0}7,\, \phantom{0}3,\, \phantom{0}7\}\\ B &= \{11,\, \phantom{0}8,\, \phantom{0}3,\, \phantom{0}7\} \rightarrow \{\phantom{0}1,\, \phantom{0}4,\, \phantom{0}3,\, \phantom{0}0\} \rightarrow \{\phantom{0}4,\, \phantom{0}1,\, \phantom{0}3,\, \phantom{0}1\} \rightarrow \{\phantom{0}7,\,12,\,\phantom{0}3,\,\phantom{0}2\} \end{align*} \]
This is a particularly convenient notation for placing these creatures within fields, as demonstrated by deck 3.

Deck 3: The B And A Creatures

Now the \(A\) creatures can survive in extremely close proximity to one another with, for example, two, three, four and five of them given by
\[ \begin{align*} A^2 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\\ A^3 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\phantom{\square}\, \square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\\ A^4 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\\ A^5 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \square\,\square\,\square\,\blacksquare\,\square \end{align*} \]
which we may encode with
\[ \begin{align*} A^2 &= \{0, 7, 5, 29\}\\ A^3 &= \{10, 3, 5, 23\}\\ A^4 &= \{10, 7, 7, 119\}\\ A^5 &= \{0, 7, 9, 477\} \end{align*} \]
as evidenced by deck 4.

Deck 4: A Creatures In Close Formation

A more complex example of formation gliders are the leftward migrating \(\bar{B}^n\), the first three of which are given by
\[ \begin{align*} \bar{B}^1 &= \small{\blacksquare\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare}\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\\ \bar{B}^2 &= \small{\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare}\\ \bar{B}^3 &= \small{\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare} \end{align*} \]
or
\[ \begin{align*} \bar{B}^1 &= \{3, 0, 19, 302623\}\\ \bar{B}^2 &= \{7, 11, 27, 74501992\}\\ \bar{B}^3 &= \{11, 8, 35, 32882764867\} \end{align*} \]
as demonstrated by deck 5.

Deck 5: B-bar Formation Gliders

A still more complex example are \(\hat{B}^n\), starting with
\[ \begin{align*} \hat{B}^1 &= \small{\blacksquare\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square}\\ \hat{B}^2 &= \small{\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\phantom{\square}\, \,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare}\\ \hat{B}^3 &= \small{\blacksquare\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\square\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\phantom{\square}\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square} \end{align*} \]
which we may summarise as
\[ \begin{align*} \hat{B}^1 &= \{3, 12, 24, 1285663\}\\ \hat{B}^2 &= \{11, 4, 33, 7515614275\}\\ \hat{B}^3 &= \{3, 12, 42, 1652473699871\} \end{align*} \]
and are exercised by deck 6.

Deck 6: B-hat Formation Gliders

Next we have a trio of creatures that migrate vertically and a pair that migrate rightwards
\[ \begin{align*} C_1 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\\ C_2 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\\ C_3 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\\ D_1 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\\ D_2 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\, \blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare \end{align*} \]
represented by
\[ \begin{align*} C_1 &= \{11, 4, 8, 24\}\\ C_2 &= \{7, 0, 10, 626\}\\ C_3 &= \{11, 4, 10, 99\}\\ D_1 &= \{7, 8, 10, 1006\}\\ D_2 &= \{0, 8, 11, 1821\} \end{align*} \]
which my fellow students and I have put together in deck 7.

Deck 7: The C And D Creatures

A further pair of leftward moving gliders are the solitary \(\bar{E}\) and the compound \(E^n\), given by
\[ \begin{align*} \bar{E}\phantom{^1} &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\\ E^1 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\square\,\blacksquare\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\\ E^2 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\\ E^3 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\square\,\square\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\\ E^4 &= \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare \end{align*} \]
or equivalently
\[ \begin{align*} \bar{E}\phantom{^1} &= \{0, 8, 13, 4621\}\\ E^1 &= \{0, 12, 7, 9\}\\ E^2 &= \{11, 4, 12, 115\}\\ E^3 &= \{0, 8, 13, 5001\}\\ E^4 &= \{7, 0, 22, 2562498\} \end{align*} \]
whose evolution is illustrated by deck 8.

Deck 8: The E-hat And En Gliders

The penultimate pair are the leftward migrating lone and pack creatures \(F\) and \(G^n\)
\[ \begin{align*} F\phantom{^1} &= \small{\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\, \phantom{\square}\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square}\\ G^1 &= \small{\blacksquare\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\square\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square}\\ G^2 &= \small{\blacksquare\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare}\\ G^3 & = \small{\blacksquare\,\square\,\blacksquare\, \phantom{\square}\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare}\\ G^4 &= \small{\blacksquare\,\square\,\blacksquare\, \phantom{\square}\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare} \end{align*} \]
which are encoded as
\[ \begin{align*} F\phantom{^1} &= \{11, 4, 14, 1560\}\\ G^1 &= \{3, 0, 21, 1097307\}\\ G^2 &= \{3, 4, 25, 28545499\}\\ G^3 & = \{3, 8, 29, 504235747\}\\ G^4 &= \{3, 4, 27, 113229464\} \end{align*} \]
and demonstrated by deck 9.

Deck 9: The F And Gn Creatures

Finally, we have the particularly complicated leftward gliding \(H\) and \(!\)
\[ \begin{align*} H &= \scriptsize{\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\phantom{\square}\, \blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\blacksquare}\\ ! &= \scriptsize{\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\, \phantom{\square}\,\square\,\square\,\square\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\phantom{\square}\, \blacksquare\,\square\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\blacksquare\,\square\,\square\,\square\,\blacksquare\,\square\,\square\,\blacksquare\,\blacksquare} \end{align*} \]
or
\[ \begin{align*} H &= \{7, 4, 42, 549429510126\}\\ ! &= \{7, 0, 34, 9768131688\} \end{align*} \]
the latter of which emits \(A\) and \(B\) gliders as it migrates, as demonstrated by deck 10.

Deck 10: The H And ! Creatures

A Catalogue Of Collisions

Our industrious compeer then set to studying the various ways in which those creatures might interact. For example, there are six possible collisions between \(A^4\) and \(\bar{E}\), the first two of which result in another \(A^4\) and \(\bar{E}\), and a \(C_2\) respectively, as illustrated by deck 11.

Deck 11: The First Two A4 and E-bar Collisions

The next two collisions yield a \(C_2\), and a \(B\), a \(\bar{B}^1\) and an \(F\) respectively, as shown by deck 12.

Deck 12: Another Pair Of A4 and E-bar Collisions

The final pair, demonstrated by deck 13, yield another triplet of \(B\), \(\bar{B}^1\) and \(F\), and another \(C_2\).

Deck 13: The Final Pair Of A4 and E-bar Collisions

Note that whilst the second, third and sixth collisions all result in a \(C_2\), they each emerge at a different relative position, as do the triplets of \(B\), \(\bar{B}^1\) and \(F\) that are spawned by the fourth and fifth.

Furthermore, there are four possible collisions between \(C_2\) and \(\bar{E}\) creatures, the first of which yields an \(F\) and a \(C_1\) creature and the second of which produces three \(B\) creatures, as shown by deck 14.

Deck 14: The First Two C2 And E-bar Collisions

Deck 15 shows that the third collision results in a \(\bar{B}^1\), three \(B\) and an \(A\) glider, and that the fourth yields another \(C_2\) and \(\bar{E}\).

Deck 15: The Second Two C2 And E-bar Collisions

A remarkable property of the last of these is that both gliders emerge offset by the same number of generations and so, if we place them carefully, fleets of \(C_2\) and \(\bar{E}\) creatures may cross each others' paths without disturbing their relative positions, as demonstrated by deck 16.

Deck 16: Crossing Paths

Logical Creatures

It consequently struck that assiduous student that the \(C_2\) gliders could be used to represent a paper tape of data, read from right to left, and the the \(\bar{E}\) gliders could be used to construct a moving table of data that could be conditionally appended to it by collisions with \(A^4\) creatures which he dubbed ossifiers, as illustrated by figure 1 which is reproduced from his report.

Figure 1: Appending Table Data To Tape Data

To facilitate the conditional transmission of table data he represented each of the letters N and Y upon the tape with two pairs of \(C_2\) creatures, the former having them more closely placed to one another than the latter. These interact with a conglomeration called a leader to emit either an \(A^3\) or a trio of \(A\) to the right, known as an acceptor and a rejector respectively, simultaneously ceasing the propagation of the tape letters, as shown by figure 2.

Figure 2: N To Reject, Y To Accept
 

Note that the \(\bar{E}\) that are ejected to the left are out of phase with the rest of the table data so that they pass through the ossifiers that commit them to the tape.
A pair of formations called primary and standard components are used to represent N and Y letters forming words in the table data, the former being the first to be placed after a leader and the latter following behind. Each letter is represented by a pair of these components with the distance between them determining which; larger for N and smaller for Y.
When colliding with an acceptor these pairs of components yield two pairs of \(\bar{E}\) gliders, as shown by figure 3.

Figure 3: Accepting Primary And Standard Table Components
 

When they are ossified the spacing between them is inverted so that a large gap in the table data becomes a small gap in the tape data and vice-versa, yielding the correct forms for its N and Y letters.
Conversely, when colliding with rejectors these components are erased, as illustrated by figure 4.

Figure 4: Rejecting Primary And Standard Table Components
 

To stop acceptors and rejectors from interacting with subsequent table data, we use a different species of leader, known as a raw leader. The collisions between this and both of the former stop their progression and result in a normal leader, as shown by figure 5.

Figure 5: Blocking Acceptors And Rejectors With A Raw Leader



Now it so happens that if we want to append an empty element from the table data to the tape data by placing a leader without any following letters, the distances to subsequent output \(\bar{E}\) gliders are disturbed and we must consequently use yet another species of leader, known as a short leader, in such eventualities, which figure 6 shows yields a rejector for an N with an acceptor and a Y with a rejector, the letter on the tape being of no consequence if the word on the table is empty and therefore free for us to choose.

Figure 6: The Short Leader
 

Once again, the \(\bar{E}\) gliders emitted to the left are out of phase with the table data and will pass through the ossifiers.

Since the initial tape data is blocked during its interactions with the table data we may place further table data to the right that will collide with the ossified results and we are consequently equipped with a mechanism for the iterative acceptance or rejection of words. The talented academician to whom we owe this analysis finally proved that, with sufficient patience and care we may place ossifiers to the left, tape data in the middle and table data to the right in such a fashion as to exercise any form of logical procedure, making automaton one hundred and ten just as capable, albeit somewhat inefficiently, of performing the same calculations as our esteemed Professor B------'s clockwork mathematical machine[6]!
\(\Box\)

References

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

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

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

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

[5] Cook, M., Universality in Elementary Cellular Automata, Complex Systems, Vol. 15, No. 1, 2004.

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

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+