Game of Life
- This article is not detailed enough and needs to be expanded. Please help us by adding some more information.
| Designed by | Conway et al. |
|---|---|
| Appeared in | 1970 |
| Computational class | Turing-complete, universal |
| Reference implementation | Unpublished code by Steve Bourne and Michael J. T. Guy |
| File extension(s) | .cells, .lif, .life, .rle |
Conway's Game of Life (often simply Game of Life or Life) is a cellular automaton invented by John Horton Conway sometime between 1968 and 1970, documented by wikipedia:Martin Gardner in Scientific American and by Conway, wikipedia:Elwyn Berlekamp, and wikipedia:Richard K. Guy in Winning Ways for Your Mathematical Plays. It is notable for its complex and diverse emergent behavior compared to other cellular automata, despite the simplicity of its definition, and the relative ease in which powerful artificial constructions (such as Turing machines) can be constructed within it.
The idea of the Game of Life was to show that self-sustaining "life" (or infinite growth) could arise from a set of simple rules. This was quickly shown to be true with the discovery of glider gun by wikipedia:Bill Gosper.
The state (pattern) of game of life is a square grid filling the whole plane, in which each cell of the grid is either dead or alive. Each cell is considered to have eight neighbors, which are the cells a chess king's move away (this is called Moore neighborhood). The state is updated at each clock cycle (generation), in which the state of each cell is replaced simultaneously. A cell will be alive in the next clock cycle iff it is alive and has exactly 2 or 3 alive neighbors or dead and has exactly 3 neighbors.
It is common to consider only finite states, which are states in which all but a finite number of cells are dead. (It is easy to see that Game of Life started in a finite state will always be in a finite state.) Game of Life was proven Turing-complete starting from finite configurations by John H. Conway in 1982.
Game of Life is universal (the cellular automaton analogue of Turing-completeness), and was proven to have a self-replicating pattern in 2010 with the discovery of the Gemini pattern. The fact that this pattern eluded construction for so long is surprising (although that one was incredibly likely to exist had been known for decades), as many other cellular automata of similar complexity have very trivial self-replicators; Gemini, on the other hand, is incredibly complex (with a bounding box of 4217807 by 4220191 cells).
Game of Life still has a large active research community (as of 2018), and LifeWiki offers a glimpse into some of the most attractive results. The size of the bounding box and the number of cells alive in the starting state are usually considered useful measures of the size of a program in Game of Life, although technically the latter is flawed because a Life program can be encoded in the positions of living cells; a universal construction for any glider-constructible object is known starting from 15 gliders using the "Reverse Caber Tosser", with the object to construct encoded in the position of the gliders (and there are known Turing-complete glider-constructible programs). Research is active in both finding small programs with interesting behavior, and constructing gigantic machines (with bounding boxes whose sides are millions) as the first example to prove certain behaviors possible.
See also
External resources
- Gardner 1970, the earliest published explanation of the rules of Life
- Conway's Game of Life at Wikipedia
- LifeWiki