Sunday, 29 August 2010

John Conway's "Game of Life"

Recently I became very interested in cellular automaton. Have you, the reader ever come across John Conway's "Game of Life"?

It is a very simple game. The game is played on a two dimensional grid. Each cell in the grid can have two states: alive or dead. Every cell has eight neighbouring cells and the states of these cells affect the state of the central cell. Each step the fate of a cell is determined by the following rules.

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

To better visualize this situation look at the following pictures. The "game" is played on a grid that looks like the one below. At the beginning of the game the player chooses which cells to populate. this is called the initial state of the grid. At each step (sometimes referred to as a generation) the cells surrounding these populated cells and the cells themselves are changed according to the rules given above.

The above rules may appear to be strikingly simple. But the beauty of this game lies in the fact that extremely complicated patterns can be created using these simple rules. I'll start simple. Say you populate three horizontal rows and then allow the game to start. Here is the result.

If we start out with a shape that is a bit more complex.

These are however unimpressive when compared to the highly complex patterns that have been discovered. For example:

The game of life is not just a game. The complexity produced by these simple rules are a prime example of how complicated structures can evolve from simple physical systems. In particular the arguments put forward by creationists and supporters of intelligent design can be refuted. Since the human body contains billions of atoms it is possible for this group of atoms to develop complex behaviour such as locomotion, and thought and an intelligence.

The patterns that I have shown in this post are the simplest of all discovered. High power computers have been used to generate highly complex structures that exhibit extremely complex behaviour.


Kian Seng said...

Ashwin, do me a favour by integrating the below between the limits of r and -r

(r square- y square) / (r square-y square)

I know it may sound stupid, but doesn't it cancel each other out and give 1.

Thus, allowing us to integrate 1 into X and substituting r and -r into it which will give us 2r?

Ashwin Narayan said...

The two (r^ - y)s will cancel each other out to give one.

Is this the
--------(r^2 -y)
integral--------- dy?
--------(r^2 - y)

The answer to the indefinite integral depends on whether you put a dy or a dx at the end. For example:

--------(r^2 -y)
integral--------- dy = y +constant
--------(r^2 - y)

--------(r^2 -y)
integral--------- dx = x +constant
--------(r^2 - y)


------(r^2 -y)
intgrl---------d(blah)= blah + c
------(r^2 - y)

because the two (r^ - y)s will cancel each other out to give one.

Ashwin Narayan said...


------r-(r^2 -y)
integral--------- dx = r - (-r)
----(-r)(r^2 - y) = 2r


---(-r)--(r^2 -y)
integral--------- dx = -r -r
-----r--(r^2 - y) = -2r

Kian Seng said...

Ok help appreciated. It did cancel out, one of my friends tried doing it without cancelling it, as in trying to bring the denominator up and put a negative power on it, seems like it didnt work for him...