Local and Global Properties in Conway’s Game of Life
Conway’s Game of Life is a cellular automata “game” played on an infinite grid of cells. Every cell on the grid is either alive or dead, and over time, the status of each cell changes based on a set of rules. The rules are defined as follows:
- Any live cell with fewer than two live neighbours dies, as if caused by under-population.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overcrowding.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
An Example of a Grid
Interestingly enough, the Game of Life can be modeled by a graph with a few adjustments. For each cell in the graph, we can create a node, and between every neighboring cells, we can create an undirected edge. Then, there are 3 possible edges:
- Alive cell and alive cell (+,+)
- Dead cell and alive cell (-,+)
- Dead cell and dead cell (-,+)
Example of Local Graph
When we considered the Structural Balance Property, we considered groups of 3 nodes. Similarly, we can consider groups of 9 nodes: a center node and all of its neighbors. Using this construction, the rules of Conway’s Game of Life can be encoded into rules similar to those of the Structural Balance Theorem, to create a notion of balance. We can define a node to be balanced if:
- It has 2 or 3 (+,+) edges
- It has 1, 2, 3, 4, 5, 7, 8 (-,-) edges
A node is unbalanced if it is not balanced. As you may have guessed, a balanced cell does not change its state in the next generation. An unbalanced cell changes its state in the next generation, that is, a dead cell becomes alive and an alive cell becomes dead.
These are purely local properties, as they only consider a local set of 9 nodes at a time. However we’ve seen that purely local properties such as the Structural Balance Theorem, which applies to only 3 nodes at a time, can imply strong global properties. In the case of Conway’s Game of life, a global property would be the proportion of cells that are still lifes. Still lifes are alive cells that do not change state in one generation to next.
Some Fancy Still Life Examples
While the proof for the Structural Balance Theorem was quite simple, the proof for the maximum density of still lifes in Conway’s Game of life is much more complicated. Nonetheless, Noam D. Elkies has proven that at any point, a maximum of one half of all of the cells are still lifes. This was done using the Voronoi Cell Method to calculate bounds on local densities. Perhaps it is also interesting to note that the ratio was at most one half, similar to how the Structural Balance Theorem separates the nodes into two groups.
When modeled as a graph, Conway’s Game of Life shows interesting parallels to networks we’ve studied in class. Similar to real life networks, the grid evolves over time based on a set of rules that imply unbalance. We’ve examined alliances that have evolved over time to “resolve” unbalancedness, and similarly, Conway’s Game of Life evolves to resolve unbalancedness (although in this case, a final resting state may never be reached). Furthermore, we notice that local properties can be extrapolated through proof to suggest powerful global properties that apply to the entire sample space.
Sources:
http://people.eng.unimelb.edu.au/pstuckey/papers/still-life.pdf
http://arxiv.org/pdf/math/9905194v1.pdf
http://www.math.cornell.edu/lipa/mec/lesson6.html