What is the maximum "alive density" of cells in Conway's Game of Life when played on a torus?

732 Views Asked by At

I've read that Conway's Game of Life (CGOL) can have unbounded growth from a finite initial number of alive cells (e.g. a glider gun). However, if CGOL is played on a torus, space (the number of cells) becomes finite, and glider guns are guaranteed to eventually destructively interfere with themselves.

Because of this, I wondered about the maximum proportion of alive cells on a torus. To be specific,

What is the maximum stable density of alive cells in CGOL on a torus, where density means proportion of alive cells out of all cells, and stable means this density occurs infinitely many times (as opposed to the recurrence of position: a glider might have nonperiodic position, but stable density)

2

There are 2 best solutions below

6
On BEST ANSWER

In the specific case of a pattern that is fixed under the rules of the Game of Life, the maximum density is 1/2, as shown by Noam Elkies in The still-Life density problem and its generalizations.

Elkies also presents (on page 22) a simple example of a period 6 oscillator with maximum density 3/4. Here are all its phases: \begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&1&0&0&0&0&0&0\\ \hline 1&1&0&0&0&0&0&0\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&1&0&0&0&0&1\\ \hline 0&0&1&0&0&0&0&1\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&1&1&1&0&0&1&1\\ \hline 1&1&1&1&0&0&1&1\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&0&0&1&1&0&0\\ \hline 0&0&0&0&1&1&0&0\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&0&1&0&0&1&0\\ \hline 0&0&0&1&0&0&1&0\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&1&1&1&1&1&1\\ \hline 0&0&1&1&1&1&1&1\\ \hline \end{array}

3
On

I think it'll be hard to beat

\begin{array}{|c|c|} \hline 1&1\\ \hline 0&0\\ \hline \end{array}