Conway's Game of Life

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively).

Stanisław Ulam, while working at the Los Alamos National Laboratory in the 1940s, studied the growth of crystals, using a simple lattice network as his model.

[7] At the same time, John von Neumann, Ulam's colleague at Los Alamos, was working on the problem of self-replicating systems.

The driving concept of the method was to consider a liquid as a group of discrete units and calculate the motion of each based on its neighbours' behaviours.

Like Ulam's lattice network, von Neumann's cellular automata are two-dimensional, with his self-replicator implemented algorithmically.

Von Neumann gave an existence proof that a particular pattern would make endless copies of itself within the given cellular universe by designing a 200,000 cell configuration that could do so.

[14] Motivated by questions in mathematical logic and in part by work on simulation games by Ulam, among others, John Conway began doing experiments in 1968 with a variety of different two-dimensional cellular automaton rules.

Moreover, some "simple initial patterns" should "grow and change for a considerable period of time" before settling into a static configuration or a repeating loop.

[3] A version of Life that incorporates random fluctuations has been used in physics to study phase transitions and nonequilibrium dynamics.

For many, the Game of Life was simply a programming challenge: a fun way to use otherwise wasted CPU cycles.

The simplest still lifes and oscillators were discovered while tracking the fates of various small starting configurations using graph paper, blackboards, and physical game boards, such as those used in Go.

The first two create a single block-laying switch engine: a configuration that leaves behind two-by-two still life blocks as it translates itself across the game's universe.

[38] Gosper also constructed the first pattern with an asymptotically optimal quadratic growth rate, called a breeder or lobster, which worked by leaving behind a trail of guns.

[16][2] In fact, several different programmable computer architectures[39][40] have been implemented in the Game of Life, including a pattern that simulates Tetris.

A universal constructor can be built which contains a Turing complete computer, and which can build many types of complex objects, including more copies of itself.

[2] On November 23, 2013, Dave Greene built the first replicator in the Game of Life that creates a complete copy of itself, including the instruction tape.

[2] From most random initial patterns of living cells on the grid, observers will find the population constantly changing as the generations tick by.

Because of the nearest-neighbour based rules, no information can travel through the grid at a greater rate than one cell per unit time, so this velocity is said to be the cellular automaton speed of light and denoted c. Early patterns with unknown futures, such as the R-pentomino, led computer programmers to write programs to track the evolution of patterns in the Game of Life.

The drawback is that counting live neighbours becomes a hash-table lookup or search operation, slowing down simulation speed.

[citation needed] For exploring large patterns at great time depths, sophisticated algorithms such as Hashlife may be useful.

For example, the automaton B1/S12 generates four very close approximations to the Sierpinski triangle when applied to a single live cell.

The Sierpinski triangle can also be observed in the Game of Life by examining the long-term growth of an infinitely long single-cell-thick line of live cells,[63] as well as in Highlife, Seeds (B2/S), and Stephen Wolfram's Rule 90.

When John Conway was first investigating how various starting configurations developed, he tracked them by hand using a go board with its black and white stones.

The first interactive Game of Life program was written in an early version of ALGOL 68C for the PDP-7 by M. J. T. Guy and S. R. Bourne.

The results were published in the October 1970 issue of Scientific American, along with the statement: "Without its help, some discoveries about the game would have been difficult to make.

"[1] A color version of the Game of Life was written by Ed Hall in 1976 for Cromemco microcomputers, and a display from that program filled the cover of the June 1976 issue of Byte.

[72] Two early implementations of the Game of Life on home computers were by Malcolm Banthorpe written in BBC BASIC.

[73] Susan Stepney, Professor of Computer Science at the University of York, followed this up in 1988 with Life on the Line, a program that generated one-dimensional cellular automata.

Most of these programs incorporate a graphical user interface for pattern editing and simulation, the capability for simulating multiple rules including the Game of Life, and a large library of interesting patterns in the Game of Life and other cellular automaton rules.

[77] The visual novel Anonymous;Code includes a basic implementation of the Game of Life in it, which is connected to the plot of the novel.