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:
- A regular grid of cells, each in one of a finite number of states
- Grid could be in any number of finite dimensions
- Each cell has a set of neighbours called its neighbourhood, defined relative to the cell
- 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:
- Any live cell with less than two live neighbours in the current turn dies in the next turn (underpopulation).
- Any live cell with two or three live neighbours in the current turn lives in the next turn.
- Any live cell with more than three live neighbours in the current turn dies in the next turn (overpopulation).
- 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.
-
Still life - these do not change at all from turn to turn. Examples are…
-
Oscillators - these evolve from an initial state and come back to the original state after a certain number of turns. Examples are…
-
Period 2
-
Period 3
-
Period 15
-
Pentadecathlon 4
-
-
Period 30
-
Eureka 3
-
-
Period 60
-
Toadsucker - This consists of a Hassler and a toad. A Hassler is basically an oscillator that alternatively changes a properly placed object, and then changes it back to the original state. The object that the Hassler interacts with is in this case a toad, which we met in our examples for a period 2 oscillator. 3
-
-
-
Spaceships - these move across the square grid as they evolve. They are classified on the basis of their speed. Given the rules, it can be shown that the maximum speed achievable by a moving object in this world is one tile per second. In analogy with the real world, this could be termed as c. It is also known that Life has all possible spaceships that can move in any rational direction at an arbitrarily slow pace, but until May 2010, only spaceships that move in orthogonal or diagonal directions were known. The maximum speed for a spaceship is c/2 orthogonally, c/4 diagonally and so on for other slope values. For now, the following are examples of spaceships based on velocity:
-
Glider guns - It is a pattern consisting of a main part that repeats periodically, and periodically emits a spaceship. The period of the gun is a multiple of the period of spaceship production. There is an interesting story about the glider gun. Its existence implies that initial patterns with a finite number of cells can eventually lead to configurations with an infinite number of cells. John Conway conjectured that such a thing was impossible but Bill Gosper discovered the Gosper Glider Gun in 1970, winning $50 from Conway.5
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
-
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. ↩
-
Open Source image from Wikimedia Commons. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 ↩8 ↩9
-
Image from Eric Weisstein’s Treasure Trove of the Life Cellular Automaton ↩ ↩2 ↩3 ↩4 ↩5 ↩6
-
Image under Creative Commons License from Wikimedia Commons. Link ↩
-
Image under GNU Free Documentation License from Wikimedia Commons. Link ↩
Leave a comment