The Game of Life

I've mentioned the mathematician John Conway in three posts to this blog. The first was the Look and Say Sequence on February 10th 2017, the second was the RATS Sequence on September 26th 2020 and the third was the Free Fibonacci Sequences on July 18th 2021.

John Conway: 1937 - 2020
MacTutor Biography

I've known about his Game of Life for quite some time now but had avoided delving into it. However, yesterday I downloaded an iOS app that allows one to play around with it and this kindled an interest to find out more. Here is some information about the game together with its rules taken from Wikipedia:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with fewer than two live neighbours dies, as if by underpopulation.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by overpopulation.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

Figures 1, 2 and 3 show examples of commonly occurring patterns that occur during the game:

Figure 1: Loaf
Example of a still life

Figure 2: Blinker
Example of an Oscillator

Figure 3: Glider
Example of a Spaceship

The Pulsar is the most common period-3 oscillator as shown in Figure 4.

Figure 4: Pulsar
The most common
Period-3 oscillator

The Wikipedia comments go on to say:

The pulsar is the most common period-3 oscillator. The great majority of naturally occurring oscillators have a period of 2, like the blinker and the toad, but oscillators of all periods are known to exist, and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions. Patterns which evolve for long periods before stabilizing are called Methuselahs, the first-discovered of which was the R-pentomino. Diehard is a pattern that eventually disappears, rather than stabilizing, after 130 generations, which is conjectured to be maximal for starting patterns with seven or fewer cells. Acorn takes 5,206 generations to generate 633 cells, including 13 escaped gliders.

Figure 5: R-Pentomino
The first discovered Methuselah

Of course, I've encountered numerous references to the Game of Life in the OEIS over the years but have uniformly ignored them. OEIS A019473 is one example.

A019473

Number of stable \(n\)-celled patterns ("still lifes") in Conway's Game of Life, up to rotation and reflection.

The initial members of the sequence are: 0, 0, 0, 2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, 3286, 7773, 19044, 45759, 112243 (beginning with \(n\)=1).

Figure 1 shows the Loaf, one of the four 7-celled stable patterns. OEIS A089520 is another such sequence:

A089520

In Conway's Game of Life, the number of steps it takes for an \(n \times n\) square, in which all the cells are in the "on" state, to die out or start to cycle, or -1 if there is no cycle.

The initial members are:

1, 0, 5, 4, 11, 5, 5, 6, 16, 17, 32, 9, 18, 9, 22, 11, 33, 17, 20, 12, 26, 13, 48, 15, 46, 26, 295, 45, 154, 38, 62, 309, 38, 87, 78, 53, 96, 150, 641, 69, 82, 265, 216, 70, 70, 70, 120, 401, 107, 78, 70, 351, 318, 109, 297, 95, 122, -1, -1, 85, 232, 294, 127 (beginning with \(n\)=1).

The 1 x 1 square disappears in one step but the 2 x 2 square (called the Block) is stable and an example of a still life. The 3 x 3 square takes five steps to turn into four blinkers (one of which is shown in Figure 2). The 4 x 4 square takes four steps to disappear and so on. The OEIS comments for this sequence state that:

The -1 terms for \(n\) = 58, 59, 80, 92, 95, 96, 98, 99, 100 correspond to starting \(n \times n \) squares that produce 8 gliders (16 for \(n\) = 99) that go off to infinity, hence never reaching a cycle.

Here is a link to an interesting article in Quanta Magazine about the latest news regarding the Game of Life. Here is an excerpt:

Throughout the 1970s, mathematicians and hobbyists filled in the other short periods and found a smattering of longer ones. Eventually, mathematicians discovered a systematic way to build long-period oscillators. But oscillators with periods between 15 and 43 proved tough to find. “People have been trying to figure out the middle for years,” said Maia Karpovich, a graduate student at the University of Maryland. Filling in the gaps forced researchers to dream up a slew of new techniques that pushed the boundaries of what was thought possible with cellular automata, as mathematicians call evolving grids like Life.

Now Karpovich and six co-authors have announced in a December preprint that they have found the last two missing periods: 19 and 41. With those gaps filled, Life is now known to be “omniperiodic” — name a positive integer, and there exists a pattern that repeats itself after that many steps.