Lifeline was a newsletter for “enthusiasts of Conway’s Game of Life” that was published by Robert Wainwright in the early 1970’s. It and a handful of Scientific American articles were some of the only places ever to describe and coordinate the multitude of discoveries in the game during its early years. It ran for 11 issues from March 1971 through September 1973 and it was the first place in which the following discoveries/inventions (among others) were described:

• Several oscillators, such as candleabra, cuphook, double ewe, hustler, Kok’s galaxy, octagon II, quasar, and the twin bees shuttle.
• Several agars, including squaredance and several that are unnamed.
• The three grandparents of the R-pentomino, which are the longest-lived patterns with 5 or fewer cells.
• Immigration, a two-player variant of Conway’s Game of Life.
• The “new gun“, which was the second glider gun ever constructed.
• Bill Gosper’s famous breeder, the first pattern constructed that grows quadratically.
• The switch engine and related glider-producing switch engine.
• And on and on and on…

Unfortunately, Lifeline has been extremely difficult to find because only about 500 copies of the newsletter were distributed and they were distributed some 40 years ago. Thanks to someone who found a set of the newsletters in the bottom of a box somewhere however, I have been able to scan them and get all eleven issues online at the LifeWiki:

Number 1 • Number 2 • Number 3 • Number 4 • Number 5 • Number 6

Number 7 • Number 8 • Number 9 • Number 10 • Number 11

All eleven issues have page scans provided as images, the first five issues have been transcribed to text, and the first four issues have had their images updated/pretty-ified a bit. Also, you can download a PDF of the first issue below. So go read and learn about the early days of Life! And if you’re feeling generous, help transcribe some of the later issues to text.

Download: Lifeline Number 1 [pdf — 5.52MB]

One of the more exciting things to happen in my world this week was the discovery of a methuselah with lifespan 31,192 in Conway’s Game of Life. A methuselah is a small pattern that behaves chaotically for a large number of generations before settling down into a predictable mess.

The pattern, which has been named “Edna” (after Methuselah’s wife), was found by Erik de Neve via the Online Life-Like CA Soup Search and is the second notable discovery of the soup search (the first being the first infinitely-growing pattern in the 2×2 rule). Edna is now the longest-lived known (non-infinitely-growing) pattern that fits within a 20×20 square, beating the previous record-holder by over 2,000 generations.

Congratulations to Erik for finding the pattern after evolving a whopping 425 million random patterns.

The original 31,192-generation form of Edna

A 26-cell form of Edna with lifespan 31,082

Those of you familiar with Conway’s Game of Life probably know of its two most basic spaceships: the glider and the lightweight spaceship (shown below). The glider travels diagonally by one cell every four generations (and thus its speed is said to be “c/4”) and the lightweight spaceship travels orthogonally by two cells every four generations (and so its speed is denoted by “2c/4” or “c/2”).

The glider

Lightweight spaceship

A natural question to ask is whether or not there are any spaceships that travel faster than c/4 diagonally or c/2 orthogonally. John Conway proved in 1970 (very shortly after inventing the Game of Life) that the answer is no. I present this proof here, since it’s a bit difficult to find online (though Dave Greene was kind enough to post a copy of it on the ConwayLife.com forums).

Theorem 1. The maximum speed that a spaceship can travel in Conway’s Game of Life is c/4 diagonally and c/2 orthogonally.

Proof. We begin by proving the c/4 speed limit for diagonal spaceships. Consider the grid given in Figure 1 (below). If the spaceship is on and to the left of the diagonal line of cells defined by A, B, C, D, and E in generation 0, then suppose that cell X can be alive in generation 2.

Figure 1: The spaceship is to the left of A, B, C, D, and E

Well, if cell X is alive in generation 2, then cells C, U, and V must be alive in generation 1. This means that U and V must have had 3 alive neighbours in generation 0, so each of B, C, D, J, and K must be alive in generation 0. This means that C must have at least four live neighbours in generation 0 though, so there is no way for it to survive to generation 1, which gives a contradiction.

It follows that X can not be alive in generation 2. In other words, if the spaceship is behind the diagonal line A, B, C, D, E in generation 0, then it must be behind the diagonal line defined by U and V in generation 2. It follows that can not travel faster than c/4 diagonally.

To see the corresponding result for orthogonal spaceships, just use two diagonal lines as in Figure 2. If a spaceship is on and below the diagonal lines defined by the solid black cells in generation 0, then we already saw that it must be on and below the diagonal lines defined by the striped cells in generation 2. It follows that it can not travel faster than c/2 orthogonally.

Figure 2: The spaceship is on and below the solid black cells in generation 0

Notice that this result doesn’t only apply to spaceships, but also to other configurations that are (initially) finite and travel across the grid, such as puffers and wickstretchers. Also, this result applies to many Life-like cellular automata — not just Conway’s Game of Life.

In particular, these speed limits apply to any of the 2¹² = 4096 Life-like cellular automata in the range B3/S – B345678/S0123678. That is, these speed limits apply to any rule on the 2D square lattice such that birth occurs for 3 neighbours but not 0, 1, or 2 neighbours, and survival does not occur for 4 or 5 neighbours. But are the spaceship speed limits attained in each of these rules? The regular c/4 glider only works in the 2⁸ = 256 rules from B3/S23 – B3678/S0235678. In the remaining rules, not much is known; some of them have c/3 orthogonal spaceships, some have c/5 orthogonal spaceships, and some have no spaceships at all (such as any of the rules containing S0123, which can not contain spaceships because the trailing edge of the spaceship could never die). Of particular interest are the sidewinder and this spaceship, which play the c/4 diagonal and c/2 orthogonal roles of the glider and lightweight spaceship, respectively, in B3/S13 (as well as several other rules).

So what about the other B3 (but not B0, B1, or B2) rules? If cells survive when they have 4 or 5 cells, then it’s conceivable that spaceships might be able to travel faster than c/4 diagonally or c/2 orthogonally because Theorem 1 does not apply to them. It turns out that they indeed can travel faster diagonally, but somewhat surprisingly they can not travel faster orthogonally.

Theorem 2. In any Life-like cellular automaton in which birth occurs when a cell has 3 live neighbours but not 0, 1, or 2 live neighbours, the maximum speed that a spaceship can travel is c/3 diagonally and c/2 orthogonally.

Proof. The trick here is to consider lines of slope -1/2 as in Figure 3 below. It is possible (though a bit more complicated) to prove the c/3 diagonal speed limit using a diagonal line as in Figure 1 for Theorem 1, but the orthogonal speed limit that results is 2c/3. What is presented here is the only method I know of proving both the diagonal speed limit of c/3 and the orthogonal speed limit of c/2.

Figure 3: The spaceship is below A, B, C, D, E, and F in generation 0

Suppose that a spaceship is on and below the line defined by the cells A, B, C, D, E, and F in Figure 3 in generation 0. It is clear that Y can not be alive in generation 2, since its only neighbour that could possibly be alive in generation 1 is K. Similarly, X can not be alive in generation 2 because its only neighbours that can be alive in generation 1 are B and K. It follows that in generation 2, the spaceship can not be more than 1 cell above the line A, B, C, D, E, F.

More mathematically, this tells us that the maximum speed of a spaceship that travels x cells horizontally for every y cells vertically can not travel faster than max{x,y}c/(x+2y). Taking x = y = 1 (diagonal spaceships) gives a speed limit of c/3. Taking x = 0, y = 1 (orthogonal spaceships) gives a speed limit of c/2.

Finally, it should be noted that even though these spaceship speed upper bounds apply to a wide variety of different rules, many rules don’t even have spaceships (even relatively simple rules containing B3 in their rulestring). For example, no spaceships are currently known in the rule “maze” (B3/S12345), and it seems quite believable that there are no spaceships to be found in that rule. I would love to see a proof that maze contains no spaceships, but it seems that there are too many cases to check by hand. I may end up trying a computer proof sometime in the near future.

One of the things that has bothered me severely with the status of Conway’s Game of Life on the internet (and the main reason that I started the LifeWiki) is the severe fragmentation of information about the game — there are tidbits of knowledge sprinkled all over the place, but it’s quite a task to find a complete collection of patterns of a specific type unless you already know where to look. Fortunately, this fragmentation problem just got knocked around quite a bit by the release of Golly 2.1.

Golly is an open-source, cross-platform application for exploring Conway’s Game of Life (and it is probably currently the most widely-used such program). Version 2.1 was just released this week, and it’s a particularly exciting update from my point of view because it introduces a feature that has been long-needed in the Game of Life world — access to online pattern collections.

The pattern collections that Golly 2.1 can access by default are as follows:

• The LifeWiki pattern archive
• David Eppstein’s database of gliders in Life-like cellular automata
• Alan Hensel’s pattern collections
• Jason Summers’ pattern collections

Additionally, Golly can directly download rules from the cellular automata Rule Table Repository and scripts from the Golly Scripts Database. So now all the interested Lifer has to do to find out about (for example) period 51 oscillators is open up the LifeWiki pattern archive, select “oscillators”, and either load a relevant pattern or click on the help link beside it to bring up the corresponding page at LifeWiki. Take that, fragmentation of information.

Anyway, other changes have of course been made for the new release of Golly as well — a complete list can be found here. Or just go right ahead and…

Download Golly

One of the most interesting patterns that has ever been constructed in Conway’s Game of Life is primer, a gun that fires lightweight spaceships that represent exactly the prime numbers. It was constructed by Dean Hickerson way back in 1991, yet arguably no pattern since then has been constructed that’s as interesting. It seems somewhat counter-intuitive at first that the prime numbers, which seem somehow “random” or “unpredictable”, can be generated by this (relatively simple) pattern in the completely deterministic Game of Life.

Primer, the prime-generating gun

The gun works by firing lightweight spaceships westward, and destroying them via glider guns that emulate the Sieve of Eratosthenes. A lightweight spaceship makes it past the left edge of the gun at generation 120N if and only if N is a prime number (though for technical reasons, 2 and 3 are not outputted).

The first six lightweight spaceships output by primer

It wasn’t too long after making primer that Hickerson realized that he could attach a gun to the bottom-left corner of it to turn it into a twin prime calculator by allowing each lightweight spaceship through only if another lightweight spaceship passed through 240 generations earlier. Similarly, Jason Summers constructed a Fermat prime calculator in 2000 by shooting a glider at the lightweight spaceship stream every generation of the form 120(2^N + 1), which ends up detecting exactly the Fermat primes.

So what other families of primes can we compute in Life by altering the output of the original prime-generating gun?

Mersenne Primes

Mersenne primes can easily be computed using the exact same method as was used in the Fermat prime calculator — use a 7-engine Cordership (in blue below) to bounce a glider back at the stream of lightweight spaceships, with the time required for the glider to reach the stream doubling each time. An inverter (in green below) eliminates all lightweight spaceships that try to get past it unless it just received a glider from the Cordership. By fiddling around with timing a tiny bit, we then have a Mersenne prime calculator:

Mersenne Prime Calculator

• Java link: here
• RLE file: here

Prime Quadruplets

Four prime numbers are said to form a prime quadruplet if they are of the form (p, p+2, p+6, p+8) for some prime number p, which is the closest that four prime numbers can be together (except for the degenerate cases of (2,3,5,7) and (3,5,7,11)). Prime quadruplets are easy to compute because they can be thought of as consecutive pairs of twin primes. Since we already have a twin prime calculator, we can just repeat its reaction.

The twin prime calculator works by attaching a period 240 gun (in green below) to the bottom-left corner of primer. If it is timed correctly, it has the effect of allowing a lightweight spaceship through at generation 240N if and only if a lightweight spaceship tried to pass through at generation 240(N-1). Thus, it will only allow a lightweight spaceship through if it represents a prime number of the form p+2, where p is another prime number. Well, simply attaching a period 720 gun (in blue below) then allows a spaceship through at generation 720N if and only if a lightweight spaceship tried to pass through at generation 720(N-1). This has the effect of allowing a lightweight spaceship to pass through only if it represents a twin prime pair (p,p+2), and there is another twin prime pair of the form (p-6,p-4). That is, the only lightweight spaceships allowed through are those representing the upper members of prime quadruplets.

Prime quadruplet calculator

• Java link: here
• RLE file: here

Prime Pairs of the Form (p, p+2k)

The twin prime calculator mentioned earlier gives a way of computing prime pairs of the form (p,p+2), but what about pairs where the gap is larger than 2? For example, the k=2 case gives what are known as cousin primes, and the k=3 case gives sexy primes (yes, really).

For the case of cousin primes, the thing to notice is that every pair of cousin primes (except for the first pair, (3,7)) must be of the form (6n+1, 6n+5) for some natural number n. Thus, we can use two period 720 guns (in blue below) to allow only the upper prime in a cousin prime pair to pass through. This is achieved by having the top gun fire at the lightweight spaceships representing primes of the form 6n+1 — if a lightweight spaceship is hit, then a block is created in the path of the other gun, which is fired at lightweight spaceships representing primes of the form 6n+5. If a prime was present at 6n+1, then the lightweight spaceship makes it through unharmed at 6n+5. If there was no prime present at 6n+1, then the bottom gun destroys the lightweight spaceship representing 6n+5.

Cousin prime calculator

• Java link: here
• RLE file: here

Extending this idea to prime pairs of the form (p,p+2k) for k ≥ 3 is a bit more challenging, however, because it is possible for pairs to overlap. For example, (37,43) is a sexy prime pair, as is (41,47). Up until now we have only been able to detect single pairs at a time, since the block that acts as our “counter” that keeps track of whether a prime was detected earlier is placed in the stream of incoming lightweight spaceships. Thus, if it’s possible for two pairs to overlap, we will get lightweight spaceships colliding with the block, causing a mess.

To get around this problem, we use a device (known as a fanout, in green below) that duplicates the stream of lightweight spaceships. We then check for certain pairs on one stream, and the rest of the pairs on the other stream (these devices are outlined in blue below). Once we’re done, we merge the resulting streams of lightweight spaceships back together (using the devices in purple below).

To make this process a bit more explicit, I present a gun that computes prime pairs of the form (p,p+8). In particular, a lightweight spaceship will make it past the left edge of this pattern at about generation 1620+120N if and only if both N and N+8 are prime.

(p, p+8) prime calculator

• Java link: here
• RLE file: here

We now have all of the tools needed to build any pattern that computes prime pairs of the form (p, p+2k) as long as k = 1 or 2 (mod 3), though we may need to use the fanout device multiple times if it’s possible for more than one pair to overlap. If k = 0 (mod 3), however, it’s much more difficult to construct the desired pattern, because not only can you have overlapping prime pairs like (5, 11) and (7, 13), but you can have prime pairs in sequence such as (5, 11) and (11, 17). This problem can be remedied using the same tools as used in the (p,p+8) prime calculator, though you may need to use a lot of fanout devices to make things work. For example, computing the sexy primes using these tools would require at least four fanouts, and some clever elimination logic on each of the resulting five lightweight spaceship streams. I don’t feel up to that task myself, but it’s nice to know that we have a method for constructing a sexy prime calculator.

In a couple of recent posts, I argued that random patterns in Conway’s Game of Life tend, on average, to live longest when they have an initial density of 37.5% cells being alive. In this post, rather than looking at the distribution of the average lifespan for various initial densities, I will fix the density at 37.5% and look at the distribution of lifespans that results, and use that to estimate what the maximal lifespan of any small pattern is (as in my previous posts, I will use 20×20 starting patterns). As before, I will explore both the case when we simulate Life on a torus and when we simulate it on an infinite plane.

Lifespan Distribution on a Torus

After simulating 175000 random patterns on a 20×20 torus, the distribution of the lifespans was as follows:

The bins in the graph have a width of 10, and the peak occurs in the lifespan 91 – 100 bin. Some other interesting stats include:

• Maximum observed lifespan: 2092
• Minimum observed lifespan: 14
• Average lifespan: 210
• Median lifespan: 164
• Standard deviation of lifespan: 159.3

In order to try to estimate the longest lifespan of any pattern on a 20×20 torus, I will assume that if the lifespan is above 100, then it follows an exponential distribution, which appears to be a reasonable assumption given the above histogram. Indeed, this leads to the following histogram, which has the exponential of best fit overlaid in black. The equation of the exponential is y = 9088.7(0.938)^x, and the R² value is 0.997 (that’s one heck of a good fit).

Now that we have our exponential of best fit, we can get an estimate of the maximal lifespan in this scenario by assuming that the lifespan of the 2^20*20 different patterns are independent of each other (this may not be a particularly good assumption, as two patterns, for example, will have the same lifespan if they are translations of each other — nonetheless it seems that the number of reductions that can be made by symmetry arguments like that is tiny compared to the total number of such patterns, so let’s roll with it). We then set

and solve for x to get a maximal lifespan of x = 4474. This seems believable and not particularly shocking to me given the statistics that I listed earlier.

Lifespan Distribution on a Plane

Typically, Life enthusiasts are more interested in results on the infinite plane than on a torus, as it leads to behaviour that is much more chaotic and unpredictable. For example, even though we just saw that the longest-lived 20×20 pattern on a torus likely lives for less than 4500 generations, there is a known 9×15 pattern that lives on the plane for over 29000 generations. We will now proceed analogously to the torus discussion above to see how much better we can reasonably expect to do. We begin with the distribution of the lifespan based on 60000 initial 20×20 patterns:

The bins in the graph have a width of 50, and the peak occurs in the lifespan 151 – 200 bin. The other basic stats are listed below, and as we would expect, the average lifespan and the standard deviation of lifespans are both much greater on the plane than they are on the torus.

• Maximum observed lifespan: 13612
• Minimum observed lifespan: 15
• Average lifespan: 678
• Median lifespan: 368
• Standard deviation of lifespan: 885.6

The main difference with the analysis in this situation is that instead of assuming the lifespan itself follows an exponential distribution, I will assume that some power of the lifespan follows an exponential distribution; the reason for this is that the R² is quite low if we try to fit an exponential to the distribution of the lifespans itself. Fitting an exponential to lifespan^0.75 seems to give the maximum R² value (0.9857), so this is what I will use. The following histogram shows the curve of best fit, which has the equation y = 1854.6(0.957)^x, where this time x = lifespan^0.75.

Finally, we follow our method from before and set

and solve for x to get a maximal lifespan of x = 120795. Of course, this number should be taken with a grain of salt, because that pattern I mentioned earlier that has a lifespan of over 29000 generations was found during a simulation of a whopping 12 billion 20×20 patterns, while our equation of best fit tells us that after 12 billion patterns, we would expect only to see a pattern with lifespan 6206 (when really it should only take about 400 patterns to see such a lifespan). Similarly, in the longest-lived patterns found by the Online Life-Like CA Soup Search, a pattern has been found with lifespan 24389. According to our formula, we should have to look at roughly 9 million billion billion billion soups before finding such a pattern, but only 40 million soups have actually been searched.

This all seems to suggest that the longest-lived pattern in a 20×20 box may in fact live considerably longer than 120000 generations, which goes to show just how in the dark we are when it comes to some of these simple questions — since the search space is so unimaginably huge, we likely will never know for sure what the true upper limit is.

Downloads:

• Lifespan raw data and graphs [.zip of an Excel spreadsheet — 2.91MB]
• Lifespan recorder scripts [.zip of two Golly Python scripts]