Agnijo's Mathematical Treasure Chest banner
Home > Cellular automata > Life

Life


Life is a cellular automaton invented by John H. Conway. It involves a square grid and some black squares placed on it. There are rules about which cells are black in the next step.

1: If a cell is black and it has 2 or 3 black neighbours (a neighbour is any of 8 squares surrounding it) then it will remain black; otherwise it will turn white.

2: If a cell is white and it has 3 black neighbours then it will turn black; otherwise it will remain white.

These simple rules lead to very complex behaviour. For example, patterns such as the blinker can oscillate between two different states. Patterns such as the glider can move across the grid. This is not all. Even more complex patterns such as the Gosper gun can produce a steady stream of gliders. In fact, there is complexity in some of the simplest patterns. The r-pentomino only has 5 black cells but it explodes into a vast array of patterns.

This is not the most surprising thing about Life. That is that it can actually be used to build computers! For example, a pattern could be set up so that it computes prime numbers then shows an LCD-type display with streams of gliders. Such a computer would be an enormous pattern and would be extremely slow. However, it is impossible to predict in general the future of a pattern without checking it out. This is as it can simulate universal Turing machines and Turing proved that it is impossible to predict whether they will ever halt.


Related entries

   • Turing machines