Back in September 1995, David Buckingham showed how to construct oscillators and glider guns of any period at least 61 in Conway’s Game of Life. His method was based on a tool called a “Herschel conduit“; a configuration of still lifes that can be used to move a Herschel from one location to another. By stitching together several of these Herschel conduits, we can create a complete track for the Herschel to move around, thus creating an oscillator (or a gun, if we let the glider that the Herschel naturally creates escape).

Herschel tracks are still used constantly in Conway’s Game of Life, and I’m starting a series of video tutorials that show how they work. Part 1 is now up:

The pattern animations throughout the video were all made with Manim. Once I get a few more videos under my belt, and my code cleaned up a bit more, I’ll share my code for making pretty Life animations.

I’ve been meaning to make a series of videos on Conway’s Game of Life for a few years now, and I finally decided that rather than rehashing topics that are already covered in the textbook, I’ll make videos explaining particularly notable new discoveries as they’re made. Unfortunately, the news that Life is omniperiodic is somewhat well-worn at this point, so I started this week with a video about the newly-discovered true period 15 and 16 glider guns (which are both the first guns of their respective periods ever found, and which were found less than 5 hours apart!):

The video does delve into some “rehashed” stuff, like what a B-heptomino is, and how guns work in general, but that’s unavoidable if I want the video to be understandable to more than 100 or so people in the world. Hopefully a few news videos like this might actually convince enough people that Life is interesting enough so as to bump that “100” number up in the near future!

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