## Spaceship Speed Limits in "B3" Life-Like Cellular Automata

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”).

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.

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.

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^{12} = 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^{8} = 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.

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.

I guess we should give up on light-speed travel then..if ships can’t move faster than c/2 orthogonally.. 🙂

It’s worth noting that infinitely-large configurations can travel faster. My little game of life iphone app has a 16×22 layout where opposite edges continue onto each other, so a straight line across is effectively infinite. A straight line with extra cells on just one side starts sweeping the screen (orthogonally) at the neck-breaking pace of c. Fun to watch it chase down gliders.

This article was of no use to me, as the links to the pics are broken and as the date is 2009. Life seems to have dried up, and after 48 years, nothing new or usable* has appeared. Websites are archived and links are broken. I am now searching my 34 volumes for any errors in transcribing.

* Can be handled by my laptop.

@Paul Wilson – The images being offline was a hosting problem. Fixed now, sorry about that.

I’d like to point out that the proof of Figure 1 might be incomplete. After we know that

X can not be alive in generation 2, you say “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”. That’s right, of course. But v(the diagonal speed)=s/t, for s<1,t=2, so we can only say v<1/2. But what if v=1/3? In other words, if the spaceship is on ABCDE, the X cell may be alive in generation 3, and you haven't retorted that yet.

@KyleKirsten — we don’t need to consider that case separately. The logic goes as follows: If at generation 0 it is on (or behind) the ABCDE line, then at generation 2, it is on (or behind) the UV line. But then you can just repeat that argument to see that at generation 2+2 = 4 it is on (or behind) the X line.

@Nathaniel

But generation 2+1=3 may also be on the X line. So the spaceship may have traveled to the X line on generation 3.

However, it’s easy to see the contradiction of the assumption above: generation 3 has the same state in generation 0, so generation 4 has the same state in generation 1. As generation 4 is on(or behind) X line, generation 1 is on(or behind) ABCD line. For generation 1, repeat the argument to see that generation 3 is on (or behind)UV, which gives a contradiction. (Anyway, problems solved

@KyleKirsten – “But generation 2+1=3 may also be on the X line.” Yes, that’s true, but that’s not a problem. The point is that it can’t travel faster than 1 diagonal lane per 2 generations. That’s all you need. That implies the c/4 speed limit right away.

Even if X is alive in generation 3, we already showed that it can’t be *past* X in generation 4. That’s all that matters.