Conway's Game of Life

This is a small analysis of the celebrated Conway’s Game of Life. History of this game is really fascinating. All started with John Von Neumann’s wish of creating self-evolving machines and this is just a simplified quantification of his attempt by Conway.

Lets assume that we are given an infinite two dimensional Cartesian grid. We design our initial species pattern at random on the life plane. A cell is designated to be with life or in short populated when it is occupied by a species. Given the initial pattern, we design the rules of evolution and start the process of evolution on the pattern. The rules determine the scope of a living cell as well, decide the birth of new species in an unoccupied cell.

The rules govern a particular cell about survival in the next generation. The rule is applied to all cells that are occupied as well as their neighbours. The neighbour of a cell is the 8 cells surrounding it in the cartesian grid. The rules are as follows:

1. If it has two are three neighbours, it survives in the next generation.
2. If it has less than two or more than three neighbours, it dies. If the neighbours are more, it dies due to crowd and if they are less, perhaps due to lonliness it never stays in next generation.

1. If it has exactly three neighbours, it is occupied by a new life in next generation.

The fascinating part of the game is that the final life form of the initial pattern given is almost unpredictable. Its because of one reason that there are lot of inter-dependencies that makes it so hard. Though there are few simple patterns that could be predicted of their life forms on the long run.

Actually, a rather difficult question to answer. This question has multiple answer. The final life form of a given initial pattern could be either one of the following possible forms:

1. Stable. After this pattern is attained, there is no change in the life form. It freezes.
2. Extinct. There is no life to further continue evolution. Certain patterns decay on the long run and never leaves a trace.
3. Oscillatory. This form oscillates between one pattern and the other. There can be several intermediate patterns in this transition.
4. Exploding. This kind of pattern is mostly completely chaotic and the pattern exhibit an explosive growth and continues evolution forever.
5. Translatory. In this case the pattern gets translated on the plane and it seems that it moves slowly in different directions but the life cells count doesnot increase as in case of exploding type.
6. Hybrid. This pattern is the combination of above observed patterns.

There are certain patterns whose dynamics are interesting to observe. Ofcourse the complex patterns of the game are not much interesting because of one reason, our minds would never be immediately ready to hold the complexity and would feel bored (aesthetically rather!)

The Stable type patterns are really interesting ones to analyse. In particular, patterns that has no more generations to proceed right from the start and stays stable gives a pseudo thought that those forms could be enumerable.

Here in this text we would analyze a few stabler patterns that has no more generations to involve in evolution and even though its age would be infinite, its change rate is 0. We would like to call these family of patterns as 0-Stabler patterns.

Involving ourself in the grid of patterns, we are pushed to enumerate the patterns that are 0-Stabler. We start with 1 living cell and ofcourse, from the game dynamics, we could very well immediately see that there could be no stabler patterns till we reach 4 living cells.

Here goes a few graphical patterns for 4, 5, 6 and 7 living cells:

4/5 Living Cells
	We have the first two patterns that form the 0-Stabler pattern with 4 living cells and the next one with 5 living cells. The later is quite similar to the 4 living cell in that the diagonal part has an extra cell with life. These are the two patterns available for 4 living cells.

6 Living Cells
	Interesting to observe. The 0-Stabler patterns with 6 living cells Not all patterns are shown here. Only two are available here. The first patterns resembles more or less to the 5 living cells pattern. Again a diagonal element added to it.

7 Living Cells
	This is where something strikes us. The second pattern of this 0-Stabler for 7 living cell does look more similar to some of the above patterns. Seems just an addon to the previous ones. But the first pattern looks entirely different, as actually it is.

22 Living Cells
	The pattern that i liked the most. 1)

The next obvious question that would arise is the following:

The enumeration of the number of 0-Stabler patterns is not an easier task. This should’ve been clear with the way the dynamics of this system behaves. But there is another suspicion that would arise again which could be settled easily. The question:

Surprisingly, the answer is YES. There does exists atleast one 0-Stabler pattern for any given N > 3. The next section explains that.

For any given N, there exists atleast one pattern that is 0-Stabler, provided N > 3.

We are not going for the proof of the above theorem since it would be drifting out from the actual point that we are heading to. We would like to see how we could enumerate a 0-Stable for any given N.

The actual clue lies in our suspicion of the patterns in case of 4, 5, 6 and 7 living cells. Going deep into the evaluation of 4, 5, and 6 living cells reveals us the secret. There exists a “Rhombus” pattern (actually a rhombus translated diagonally with copies of itself) which could be built infinitely. Here goes an illustration which explains to build a 2N as well as 2N+1 0-Stabler patterns.

This construction fits the last piece of puzzle about the relation between different pattern in the above 0-Stabler diagrams. Here we go,

1. The cells shaded dark are the cells that we assume initially to be empty.
2. Then, we got to prove the part above and the part below are 0-Stablers.
3. And finally, we got to prove, by populating the two shaded cells, we are not affecting the stability of the pattern as a whole.

This would be pretty easy since we dont affect many of those cells. The initial conditions could be proved by taking patterns 4, 5, 6 and 7. And everything falls in the line through the usage of Induction.

The above method is one of the proof by construction. It has become so easy since we’ve known of a pattern that is a 0-Stabler. But if the proof has to be more general, we’ll have to assume the pattern to be a graph and the proof would be much more complex than the proof for the above method.

Neverthless, the curiosity never stops even when the complexity increases. The curiosity is directly proportional to complexity i believe. Here are few questions that would normally arise when we dwell ourself in the analysis of this kind. These are the few that we would be interested to address a solution.

1. How many such 0-Stabler patterns exists for a given N > 3. Can we have an algorithm to enumerate all such distinct 0-Stabler patterns? (Rotations ignored).
2. How many predecessors could possibly exist for a given 0-Stabler of order N>3? Say, a given pattern might after S steps would decay to form a 0-Stabler. How many such pattern exists?
3. Do we have an algorithm to determine the type of the life form in the long run for a given pattern?
4. Is there any method that could determine if a given pattern would decay?
5. Given a 0-Stabler pattern, enumerate the weaker zones 2) of the pattern.
6. Given a pattern which is just a horizontal line of length K > 3, can we determine the complete dynamics of the pattern in long run?

Here are the places to visit for deeper information into the world of Cellular Dynamics.

1. Conway's Game of Life at IBIBLIO.
2. Wikipedia :: Game of Life.
3. Mathworld :: Cellular Automaton.
4. Achim's Game of Life.
5. The Nth Wonder in Game of Life, "The Caterpillar Spaceship" by Gabriel Nivasch, David Bell and Jason Summers.
6. Guns, the wonder in Game of Life.
7. Wikipedia :: Cellular Automaton.
8. David Eppstein's Cellular Automaton page.