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!

The Q-toothpick cellular automaton (defined earlier this month by Omar E. Pol) is described by the following simple rules:

1. On an infinite square grid, draw a quarter circle from one corner of a square to the opposite corner of that square:
2. Call an endpoint of a quarter circle (or a “Q-toothpick”) exposed if it does not touch the endpoint of any other quarter circle.
3. From each exposed endpoint, draw two more quarter circles, each of the same size as the first quarter circle you drew. Furthermore, the two quarter circles that you draw are the ones that can be drawn “smoothly” (without creating a 90° or 180° corner). Thus the next two generations of the automaton are (already-placed quarter circles are green, newly-added quarter circles are red):
   

The name “Q-toothpick” comes from its analogy to the more well-studied toothpick automaton (see Sloane’s A139250 and this paper), in which toothpicks (rather than quarter circles) are repeatedly placed on a grid where exposed ends of other toothpicks lie. In this post, we will examine how this automaton evolves over time, and in particular we will investigate the types of shapes that it produces.

Counting Q-Toothpicks

While the Q-toothpick automaton appears quite random and unpredictable for the first few generations, evolving past generation 6 or so reveals several patterns. The following image depicts the evolution of the automaton for its first 19 generations.

The first 19 generations of the Q-toothpick cellular automaton (red segments are pieces that are newly added in the current generation)

Perhaps the most notable pattern is that the grid is more or less filled up in an expanding square starting from the initial Q-toothpick. In fact, by inspecting generations 4, 6, 10, 18, we see that at generation 2ⁿ + 2 (n = 1, 2, 3, …) the automaton has roughly filled in a square of side length 2ⁿ⁺¹ + 1, and then evolution continues from there on out of the corners of that square. Also, the number of cells added (A187211) at these generations can now easily be computed:

A187211(2ⁿ + 2) = 16 + 8(2^n-1 – 1) for n ≥ 3.

Furthermore, the growth in the following generations repeats itself. In particular, we have:

A187211(2ⁿ + 3) = 22 for n ≥ 1,
A187211(2ⁿ + 4) = 40 for n ≥ 2,
A187211(2ⁿ + 5) = 54 for n ≥ 2.

Similarly, for n ≥ 3, the four values of A187211(2ⁿ + 6) through A187211(2ⁿ + 9) are similarly constant (their values are 56, 70, 120, and 134). In general, for n ≥ k the 2^k-1 values of A187211(2ⁿ + 2^k-1 + 2) through A187211(2ⁿ + 2^k + 1) are constant in n, though I am not aware of a general formula for what these constants are. If we ignore the first four generations and arrange the number of Q-toothpicks added in each generation in rows of length 2ⁿ, we obtain a table that begins as follows:

22, 20
22, 40, 54, 40
22, 40, 54, 56, 70, 120, 134, 72
22, 40, 54, 56, 70, 120, 134, 88, 70, 120, 150, 168, 246, 360, 326, 136

C scripts are provided at the end of this post for computing the values of A187210 and A187211 (and hence the values in the above table).

Shapes Traced Out by Q-Toothpicks

By far the most common of these shapes are circles, diamonds and hearts. The fourth shape appears only on the diagonal and it’s not difficult to see that it forever will make up the entirety of the diagonal (with the exception of the circle in the center). The fifth and sixth objects are the first two members of an infinite family of objects that appear as the automaton evolves. The fifth object first appears in generation 9, and sixth object (which is basically two copies of the fifth object) first appears in generation 17. The following object, which is basically made up of two copies of the sixth object (i.e., four copies of the fifth object) first appears in generation 33:

In general, a new object of this type (made of 2ⁿ copies of the fifth object above) first appears in generation 2ⁿ⁺³ + 1. In fact, these objects are the only ones that are traced out by this automaton. [Edit: this final claim is not true! See ebcube’s great post that shows a double-heart shape in generation 31.]

Update [March 28, 2011]: I have added a script that counts the number of circles, diamonds, and hearts in the nth generation of the Q-toothpick automaton, and another script that computes Sloane’s A187212.

Download:

• A187210.c – computes the total number of Q-toothpicks present in the nth generation
• A187211.c – computes the number of Q-toothpicks added in the nth generation
• A187212.c – computes the number of Q-toothpicks if we restrict them to the positive quadrant
• count_shapes.c – computes the number of circles, diamonds, and hearts in the nth generation

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]

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.

UPDATE [April 17, 2015]: The Online Life-Like CA Soup Search has been offline for some time now (due to being written in ASP, and me now only running websites on Linux hosts, which means I would have to re-code it entirely in PHP). However, I am happy to announce that Adam P. Goucher has recently released a new distributed soup search script called Catagolue. Not only is this script much faster than mine, but it also has many other improvements, such as being (much) better at distinguishing different objects that are near each other, and being more cryptographically secure.

See this forum thread for the announcement as well as some discussion of discoveries made by the search so far.

Today I’m “officially” announcing the Online Life-Like CA Soup Search, though some of the folks over at the ConwayLife.com forums have been helping me test it out for a couple of weeks now.

As I mentioned in this post, one way to learn about the general behaviour of Conway’s Game of Life (or any other Life-like cellular automaton) is to generate random patterns and see what stable patterns they typically evolve into (if any). If you’ve played around with Conway’s Game of Life, then you more than likely are very familiar with blocks, blinkers, beehives, loaves, and maybe even pulsars, simply as a result of drawing random gibberish on the grid and letting it evolve. This is exactly the idea behind the Online Life-Like CA Soup Search, just on a larger scale — what if we had lots of people’s computers drawing random gibberish on Life grids, letting them evolve, and storing the resulting patterns in a communal database?

This method of collecting patterns in Life is known as a census, and to my knowledge it has been carried out on a relatively large scale twice in the past; once by Achim Flammenkamp (results here), and once by Andrej Okrasinski (results linked in the first paragraph here). As we would expect, the block is by far the most common still life, and the blinker is by far the most common oscillator. If we scroll down a bit, we see that the pulsar is the fourth most common oscillator (which is reasonably surprising, given its size). Scrolling much past that, we get into the interesting stuff — objects that no reasonable person has ever seen from drawing random stuff and seeing what it evolves into, simply because they occur so infrequently.

So why bother doing another census if two rather large-scale censuses (censi?) have already been carried out? My reasons are threefold:

1. There has never (to my knowledge) been a census of any other Life-like cellular automata conducted. The Online Life-Like CA Soup Search is completely general in that it can conduct a census of any Life-like rule (assuming that rule is stable, of course). Censuses have already been started for five other rules, including 2×2, Day & Night, HighLife, and Move. Because some of these other rules have been studied relatively little, this is an easy way of discovering new yet fundamental patterns in them. For example, it didn’t take long for the soup search script to uncover a c/8 line puffer in the 2×2 (B36/S125) rule; the very first known pattern that exhibits infinite growth in 2×2!
   

   Line puffer in 2×2

2. Previous soup searches were limited in that they only looked for very specific types of objects — usually still lifes and oscillators (though Achim Flammenkamp did a search for spaceships and puffers that can be viewed here). The Online Life-Like CA Soup Search searches for still lifes, oscillators, spaceships and puffers all at once, and even gets pseudo objects (such as the bi-block) as well.
3. Multiple users can run the script and contribute to the results simultaneously. Rather than just having one person run a script that they themself wrote, the Online Life-Like CA Soup Search works by having users download a script and that script uploads results to the central database. This obviously provides a huge speed-up, and allows the census to continuously improve and expand.

So what are you waiting for? Visit the Online Life-Like CA Soup Search, download the script, and put your computer’s CPU cycles to good use!

Census results in Conway’s Game of Life

One interesting Life-like cellular automaton, known as “2×2“, is particularly abundant with frequently-occurring oscillators and has thus attracted some attention from Life enthusiasts over the years. The 2×2 automaton takes place on a grid much like Conway’s Game of Life, but cells are born if they have exactly 3 or 6 neighbours, and they survive if they have exactly 1, 2, or 5 neighbours (this behaviour is summarized by the rulestring “B36/S125”).

Some small period 2 oscillators in B36/S125

Take a look at the second oscillator from the left in the top row of the above image — it is a 2 × 4 rectangle that oscillates back and forth. The oscillators that I will be looking at in this post are rectangles like this; rectangles of sizes 2m × 2n such that m + n is odd (the reason for these restrictions on the sizes of the rectangles is simply that they aren’t oscillators otherwise (not quite, see the correction in the comments)). The next two smallest of these rectangular oscillators are shown here:

Rectangular oscillators in B36/S125

As you can see, the oscillators behave a bit more unpredictably as their size increases. The question that I will answer now is “What is the period of a 2m × 2n rectangular oscillator in the 2×2 rule in terms of m and n?”

I will present the final answer right now, since it isn’t particularly simple: the period is 2^k+1 – 2, where k is the least natural number such that 2^k = ± 1 mod (m + n). While this answer isn’t exactly pretty, the k values have at least already been computed up to m + n = 2001 (see Sloane’s A003558), and there is at least some theory developed about them (see Suborder Function at Mathworld).

It is perhaps worth noting that B36/S125 isn’t the only rule in which these oscillators work; it’s simply the most well-known. These rectangular oscillators behave the same in any rule from B3/S5 to B3678/S012567.

Deriving the Answer

Disclaimer: The following contains much handwaving. It can be made rigorous, but I don’t particularly want to; the argument is long enough as it is, and this is recreational mathematics, after all.

Before proceeding, let’s make a simplification by noticing that a 2m × 2n rectangle is simply another phase of a 2 × 2(m + n – 1) rectangular oscillator. It is thus enough to consider 2 × 4n rectangular oscillators, where n is an integer.

The thing to notice about these oscillators is that, as described by Dean Hickerson in this thread, each phase of these block oscillators can be described as an XOR of rectangles. For example, consider the following phase of one of the above oscillators:

2 × 12 XOR 6 × 8

The above phase can be considered the XOR of a 2 × 12 rectangle and a 6 × 8 rectangle. Different phases may require a different number of rectangles to be XORed, but every phase can always be represented in this way. More important, however, is the fact that the evolution of the oscillators occurs in a very predictable way when modeled like this. Consider the following grid. (Aside: you will likely recognize that it resembles very closely one half of the Sierpinski triangle. This is no coincidence; it turns out that these oscillators are, in a sense, emulating the “Rule 90” 1D cellular automaton.)

XOR grid

The way to read the above grid is that that row represents the current generation and the column represents the size of the rectangle that is being XORed (the first column represents a 2 × 4n rectangle, the second column represents a 4 × (4n – 2) rectangle, the third column represents a 6 × (4n – 4) rectangle, and so on). Thus, you “start” in the top-left cell, and that represents the 2 × 4n rectangle that you start with (in generation 0). To go to generation 1, go to the next row, where we see that the only filled in cell is in the second column, which is the 4 × (4n – 2) column. Thus, the first generation will just be a filled-in 4 × (4n – 2) rectangle. To see what generation 2 will look like, go to the next row, where we see that two cells are filled in, corresponding to 2 × 4n and 6 × (4n – 4) rectangles. Thus, XOR together two rectangles of those sizes (in the sense described earlier) to get what generation 2 must look like.

The key to determining the oscillators’ periods comes from realizing that if we continue to label the columns in the way I described, eventually we hit zero-length rectangles, which doesn’t make a whole lot of sense. Thus, we simply do not XOR any of those rectangles that are of length zero. But what about rectangles of negative length? Instead of counting down into negative numbers, start counting back up. This is probably easiest to illustrate with an example, so I’ll use the n = 3 case.

Coloured XOR grid (n = 3)

Red columns represent 2 × 12, orange represent 4 × 10, yellow represent 6 × 8, green represent 8 × 6, blue represent 10 × 4, purple represent 12 × 2, and grey represent zero-width rectangles that can be ignored. Thus, we see that (for example), in generation 9 (row 10), there is a puple and a green and so the oscillator will look like a 12 × 2 rectangle XORed with an 8 × 6 rectangle.

The period can be determined by grids of this type by going down the rows, looking for the first row (after row 1) that has an odd number of red cells filled in (so that after XORing, a 2 × 4n rectangle will be present) and an even number of each other colour besides grey (so that after XORing, no rectangles of other sizes will be present). It can be shown that the first time this occurs must be at the bottom of one the triangles that reaches all the way to the left (so in row 3, 7, 15, 31, and so on). This corresponds to the oscillators always having period that is equal to 2^k – 2, where k is some integer. To determine what that integer is, notice that if one of these oscillators starts off as a 2 × 4n rectangle, then it will appear rotated 90 degrees as a 4n × 2 rectangle halfway through its period. Thus, we need the least k such that row 2^k-1 contains a single purple cell (i.e., 2^k-1 = ± 1 mod (2n + 1)).

By transforming back to 2m × 2n rectangles and shifting around k a little bit, we see that the period is 2^k+1 – 2, where k is the least integer such that 2^k = ± 1 mod (m + n).

Thus, using Sloane’s A003558 as our guide, we see that the period of a 2m × 2n rectangle for m + n = 3, 5, 7, 9, … is 2, 6, 14, 14, 62, 126, 30, 30, 1022, …

Update [May 28, 2009]: This sequence is now listed in the OEIS as Sloane’s A160657.

Update [January 14, 2019]: A few people (at least Dave Greene as well as wwei and Blinkerspawn in the comments below) noticed that this argument is incorrect — I have just demonstrated an upper bound on the period of these oscillators, and the true period may be a factor of that upper bound (this first happens for the 2-by-72 oscillator, which has period equal to 1/3 of the value claimed in this post). Sequence A160657 has now been updated with the correct values.