Tim Hutton has announced the release of Ready 0.5, which is now able to support cellular automata and reaction-diffusion systems on three-dimensional honeycombs. There are a few sample patterns on Penrose tilings as well.
Replicators and Feynman diagrams
On the subject of cellular automata, Nathan Thompson discovered a variant of Conway’s Game of Life in 1994. It was termed ‘HighLife’ due to the existence of a small replicator, which copies itself every twelve generations. An early discovery was that the replicator can drag a blinker (cluster of three cells) behind it, translating itself by (8,8) every 48 generations:
For a while, people were unsure what this spaceship should be called. David Bell had recently conceived his second child, Carina (named after the constellation), and there were proposals to name the spaceship after her. Eventually, however, the community settled upon the term ‘bomber’ to describe how it appears to periodically emit small explosions every 24 generations.
Rather than considering these things as two-dimensional clusters of cells changing over time, it is convenient to abstract away most of the details. The replicator and bomber then become very simple objects, which can be viewed as ‘Feynman diagrams’:
Space and time are represented on the horizontal and vertical axes, respectively; as time progresses, one moves down the diagram. The Feynman diagram for the replicator is Pascal’s triangle modulo 2 (resembling the Sierpinski triangle), whilst the blinker pulled behind the bomber causes it to remain bounded instead of expanding forever. The replicator units killed by the blinker are represented by green dots in the diagram.
The bomber is said to travel at a speed of c/6, which means that (on average) it translates by one cell every 6 generations (timesteps). More precisely, its velocity is (8,8)c/48, as it travels 8 units up and 8 units to the left every 48 generations. This is clearly the fastest possible speed a replicator unit can move at, and is the speed at which an untamed replicator expands.
In 1999, Dean Hickerson wondered whether slower speeds are possible. In theory, a string of replicator units could push a blinker at one end and pull another at the other end. We already have a ‘pull’ reaction (the basic one performed by the bomber); a (5,3) push reaction was found by Dean Hickerson. This is described in the last paragraph of this article.
This would ordinarily be incompatible with the (8,8) pull reaction, since (5,3) isn’t the same vector as (8,8). Fortunately, a parallel replicator can subsequently push it by (3,5), for an overall displacement of (8,8). The Feynman diagram for the push reaction is much more complicated than the pull reaction:
Not much became of this idea. It was realised that such a beast would be colossal (estimated size: 2^60 replicator units), and the idea was abandoned. Occasionally, people talked about the possibility of one of these XOR-extendable spaceships, but no exhaustive searches were done.
Until now, that is. I’ve discovered the first XOR-extendable spaceship in HighLife, which I have named the Basilisk due to its length. Indeed, if printed on graph paper at the scale of one cell per millimetre, it would be long enough to reach the Moon!
Using some linear algebra, I realised that the most fruitful speed to search for was c/69. It’s not too slow, nor too fast, and most importantly the feedback polynomial (a term I’ll elaborate upon later in this article) has a sufficiently large order for me to be confident that c/69 XOR-extendable spaceships can exist. I decided that a good starting point would be to draw the Feynman diagram for the ‘head’ of this spaceship:
The colour of each dot (white or black) is obtained by adding together the two dots above it, modulo 2. This operation of addition modulo 2 is also known as exclusive disjunction, symmetric difference or simply ‘XOR’. Note that the bottom row is identical to the top row, but shifted two dots (corresponding to (8,8) in the original cellular automaton) to the left. These constraints are sufficient to extend the pattern above ad infinitum.
We can do the same for the tail of the spaceship, shown below. The two green dots at the back end correspond to the standard pull reaction exhibited by the bomber spaceship. There are many possible tails, and I had to include all of them in my search program to ensure that a solution was found.
Ideally, we want these two diagrams to ‘match up’ somewhere, so that we can connect the head and tail. This is not easy, since it requires the top row to agree in 46 consecutive bits. It’s quite possible that the string of bits enters a periodic behaviour before a match is found; that’s why we need to search for matches with many potential tails.
It transpires that the string of bits can be generated by a linear feedback shift register. This is defined in a similar manner to the Fibonacci sequence, but where each term depends on the previous 46 terms, rather than the previous 2. Also, it is over the finite field F_2 instead of the integers. The behaviour is obviously cyclic, and a little linear algebra and trial-and-error shows that the period is precisely 987964849939.
Due to the huge number of head/tail pairings, a match occurs well before that. The completed spaceship is just under 85 billion replicator units long. Searching for this required the development of a super-optimised algorithm (several orders of magnitude faster than the naive approach) involving matrix exponentiation and a hash table. After a couple of hours of searching, it stumbled across four potential solutions in quick succession. The one which looked the most promising is shown below:
Obviously, I can’t generate an RLE file for the whole pattern. I have, however, produced a proof-of-concept pattern file, featuring an ellipsis to show where I’ve omitted over 84 billion replicator units. You can view and run this in Golly (it works for about 18000 generations before the omission catches up to the ends and destroys the spaceship; the complete Basilisk runs smoothly forever).
Since the proof-of-concept works, and I’ve confirmed by linear algebra that the head and tail do indeed match up, the existence of the Basilisk is rigorously proved.