1

Game of Life (GOL) is well known. I will not try to describe it myself. More details here: https://conwaylife.com/wiki/Conway%27s_Game_of_Life

A Conway GOL Torus is a variation of GOL where the board wraps around (ie the number of cells are finite). See more here: https://conwaylife.com/wiki/Torus

For any initial configuration, every time we compute the new state of the board we say that one generation has passed.

This variation of the Game ends when the board gets into a state that we have seen before. This can happen if we reach a stable configuration (no more updates take place) or when we enter a cycle (an oscillator - https://conwaylife.com/wiki/Oscillator - is an example of this. Also be aware that the number of states for a cycles can be greater than 1 - sometimes a lot bigger than 1. One example could be a board that only contains one glider - https://conwaylife.com/wiki/Glider - because the board is a torus the glider will eventually wrap around and we will get the same state).

For torus board of size 32x32: What is the maximum number of generations we can get before the game ends? (i.e. board enters a stable state)

Mircea
  • 111
  • 1
    It's clearly somewhere between 232 and $2^{1024}$. Both of those bounds can likely be improved with fairly little effort, but since a 32×32 grid is way too big to search exhaustively (even assuming galaxy-sized supercomputers with atom-sized logic gates), I suspect that the best lower bound we can obtain (basically by finding an example pattern) will always remain many orders of magnitude below the best upper bound (likely of the approximate form $2^{knm}$ for an $n×m$ torus and some constant $0<k<1$). – Ilmari Karonen Nov 12 '22 at 17:33
  • 1
    Agree. It's clearly a max of 2^1024 (although I am not sure how you'd cycle through both an empty field and a full field in the same evolution). Not sure where the 232 came from but I'm guessing it's pretty trivial to show that it can be more than that. The configuration with the maximum number of generations that I've found so far is around 6300. So I we can claim that the max is somewhere between 2^12 and 2^1024 – Mircea Nov 20 '22 at 17:13
  • (Just a tangent, but if you click the "232" link and scroll down, there's an oscillator pattern with a period of 232 cycles and a bounding box of 28 x 28 cells for the first generation. Later generations extend a few cells beyond that box, but I'm still pretty sure that you can fit it on a 32 x 32 cell torus without any self-interactions.) – Ilmari Karonen Nov 22 '22 at 12:03

0 Answers0