Conway's Game of life

Conway's Game of Life is a cellular automaton designed by a British mathematician, John Horton Conway, in 1970. There has been a lot of work done on it recently and there are several interesting results.

#technical #conway's-game-of-life

I read Richard Dawkins’ amazing book called ‘The Greatest Show on Earth’ some time back. Recently, while doing a course in Linguistics, I came across the term ‘generative system’ applied to language, which took me back to something called ‘Conway’s Game of Life’, which was also used by Dawkins in his book to illustrate a particular point; that (very) simple rules could lead to complex entities, so countering the creationist argument that the simple rules governing genetics and molecular biology couldn’t have led to the immense diversity seen in the natural world today. I am writing this article having just been introduced to the world of Conway’s Game of Life, and I hope this is a good introduction. I will probably dive into much more detail on this topic in the near future, so I am looking forward to that.

‘Conway’s Game of Life’ 1 is a cellular automaton designed by a British mathematician, John Horton Conway, in 1970. A cellular automaton consists of:

  1. A regular grid of cells, each in one of a finite number of states
  2. Grid could be in any number of finite dimensions
  3. Each cell has a set of neighbours called its neighbourhood, defined relative to the cell
  4. An initial state is assigned by assigning a state for each cell, and a new generation is created according to some fixed rule that determines the new state of each cell in terms of the current state of the cell and the cells in the neighbourhood.

The concept of a cellular automaton was first studied by John von Neumann and Stanislaw Ulam at Los Alamos in the 1940s. They were interested in finding a hypothetical machine that could build copies of itself and succeeded. However, the set of rules that they came up with was extremely complicated, and John Conway created the Game of Life in an attempt to simplify those rules.

So the Game of Life is an example of a cellular automaton. It takes place on an infinite two-dimensional grid of square cells. Each cell can be in two states, dead or alive. It evolves in turns. The state of any cell in the subsequent turn is decided by the state of the eight neighbouring cells in the current turn, according to certain rules. The rules are:

  1. Any live cell with less than two live neighbours in the current turn dies in the next turn (underpopulation).
  2. Any live cell with two or three live neighbours in the current turn lives in the next turn.
  3. Any live cell with more than three live neighbours in the current turn dies in the next turn (overpopulation).
  4. Any dead cell with exactly three live neighbours in the current turn becomes a live cell in the next turn (reproduction).

Thus, given an initial state (called seed) the grid evolves according to the rules and gets to subsequent states. The evolution is completely determined by the initial state.

These simple rules lead to an almost bewildering variety of things that can happen, only a small fraction of which I will talk here.

I guess this qualifies as an introduction to Conway’s Game of Life. If you want to see more such objects, check out Eric Weisstein’s Treasure Trove of the Life Cellular Automaton. There are many fascinating details about the Game that I have got a slight introduction to and which I shall read and describe in subsequent posts. I will probably read about the proofs of certain results that I have mentioned above, and also look into the proof that certain cellular automata are Turing complete, which is a result that I find extremely cool!

FUN FACT: If you search for Conway’s Game of Life on Google, you will find an Easter egg - the search results page has a simulation of the game in the corner. Do check that out! 6

  1. Almost all information in this article obtained from Wikipedia pages Cellular Automaton, Conway’s Game of Life and Eric Weisstein’s Treasure Trove of the Life Cellular Automaton↩︎

  2. Open Source image from Wikimedia Commons. ↩︎ ↩︎2 ↩︎3 ↩︎4 ↩︎5 ↩︎6 ↩︎7 ↩︎8 ↩︎9

  3. Image from Eric Weisstein’s Treasure Trove of the Life Cellular Automaton ↩︎ ↩︎2 ↩︎3 ↩︎4 ↩︎5 ↩︎6

  4. Image under Creative Commons License from Wikimedia Commons. Link ↩︎

  5. Image under GNU Free Documentation License from Wikimedia Commons. Link ↩︎

  6. Link here ↩︎