Game of Life
| 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, .mc |
Conway's Game of Life (often simply Game of Life or Life) is a cellular automaton first described 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.
History
Conway originally discovered the precise rules of Life while searching for universal cellular automata over low-dimensional grids. At the time, Conway was following the research programme established by wikipedia:Stanislaw Ulam and wikipedia:John von Neumann in the late 1940s concerning self-replicating machines; a universal constructor would allow arbitrary constructions including constructing copies of itself, and Von Neumann had already shown the theoretical feasibility of the approach by proposing the wikipedia:Von Neumann universal constructor.
In an informal sense, the idea of studying the Game of Life is to show that self-sustaining patterns, indefinite growth, and other substrate-agnostic definitions of wikipedia:life could arise from relatively easy-to-describe systems. In support of that line of thinking, there has been a stream of theorems showing that Life is — depending on definitions — alive:
Construction (glider). There is a life:spaceship: a pattern which translates across the grid. Moreover, its rate of travel is one cell per four generations, or c/4, and its slope is 1. (R. K. Guy, 1969)
Conway would name Guy's spaceship the "glider" and it would become a symbol for Life.
Construction (Gosper glider gun). There is a life:gun of gliders. (Gosper, 1970)
Theorem. There exist spaceships of every rational slope. (Berlekamp, 1982, Winning Ways)
Theorem (Turing completeness). There is a universal computer with finitely many alive cells. (Conway, 1982, Winning Ways)
Theorem. There is a universal constructor with finitely many alive cells. (Conway, 1982, Winning Ways)
Construction (Gemini). There is an life:oblique spaceship: a spaceship which neither moves in a straight line nor has a slope of 1. Moreover, its slope is 1/5. (A. J. Wade, 2010)
The details of Gemini's construction offer a potential way to fulfill Berlekamp's theorem, as discussed here.
Construction (reverse caber-tosser (RCT)). There is a universal constructor parameterized solely by the positions of a fixed number N of gliders. (Goucher & Greene, 2018)
Theorem. Reverse caber-tossers are universal for N=329 gliders. (Goldtiger997, 2018)
As of 2022, reverse caber-tossers have been shown universal for N=15 by a collaborative effort.
Description
The cells of Life are a standard two-dimensional grid of squares with Boolean values, traditionally called "dead" and "alive". Each cell has a wikipedia:Moore neighborhood of eight neighboring cells. The automaton acts on all cells at once based on the number of alive cells in its Moore neighborhood and its current state: if a cell's neighborhood has three alive cells, or if it is alive and its neighborhood has two alive cells, then the automaton marks it alive; otherwise it is marked dead. As with other cellular automata, the automata's action is known as the "generation".
It is common to consider only states in which a finite number of cells are alive, due to the following theorems which make them easy to simulate on computers:
Theorem. Every generation of a starting configuration with finitely many alive cells also has finitely many alive cells. (Folklore)
Theorem. Every finite starting configuration has a minimal bounding box containing all alive cells. (Folklore)
Complexity class
Conway proved that their 1982 constructions are universal computers. Several other models of computation have been directly embedded into Life since then:
Construction (Turing machine). There are simulations of Turing machines with 3-16 symbols and 3-8 states. (Rendell, 2000)
Construction (Minsky machine). There is a simulation of a Minsky machine. (Chapman, 2002)
As such, whether certain families of starting configurations ever reach generations with certain properties is Turing-complete. In particular, any Halting problem or property subject to wikipedia:Rice's theorem can be lifted to a property of configurations.
However, it is not the case that any finite pattern can be constructed. There are patterns which are not a generation of any starting configuration, called Gardens of Eden:
Theorem (Moore–Myhill Gardens of Eden). For cellular automata like Life, Gardens of Eden exist if and only if at least two finite patterns evolve to the same configuration. (Moore, 1963; Myhill, 1963)
Moore and Myhill were not publishing together; see [1] for a retrospective.
Theorem. Life has Gardens of Eden. (A. R. Smith, 1970)
Construction (Garden of Eden 1). There is a Garden of Eden with bounding box 33 × 9 cells. (Banks et al., 1971)
Following this, Conway asked whether there were any configurations which could only be generated from themselves (Conway, 1972, Lifeline Volume 6) or still-lifes which can only be present in a generation if they were present in the initial configuration (Conway, 1992). The answer to both is yes:
Construction (unique father problem). There is a pattern with bounding box 22 × 28 which must appear in any of its fathers. (Salo & Törmä, 2022)
Construction (Unsynthesizable oscillator 1). There is a pattern with bounding box 60 × 53 which must appear in any of its ancestors. (Cunningham, 2022)
So, while Life is capable of embedding universal computation, and many patterns are glider-constructible, there are patterns that cannot be constructed.
See also
External resources
- Gardner 1970, the earliest published explanation of the rules of Life
- Conway's Game of Life at Wikipedia
- LifeWiki
- Online interpreter