The Game of Life on a finite field is sometimes explicitly studied; some implementations, such as Golly, support a choice of the standard infinite field, a field infinite only in one dimension, or a finite field, with a choice of topologies such as a cylinder, a torus, or a Möbius strip. The great majority of naturally occurring oscillators are period 2, like the blinker and the toad, but oscillators of many periods are known to exist,[19] and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions. For many years, this glider gun was the smallest one known. Sometimes very simple rules generate patterns of astonishing complexity. For many, the Game of Life was simply a programming challenge: a fun way to use otherwise wasted CPU cycles. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. [5][6] In fact, several different programmable computer architectures[28][29] have been implemented in the Game of Life, including a pattern that simulates Tetris. His construction was complicated because it tried to simulate his own engineering design. The prize was won in November by a team from the Massachusetts Institute of Technology, led by Bill Gosper; the "Gosper glider gun" produces its first glider on the 15th generation, and another glider every 30th generation from then on. The simplest strategy is to assume that every cell outside the array is dead. [63] 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.[64]. The Sierpinski triangle can also be observed in the Game of Life by examining the long-term growth of a long single-cell-thick line of live cells,[54] as well as in Highlife, Seeds (B2/S), and Wolfram's Rule 90.[55]. In the game's original appearance in "Mathematical Games", Conway offered a prize of fifty dollars to the first person who could prove or disprove the conjecture before the end of 1970. Alternatively, programmers may abandon the notion of representing the Game of Life field with a two-dimensional array, and use a different data structure, such as a vector of coordinate pairs representing live cells. Some variations on the Game of Life modify the geometry of the universe as well as the rule. It was a significant challenge and an open problem for years before experts on cellular automata managed to prove that, indeed, the Game of Life admitted of a configuration which was alive in the sense of satisfying Von Neumann's two general requirements. A cell that did not change at the last time step, and none of whose neighbours changed, is guaranteed not to change at the current time step as well, so a program that keeps track of which areas are active can save time by not updating inactive zones.[45]. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. All three of the patterns shown below grow indefinitely. Stanislaw Ulam invented cellular automata, which were intended to simulate von Neumann's theoretical electromagnetic constructions. The earliest interesting patterns in the Game of Life were discovered without the use of computers. [34][35] This pattern replicates in 34 million generations, and uses an instruction tape made of gliders oscillating between two stable configurations made of Chapman–Greene construction arms. This is easy to program but leads to inaccurate results when the active area crosses the boundary. Period refers to the number of ticks a pattern must iterate through before returning to its initial configuration. If a toroidal array is used, a third buffer is needed so that the original state of the first line in the array can be saved until the last line is computed. [31] A knightship is a spaceship that moves two squares left for every one square it moves down (like a knight in chess), as opposed to moving orthogonally or along a 45° diagonal. Hence B6/S16 means "a cell is born if there are six neighbours, and lives on if there are either one or six neighbours". The first two create a single block-laying switch engine: a configuration that leaves behind two-by-two still life blocks as its translates itself across the game's universe. Xlife is a cellular-automaton laboratory by Jon Bennett. One line buffer is used to calculate the successor state for a line, then the second line buffer is used to calculate the successor state for the next line. [36][37] In December 2015, diagonal versions of the Gemini were built. A variety of minor enhancements to this basic scheme are possible, and there are many ways to save unnecessary computation. Patterns relating to fractals and fractal systems may also be observed in certain Life-like variations. This differed from previous metacells, such as the OTCA metapixel by Brice Due, which only worked with already constructed copies near them. Techniques of dynamic storage allocation may also be used, creating ever-larger arrays to hold growing patterns. In late 1940, John von Neumann defined life as a creation (as a being or organism) which can reproduce itself and simulate a Turing machine. Many patterns in the Game of Life eventually become a combination of still lifes, oscillators, and spaceships; other patterns may be called chaotic.