Conway's Game of Life

Conway's Game of Life is a zero-player cellular automaton devised by mathematician John Horton Conway in 1970. Despite having no input after the initial state, astonishingly complex patterns emerge from just four simple rules applied to a grid of cells. It is one of the most famous examples of emergent behavior -- how complex systems arise from simple rules -- and has deep connections to computability theory, as it has been proven to be Turing complete.

How It Works

1. Grid setup: The universe is an infinite two-dimensional grid of cells, each in one of two states: alive or dead. In practice, a finite grid with wrapping or fixed boundaries is used.
2. Neighbor count: Each cell has eight neighbors (horizontal, vertical, and diagonal). At each step, count how many of a cell's neighbors are alive.
3. Apply rules: All cells are updated simultaneously based on the current state (synchronous updates). The next generation is computed entirely from the current one.
4. Repeat: The process continues indefinitely, producing successive generations.

Rules

These four rules are applied to every cell simultaneously. The key insight is that all births and deaths happen at the same instant -- no cell's new state affects another cell's computation in the same generation.

Complexity

Where N × M is the grid size. Each cell requires checking its eight neighbors, making each generation linear in the number of cells. Advanced implementations like HashLife can achieve exponential speedups for patterns with repeated structure by memoizing sub-patterns.

Applications

The Game of Life has applications across many fields. In theoretical computer science, it demonstrates that simple rules can produce universal computation -- logic gates, memory, and even entire computers have been built within it. In biology, it models population dynamics, bacterial colony growth, and pattern formation in organisms. In physics, it serves as a simplified model for studying phase transitions and self-organization. It remains a cornerstone of recreational mathematics and a gateway to understanding cellular automata, complexity theory, and artificial life.