Conway's Game of Life#Examples of patterns

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). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick.{{#tag:ref|The simultaneity means that when each cell counts the number of live neighbours around it, it uses its neighbours' old states before the update, not their new states after the update. If the cells are instead updated in reading order, so that each cell uses the old states of the cells to its right and below it but the new states of the cells to its left and above it, a different cellular automaton results, which is known as NaiveLife{{cite web|title=NaiveLife Emulated: A reading-order simulation of Life|url=https://conwaylife.com/forums/viewtopic.php?f=11&t=4523&p=128919|website=ConwayLife.com|access-date=29 November 2021|language=en|date=24 May 2020}}{{cite web|last1=Goucher|first1=Adam|title=Re: Thread For Your Accidental Discoveries|url=https://conwaylife.com/forums/viewtopic.php?f=2&t=279&p=13168#p13168|website=ConwayLife.com|access-date=29 November 2021|language=en|archive-date=29 November 2021|archive-url=https://web.archive.org/web/20211129154301/https://www.conwaylife.com/forums/viewtopic.php?f=2&t=279&p=13168#p13168|url-status=live}} because it is a common beginners' mistake among people attempting to program Conway's Game of Life.{{cite web|author1=Ian07|title=Re: Strange spaceship that is supposed to be impossible and infinite cell spread|url=https://conwaylife.com/forums/viewtopic.php?f=9&t=4288&p=88701#p88701|website=ConwayLife.com|access-date=29 November 2021|language=en|quote=I'm pretty sure this is because you've accidentally created an implementation of what's sometimes known as NaiveLife (as it's a common mistake made by many people coding CGoL for the first time):}}|group="nb"}} Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

{{Conway's Game of Life gadget

| autoplay = false

| width = 400

| height = 300

| zoom = 8

| grid = on

| cells = 0,0; 0,1; 0,-1; -1,0; 1,1

}}

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.{{cite book|author=Pickover, Clifford A.|title=The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics|url=https://archive.org/details/mathbookfrompyth00pick|url-access=limited|page=[https://archive.org/details/mathbookfrompyth00pick/page/n410 406]|year=2009|publisher=Sterling Publishing Company, Inc|isbn=978-1402757969}} At the same time, John von Neumann, Ulam's colleague at Los Alamos, was working on the problem of self-replicating systems.{{cite book|last=Schiff|first=Joel L.|title=Cellular Automata: A Discrete View of the World|year=2011|publisher=Wiley & Sons, Inc|isbn=9781118030639|url=https://books.google.com/books?id=uXJC2C2sRbIC}}{{rp|1}} Von Neumann's initial design was founded upon the notion of one robot building another robot. This design is known as the kinematic model.John von Neumann, "The general and logical theory of automata," in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.{{cite journal|last1 = Kemeny|first1 = John G.|year = 1955|title = Man viewed as a machine|journal = Sci. Am.|volume = 192|issue = 4|pages = 58–67|doi=10.1038/scientificamerican0455-58|bibcode = 1955SciAm.192d..58K}}; Sci. Am. 1955; 192:6 (errata). As he developed this design, von Neumann came to realize the great difficulty of building a self-replicating robot, and of the great cost in providing the robot with a "sea of parts" from which to build its replicant. Von Neumann wrote a paper entitled "The general and logical theory of automata" for the Hixon Symposium in 1948.{{Cite book |last=Von Neumann |first=John |title=Collected works. 4: Continuous geometry and other topics |date=1976 |publisher=Pergamon Press |isbn=978-0-08-009566-0 |edition=Repr |location=Oxford [u.a.] Frankfurt}} Ulam was the one who suggested using a discrete system for creating a reductionist model of self-replication.{{rp|3}}{{Cite book|title=Cellular Automata: A Discrete Universe|first=Andrew|last=Ilachinski|publisher=World Scientific|year=2001|isbn=978-981-238-183-5|url=https://books.google.com/books?id=3Hx2lx_pEF8C}}{{rp|xxix}} Ulam and von Neumann created a method for calculating liquid motion in the late 1950s. 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.{{cite book|first1=Iwo|last1=Bialynicki-Birula|first2=Iwona|last2=Bialynicka-Birula|title=Modeling Reality: How Computers Mirror Life|year=2004|publisher=Oxford University Press|isbn=978-0198531005}}{{rp|8}} Thus was born the first system of cellular automata. Like Ulam's lattice network, von Neumann's cellular automata are two-dimensional, with his self-replicator implemented algorithmically. The result was a universal copier and constructor working within a cellular automaton with a small neighbourhood (only those cells that touch are neighbours; for von Neumann's cellular automata, only orthogonal cells), and with 29 states per cell. 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. This design is known as the tessellation model, and is called a von Neumann universal constructor.{{cite book|last1=von Neumann|first1=John|last2=Burks|first2=Arthur W.|title=Theory of Self-Reproducing Automata|url=https://archive.org/details/theoryofselfrepr00vonn_0|year=1966|publisher=University of Illinois Press}}

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. Conway's initial goal was to define an interesting and unpredictable cellular automaton. According to Martin Gardner, Conway experimented with different rules, aiming for rules that would allow for patterns to "apparently" grow without limit, while keeping it difficult to prove that any given pattern would do so. 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. Conway later wrote that the basic motivation for Life was to create a "universal" cellular automaton.Conway, private communication to the 'Life list', 14 April 1999.{{better source needed|date=March 2022|reason=A "private communication" to a mailing list might not be impossible to verify, but it's pretty hard.}}

The game made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column, which was based on personal conversations with Conway. Theoretically, the Game of Life has the power of a universal Turing machine: anything that can be computed algorithmically can be computed within the Game of Life.It is a model and simulation that is interesting to watch and can show that simple things can become complicated problems.{{cite web|url=http://www.igblan.free-online.co.uk/igblan/ca/|title=Life Universal Computer|author=Paul Chapman|access-date=12 July 2009|date=11 November 2002|archive-date=6 September 2009|archive-url=https://web.archive.org/web/20090906014935/http://www.igblan.free-online.co.uk/igblan/ca/|url-status=dead}}{{Cite book|last1=Berlekamp|first1=E. R.|author1-link=Elwyn Berlekamp|last2=Conway|first2=John Horton|author2-link=John Horton Conway|last3=Guy|first3=R. K.|author3-link=Richard K. Guy|title=Winning Ways for your Mathematical Plays|publisher=A K Peters Ltd|edition=2nd|year=2001–2004|title-link=Winning Ways for your Mathematical Plays}} Gardner wrote, "Because of Life's analogies with the rise, fall, and alterations of a society of living organisms, it belongs to a growing class of what are called 'simulation games' (games that resemble real-life processes)."

Since its publication, the Game of Life has attracted much interest because of the surprising ways in which the patterns can evolve. It provides an example of emergence and self-organization. A version of Life that incorporates random fluctuations has been used in physics to study phase transitions and nonequilibrium dynamics.{{Cite journal|last1=Alstrøm|first1=Preben|last2=Leão|first2=João|date=1994-04-01|title=Self-organized criticality in the game of Life|url=https://link.aps.org/doi/10.1103/PhysRevE.49.R2507|journal=Physical Review E|volume=49|issue=4|pages=R2507–R2508|doi=10.1103/PhysRevE.49.R2507|pmid=9961636|bibcode=1994PhRvE..49.2507A|url-access=subscription}} The game can also serve as a didactic analogy, used to convey the somewhat counter-intuitive notion that design and organization can spontaneously emerge in the absence of a designer. For example, philosopher Daniel Dennett has used the analogy of the Game of Life "universe" extensively to illustrate the possible evolution of complex philosophical constructs, such as consciousness and free will, from the relatively simple set of deterministic physical laws which might govern our universe.{{cite book|last=Dennett|first=D. C.|date=1991|title=Consciousness Explained|location=Boston|publisher=Back Bay Books|isbn=978-0-316-18066-5|url-access=registration|url=https://archive.org/details/consciousnessexp00denn}}{{cite book|last=Dennett|first= D.C.|date=1995|title=Darwin's Dangerous Idea: Evolution and the Meanings of Life|url=https://archive.org/details/darwinsdangerous0000denn|url-access=registration|location=New York|publisher= Simon & Schuster|isbn= 978-0-684-82471-0}}{{cite book|last=Dennett|first= D.C.|date=2003|title=Freedom Evolves|location=New York|publisher=Penguin Books|isbn =978-0-14-200384-8}}

The popularity of the Game of Life was helped by its coming into being at the same time as increasingly inexpensive computer access. The game could be run for hours on these machines, which would otherwise have remained unused at night. In this respect, it foreshadowed the later popularity of computer-generated fractals. For many, the Game of Life was simply a programming challenge: a fun way to use otherwise wasted CPU cycles. For some, however, the Game of Life had more philosophical connotations. It developed a cult following through the 1970s and beyond; current developments have gone so far as to create theoretic emulations of computer systems within the confines of a Game of Life board.{{cite web|url=http://rendell-attic.org/gol/tm.htm|title=A Turing Machine in Conway's Game of Life|author=Paul Rendell|date=January 12, 2005|access-date=July 12, 2009|archive-date=April 17, 2019|archive-url=https://web.archive.org/web/20190417075720/http://rendell-attic.org/gol/tm.htm|url-status=live}}{{cite web|url=https://conwaylife.com/wiki/Spartan_universal_computer-constructor|title=Spartan universal computer-constructor|author=Adam P. Goucher|publisher=LifeWiki|access-date=December 5, 2021}}

Many different types of patterns occur in the Game of Life, which are classified according to their behaviour. Common pattern types include: still lifes, which do not change from one generation to the next; oscillators, which return to their initial state after a finite number of generations; and spaceships, which translate themselves across the grid.

The earliest interesting patterns in the Game of Life were discovered without the use of computers. 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. During this early research, Conway discovered that the R-pentomino failed to stabilize in a small number of generations. In fact, it takes 1103 generations to stabilize, by which time it has a population of 116 and has generated six escaping gliders;{{cite web|url=https://conwaylife.com/wiki/R-pentomino|title=R-pentomino|year=1983|pages=219, 223|publisher=LifeWiki|access-date=December 5, 2021|archive-date=December 6, 2021|archive-url=https://web.archive.org/web/20211206012009/https://www.conwaylife.com/wiki/R-pentomino|url-status=live}} these were the first spaceships ever discovered.{{cite web|url=https://conwaylife.com/ref/lexicon/lex_g.htm#glider|author=Stephen A. Silver|title=Glider|publisher=The Life Lexicon|access-date=March 4, 2019}}

Frequently occurring{{cite web|url=https://conwaylife.com/soup/census.asp?rule=B3/S23&sl=1&os=1&ss=1|archive-url=https://web.archive.org/web/20090910010855/https://conwaylife.com/soup/census.asp?rule=B3%2FS23&sl=1&os=1&ss=1|archive-date=2009-09-10|title=Census Results in Conway's Game of Life|publisher=The Online Life-Like CA Soup Search|access-date=July 12, 2009|url-status=dead}}

{{cite web|url=http://wwwhomes.uni-bielefeld.de/achim/moving.html|title=Spontaneous appeared Spaceships out of Random Dust|publisher=Achim Flammenkamp (1995-12-09)|access-date=July 10, 2012|archive-date=2009-04-13|archive-url=https://web.archive.org/web/20090413192821/http://wwwhomes.uni-bielefeld.de/achim/moving.html|url-status=live}} examples (in that they emerge frequently from a random starting configuration of cells) of the three aforementioned pattern types are shown below, with live cells shown in black and dead cells in white. Period refers to the number of ticks a pattern must iterate through before returning to its initial configuration.

{{col-begin|width=auto; margin:auto}}

{{col-break}}

{{col-break|gap=1em}}

{{col-break|gap=1em}}

{{col-end}}

The pulsar{{cite web|url=https://conwaylife.com/ref/lexicon/lex_p.htm#pulsar|title=Pulsar|author=Stephen A. Silver|publisher=The Life Lexicon|access-date=March 4, 2019}}

is the most common period-3 oscillator. The great majority of naturally occurring oscillators have a period of 2, like the blinker and the toad, but oscillators of all periods are known to exist,{{cite arXiv |eprint=2312.02799 |class=math.CO |first1=Nico |last1=Brown |first2=Carson |last2=Cheng |title=Conway's Game of Life is Omniperiodic |date=5 December 2023 |last3=Jacobi |first3=Tanner |last4=Karpovich |first4=Maia |last5=Merzenich |first5=Matthias |last6=Raucci |first6=David |last7=Riley |first7=Mitchell}}{{Cite web |title=LifeWiki:Game of Life Status page - LifeWiki |url=https://conwaylife.com/wiki/LifeWiki:Game_of_Life_Status_page |access-date=2023-12-16 |website=conwaylife.com}}{{Cite web |last=Stone |first=Alex |date=2024-01-18 |title=Math's 'Game of Life' Reveals Long-Sought Repeating Patterns |url=https://www.quantamagazine.org/maths-game-of-life-reveals-long-sought-repeating-patterns-20240118/ |access-date=2024-01-18 |website=Quanta Magazine |language=en |archive-date=2024-01-18 |archive-url=https://web.archive.org/web/20240118161936/https://www.quantamagazine.org/maths-game-of-life-reveals-long-sought-repeating-patterns-20240118/ |url-status=live }} and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions.{{cite web|url=http://wwwhomes.uni-bielefeld.de/achim/freq_top_life.html|title=Most seen natural occurring ash objects in Game of Life|author=Achim Flammenkamp|date=2004-09-07|access-date=2008-09-16|archive-date=2008-10-22|archive-url=https://web.archive.org/web/20081022033319/http://wwwhomes.uni-bielefeld.de/achim/freq_top_life.html|url-status=live}} Patterns which evolve for long periods before stabilizing are called Methuselahs, the first-discovered of which was the R-pentomino. Diehard is a pattern that disappears after 130 generations. Starting patterns of eight or more cells can be made to die after an arbitrarily long time.

{{cite web|url=https://conwaylife.com/ref/lexicon/lex_d.htm#diehard|title=Diehard|author=Stephen A. Silver|publisher=The Life Lexicon|access-date=March 4, 2019}} Acorn takes 5,206 generations to generate 633 cells, including 13 escaped gliders.{{cite web|url=http://pentadecathlon.com/lifeNews/2005/02/new_methuselah_records.html|title=New Methuselah Records|author=Koenig, H.|date=February 21, 2005|access-date=January 24, 2009|archive-date=September 10, 2019|archive-url=https://web.archive.org/web/20190910130327/http://pentadecathlon.com/lifeNews/2005/02/new_methuselah_records.html|url-status=dead}}

Conway originally conjectured that no pattern can grow indefinitely—i.e. that for any initial configuration with a finite number of living cells, the population cannot grow beyond some finite upper limit. In the game's original appearance in "Mathematical Games", Conway offered a prize of fifty dollars ({{Inflation|US|50|1970|fmt=eq|r=-1}}) to the first person who could prove or disprove the conjecture before the end of 1970. 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. For many years, this glider gun was the smallest one known.{{cite web|url=https://conwaylife.com/ref/lexicon/lex_g.htm#gosperglidergun|title=Gosper glider gun|author=Stephen A. Silver|publisher=The Life Lexicon|access-date=March 4, 2019}} In 2015, a gun called the "Simkin glider gun", which releases a glider every 120th generation, was discovered that has fewer live cells but which is spread out across a larger bounding box at its extremities.[https://conwaylife.com/forums/viewtopic.php?f=2&t=1599&start=200#p19125 The Hunting of the New Herschel Conduits] {{Webarchive|url=https://web.archive.org/web/20220224001858/https://conwaylife.com/forums/viewtopic.php?f=2&t=1599&start=200#p19125|date=2022-02-24}}, ConwayLife forums, April 28th, 2015, posts by Michael Simkin ("simsim314") and Dongook Lee ("Scorbie").

Smaller patterns were later found that also exhibit infinite growth. All three of the patterns shown below grow indefinitely. 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.

{{cite web|url=https://conwaylife.com/wiki/Block-laying_switch_engine|title=Block-laying switch engine|publisher=LifeWiki|access-date=December 5, 2021}} The third configuration creates two such patterns. The first has only ten live cells, which has been proven to be minimal.{{cite web|url=https://conwaylife.com/ref/lexicon/lex_i.htm#infinitegrowth|title=Infinite Growth|author=Stephen A. Silver|publisher=The Life Lexicon|access-date=March 4, 2019}} The second fits in a five-by-five square, and the third is only one cell high.

Later discoveries included other guns, which are stationary, and which produce gliders or other spaceships; puffer trains, which move along leaving behind a trail of debris; and rakes, which move and emit spaceships.{{cite web|url=https://conwaylife.com/ref/lexicon/lex_r.htm#rake|title=Rake|author=Stephen A. Silver|publisher=The Life Lexicon|access-date=March 4, 2019|archive-date=March 1, 2019|archive-url=https://web.archive.org/web/20190301232016/http://www.conwaylife.com/ref/lexicon/lex_r.htm#rake|url-status=live}} 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.

It is possible for gliders to interact with other objects in interesting ways. For example, if two gliders are shot at a block in a specific position, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This sliding block memory can be used to simulate a counter. It is possible to construct logic gates such as AND, OR, and NOT using gliders. It is possible to build a pattern that acts like a finite-state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; it is Turing complete. In fact, several different programmable computer architectures{{cite web|url=https://conwaylife.com/forums/viewtopic.php?f=2&t=2561#p37428|title=Programmable computer|publisher=conwaylife.com forums|access-date=August 23, 2018}}{{cite web|url=http://rendell-attic.org/gol/tm.htm|title=A Turing Machine in Conway's Game of Life, extendable to a Universal Turing Machine|publisher=Paul Rendell|access-date=August 23, 2018|archive-date=April 17, 2019|archive-url=https://web.archive.org/web/20190417075720/http://rendell-attic.org/gol/tm.htm|url-status=live}} have been implemented in the Game of Life, including a pattern that simulates Tetris.{{cite web|url=https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life/142673#142673|title=Build a working game of Tetris in Conway's Game of Life|publisher=StackExchange|access-date=August 23, 2018}}

Until the 2010s, all known spaceships could only move orthogonally or diagonally. Spaceships which move neither orthogonally nor diagonally are commonly referred to as oblique spaceships.{{Cite news|last=Aron|first=Jacob|date=16 June 2010|title=First replicating creature spawned in life simulator|periodical=New Scientist|url=https://www.newscientist.com/article/mg20627653.800-first-replicating-creature-spawned-in-life-simulator.html|access-date=12 October 2013}}{{cite web|title=Gemini – LifeWiki|url=https://conwaylife.com/wiki/Gemini|access-date=2013-10-16|publisher=Conwaylife.com}} On May 18, 2010, Andrew J. Wade announced the first oblique spaceship, dubbed "Gemini", that creates a copy of itself on (5,1) further while destroying its parent.{{cite web|title=Universal Constructor Based Spaceship|url=https://conwaylife.com/forums/viewtopic.php?f=2&t=399&p=2327#p2327|access-date=2012-06-24|publisher=Conwaylife.com}} 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. These, in turn, create new copies of the pattern, and destroy the previous copy. In December 2015, diagonal versions of the Gemini were built.{{cite web|title=Demonoid|url=https://conwaylife.com/wiki/Demonoid|access-date=18 June 2016|publisher=LifeWiki}}

A more specific case is a knightship, a spaceship that moves two squares left for every one square it moves down (like a knight in chess), whose existence had been predicted by Elwyn Berlekamp since 1982. The first elementary knightship, Sir Robin, was discovered in 2018 by Adam P. Goucher.{{cite web|url=https://conwaylife.com/forums/viewtopic.php?f=2&t=3303|title=Elementary knightship|access-date=9 March 2018}} This is the first new spaceship movement pattern for an elementary spaceship found in forty-eight years. "Elementary" means that it cannot be decomposed into smaller interacting patterns such as gliders and still lifes.[https://conwaylife.com/wiki/Elementary "Elementary"], LifeWiki. Retrieved 2018-11-21

A pattern can contain a collection of guns that fire gliders in such a way as to construct new objects, including copies of the original pattern. 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. 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.{{cite web|url=https://conwaylife.com/forums/viewtopic.php?f=2&t=1006&p=9917#p9901|title=Geminoid Challenge|publisher=Conwaylife.com|access-date=2015-06-25}} In October 2018, Adam P. Goucher finished his construction of the 0E0P metacell, a metacell capable of self-replication. This differed from previous metacells, such as the OTCA metapixel by Brice Due, which only worked with already constructed copies near them. The 0E0P metacell works by using construction arms to create copies that simulate the programmed rule.{{cite web|last=Passe-Science|title=Automate Cellulaire - Passe-science #27|via=YouTube|date=2019-05-29|url=https://www.youtube.com/watch?v=CfRSVPhzN5M|archive-url=https://ghostarchive.org/varchive/youtube/20211211/CfRSVPhzN5M|archive-date=2021-12-11|url-status=live|access-date=2019-06-25}}{{cbignore}} The actual simulation of the Game of Life or other Moore neighbourhood rules is done by simulating an equivalent rule using the von Neumann neighbourhood with more states.{{Cite web|url=https://cp4space.wordpress.com/2018/11/12/fully-self-directed-replication/|title=Fully self-directed replication|last=apgoucher|date=2018-11-12|website=Complex Projective 4-Space|language=en|access-date=2019-06-25}} The name 0E0P is short for "Zero Encoded by Zero Population", which indicates that instead of a metacell being in an "off" state simulating empty space, the 0E0P metacell removes itself when the cell enters that state, leaving a blank space.{{Cite web|url=https://conwaylife.com/wiki/0E0P|title=0E0P metacell - LifeWiki|website=conwaylife.com|access-date=2019-06-24}}

Many patterns in the Game of Life eventually become a combination of still lifes, oscillators, and spaceships; other patterns may be called chaotic. A pattern may stay chaotic for a very long time until it eventually settles to such a combination.

The Game of Life is undecidable, which means that given an initial pattern and a later pattern, no algorithm exists that can tell whether the later pattern is ever going to appear. Given that the Game of Life is Turing-complete, this is a corollary of the halting problem: the problem of determining whether a given program will finish running or continue to run forever from an initial input.

From most random initial patterns of living cells on the grid, observers will find the population constantly changing as the generations tick by. The patterns that emerge from the simple rules may be considered a form of mathematical beauty. Small isolated subpatterns with no initial symmetry tend to become symmetrical. Once this happens, the symmetry may increase in richness, but it cannot be lost unless a nearby subpattern comes close enough to disturb it. In a very few cases, the society eventually dies out, with all living cells vanishing, though this may not happen for a great many generations. Most initial patterns eventually burn out, producing either stable figures or patterns that oscillate forever between two or more states;{{cite web|url=http://www.geocities.com/conwaylife/|author=Andrzej Okrasinski|title=Game of Life Object Statistics|access-date=July 12, 2009|archive-url=https://web.archive.org/web/20090727010353/http://geocities.com/conwaylife/|archive-date=2009-07-27}}{{cite web|url=https://conwaylife.com/soup/|archive-url=https://web.archive.org/web/20090910010849/https://conwaylife.com/soup/|archive-date=2009-09-10|author=Nathaniel Johnston|title=The Online Life-Like CA Soup Search|access-date=July 12, 2009}} many also produce one or more gliders or spaceships that travel indefinitely away from the initial location. 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. Most of the early algorithms were similar: they represented the patterns as two-dimensional arrays in computer memory. Typically, two arrays are used: one to hold the current generation, and one to calculate its successor. Often 0 and 1 represent dead and live cells, respectively. A nested for loop considers each element of the current array in turn, counting the live neighbours of each cell to decide whether the corresponding element of the successor array should be 0 or 1. The successor array is displayed. For the next iteration, the arrays may swap roles so that the successor array in the last iteration becomes the current array in the next iteration, or one may copy the values of the second array into the first array then update the second array from the first array again.

A variety of minor enhancements to this basic scheme are possible, and there are many ways to save unnecessary computation. 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.{{cite web|url=http://www.ibiblio.org/lifepatterns/lifeapplet.html|title=About my Conway's Game of Life Applet|author=Alan Hensel|access-date=July 12, 2009|archive-date=July 16, 2009|archive-url=https://web.archive.org/web/20090716231902/http://www.ibiblio.org/lifepatterns/lifeapplet.html|url-status=live}}

File:Trefoil knot conways game of life.gif trefoil knot]]

To avoid decisions and branches in the counting loop, the rules can be rearranged from an egocentric approach of the inner field regarding its neighbours to a scientific observer's viewpoint: if the sum of all nine fields in a given neighbourhood is three, the inner field state for the next generation will be life; if the all-field sum is four, the inner field retains its current state; and every other sum sets the inner field to death.

To save memory, the storage can be reduced to one array plus two line buffers. 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. The first buffer is then written to its line and freed to hold the successor state for the third line. 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.

File:Long gun.gif

File:Игра "Жизнь".gif

In principle, the Game of Life field is infinite, but computers have finite memory. This leads to problems when the active area encroaches on the border of the array. Programmers have used several strategies to address these problems. The simplest strategy is to assume that every cell outside the array is dead. This is easy to program but leads to inaccurate results when the active area crosses the boundary. A more sophisticated trick is to consider the left and right edges of the field to be stitched together, and the top and bottom edges also, yielding a toroidal array. The result is that active areas that move across a field edge reappear at the opposite edge. Inaccuracy can still result if the pattern grows too large, but there are no pathological edge effects. Techniques of dynamic storage allocation may also be used, creating ever-larger arrays to hold growing patterns. 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.

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. This allows the pattern to move about the field unhindered, as long as the population does not exceed the size of the live-coordinate array. The drawback is that counting live neighbours becomes a hash-table lookup or search operation, slowing down simulation speed. With more sophisticated data structures this problem can also be largely solved.{{Citation needed|date=September 2023}}

For exploring large patterns at great time depths, sophisticated algorithms such as Hashlife may be useful. There is also a method for implementation of the Game of Life and other cellular automata using arbitrary asynchronous updates while still exactly emulating the behaviour of the synchronous game.{{cite conference|title=Self-Reproduction in Asynchronous Cellular Automata|first=Chrystopher L.|last=Nehaniv|date=15–18 July 2002|conference=2002 NASA/DoD Conference on Evolvable Hardware|conference-url=https://ieeexplore.ieee.org/xpl/conhome/8000/proceeding|publisher=IEEE Computer Society Press|location=Alexandria, Virginia, USA|pages=201–209|isbn=0-7695-1718-8|doi=10.1109/EH.2002.1029886|hdl=2299/6834|hdl-access=free}} Source code examples that implement the basic Game of Life scenario in various programming languages, including C, C++, Java and Python can be found at Rosetta Code.{{Cite web|url=https://rosettacode.org/wiki/Conway%27s_Game_of_Life|title=Conway's Game of Life|date=June 7, 2024|website=Rosetta Code|access-date=July 2, 2024|archive-date=July 18, 2024|archive-url=https://web.archive.org/web/20240718213019/https://rosettacode.org/wiki/Conway%27s_Game_of_life|url-status=live}}

{{main|Life-like cellular automaton}}

Since the Game of Life's inception, new, similar cellular automata have been developed. The standard Game of Life is symbolized in rule-string notation as B3/S23. A cell is born if it has exactly three neighbours, survives if it has two or three living neighbours, and dies otherwise. The first number, or list of numbers, is what is required for a dead cell to be born. The second set is the requirement for a live cell to survive to the next generation. Hence B6/S16 means "a cell is born if there are six neighbours, and lives on if there are either one or six neighbours". Cellular automata on a two-dimensional grid that can be described in this way are known as Life-like cellular automaton. Another common {{Not a typo|Life-like}} automaton, Highlife, is described by the rule B36/S23, because having six neighbours, in addition to the original game's B3/S23 rule, causes a birth. HighLife is best known for its frequently occurring replicators.[http://www.tip.net.au/~dbell/articles/HighLife.zip HighLife – An Interesting Variant of Life] by David Bell (.zip file){{cite web|url=https://conwaylife.com/ref/lexicon/lex_r.htm#replicator|title=Replicator|publisher=The Life Lexicon|author=Stephen A. Silver|access-date=March 4, 2019|archive-date=March 1, 2019|archive-url=https://web.archive.org/web/20190301232016/http://www.conwaylife.com/ref/lexicon/lex_r.htm#replicator|url-status=live}}

Additional Life-like cellular automata exist. The vast majority of these 2¹⁸ different rules{{cite web|url=https://conwaylife.com/wiki/Life-like#Life-like_cellular_automata|title=Life-like cellular automata - LifeWiki|publisher=Conwaylife.com|access-date=March 4, 2019|archive-date=March 6, 2019|archive-url=https://web.archive.org/web/20190306043758/http://conwaylife.com/wiki/Life-like#Life-like_cellular_automata|url-status=live}} produce universes that are either too chaotic or too desolate to be of interest, but a large subset do display interesting behaviour. A further generalization produces the isotropic rulespace, with 2¹⁰² possible cellular automaton rules{{cite web|url=https://conwaylife.com/wiki/Isotropic|title=Isotropic - LifeWiki|publisher=Conwaylife.com|access-date=March 4, 2019|archive-date=March 6, 2019|archive-url=https://web.archive.org/web/20190306043649/http://conwaylife.com/wiki/Isotropic|url-status=live}} (the Game of Life again being one of them). These are rules that use the same square grid as the Life-like rules and the same eight-cell neighbourhood, and are likewise invariant under rotation and reflection. However, in isotropic rules, the positions of neighbour cells relative to each other may be taken into account in determining a cell's future state—not just the total number of those neighbours.

File:Oscillator.gif

Some variations on the Game of Life modify the geometry of the universe as well as the rules. The above variations can be thought of as a two-dimensional square, because the world is two-dimensional and laid out in a square grid. One-dimensional square variations, known as elementary cellular automata,{{cite web|url=http://mathworld.wolfram.com/ElementaryCellularAutomaton.html|publisher=Wolfram Mathworld|title=Elementary Cellular Automaton|access-date=July 12, 2009|archive-date=July 3, 2009|archive-url=https://web.archive.org/web/20090703200815/http://mathworld.wolfram.com/ElementaryCellularAutomaton.html|url-status=live}} and three-dimensional square variations have been developed, as have two-dimensional hexagonal and triangular variations. A variant using aperiodic tiling grids has also been made.{{cite magazine|url=https://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html|magazine=New Scientist|title=First gliders navigate ever-changing Penrose universe}}

Conway's rules may also be generalized such that instead of two states, live and dead, there are three or more. State transitions are then determined either by a weighting system or by a table specifying separate transition rules for each state; for example, Mirek's Cellebration's multi-coloured Rules Table and Weighted Life rule families each include sample rules equivalent to the Game of Life.

Patterns relating to fractals and fractal systems may also be observed in certain {{Not a typo|Life-like}} variations. 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,Stephen Wolfram, A New Kind of Science online, [https://www.wolframscience.com/nks/notes-6-8--structures-in-the-game-of-life/ Note (f) for structures in class 4 systems: Structures in the Game of Life]: "A simpler kind of unbounded growth occurs if one starts from an infinite line of black cells. In that case, the evolution is effectively 1D, and turns out to follow elementary rule 22" as well as in Highlife, Seeds (B2/S), and Stephen Wolfram's Rule 90.{{cite web|url=https://conwaylife.com/forums/viewtopic.php?f=7&t=90|title=Life Imitates Sierpinski|publisher=ConwayLife.com forums|access-date=July 12, 2009}}

Immigration is a variation that is very similar to the Game of Life, except that there are two on states, often expressed as two different colours. Whenever a new cell is born, it takes on the on state that is the majority in the three cells that gave it birth. This feature can be used to examine interactions between spaceships and other objects within the game.

{{cite web|url=https://conwaylife.com/ref/lexicon/lex_i.htm#immigration|title=Immigration|publisher=The Life Lexicon|author=Stephen A. Silver|access-date=March 4, 2019}} Another similar variation, called QuadLife, involves four different on states. When a new cell is born from three different on neighbours, it takes the fourth value, and otherwise, like Immigration, it takes the majority value.{{cite web|url=https://conwaylife.com/ref/lexicon/lex_q.htm#quadlife|title=QuadLife|publisher=The Life Lexicon|author=Stephen A. Silver|access-date=March 4, 2019}} Except for the variation among on cells, both of these variations act identically to the Game of Life.

Various musical composition techniques use the Game of Life, especially in MIDI sequencing.{{Cite conference|last1 = Burraston|first1 = Dave|last2 = Edmonds|first2 = Ernest|last3 = Livingstone|first3 = Dan|last4 = Miranda|first4 = Eduardo Reck|author-link4 = Eduardo Reck Miranda|contribution = Cellular Automata in MIDI based Computer Music|contribution-url = http://quod.lib.umich.edu/i/icmc/bbp2372.2004.047?view=image|title = Proceedings of the 2004 International Computer Music Conference|year = 2004|citeseerx = 10.1.1.6.3882|hdl = 10453/1425|isbn = 9780971319226|access-date = 2012-07-05|archive-date = 2023-01-11|archive-url = https://web.archive.org/web/20230111115704/https://quod.lib.umich.edu/i/icmc/bbp2372.2004.047?view=image|url-status = live}} A variety of programs exist for creating sound from patterns generated in the Game of Life.{{cite web|url=http://www.synthtopia.com/content/2008/05/29/glitchds-cellular-automaton-sequencer-for-the-nintendo-ds/|title=glitchDS – Cellular Automaton Sequencer For The Nintendo DS|publisher=Synthtopia.com|date=2008-05-29|access-date=2012-06-24|archive-date=2012-07-26|archive-url=https://web.archive.org/web/20120726170457/http://www.synthtopia.com/content/2008/05/29/glitchds-cellular-automaton-sequencer-for-the-nintendo-ds/|url-status=live}}{{cite web|url=http://www.synthtopia.com/content/2009/04/29/game-of-life-music-sequencer/|title=Game Of Life Music Sequencer|publisher=Synthtopia.com|date=2009-04-29|access-date=2012-06-24|archive-date=2012-07-26|archive-url=https://web.archive.org/web/20120726113942/http://www.synthtopia.com/content/2009/04/29/game-of-life-music-sequencer/|url-status=live}}{{cite web|url=http://www.synthtopia.com/content/2011/01/12/game-of-life-music-sequencer-for-ios-runxt-life/|title=Game Of Life Music Sequencer For iOS, Runxt Life|publisher=Synthtopia.com|date=2011-01-12|access-date=2012-06-24|archive-date=2012-07-26|archive-url=https://web.archive.org/web/20120726014246/http://www.synthtopia.com/content/2011/01/12/game-of-life-music-sequencer-for-ios-runxt-life/|url-status=live}}

File:Turing Machine in Golly.png, made in the Game of Life, computed in less than 30 seconds on an Intel Core Duo 2 GHz CPU using Golly in Hashlife mode]]

Computers have been used to follow and simulate the Game of Life since it was first publicized. 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. This was tedious and prone to errors. 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."

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.{{cite magazine|last=Helmers|first=Carl|title=About the Cover|magazine=Byte|date=June 1976|issue=10|pages=6–7|url=https://archive.org/stream/byte-magazine-1976-06/1976_06_BYTE_00-10_The_Game_of_LIFE_in_Color#page/n7/mode/2up|accessdate=February 18, 2013}} The advent of microcomputer-based color graphics from Cromemco has been credited with a revival of interest in the game.{{cite journal|last1=McIntosh|first1=Harold|author1-link=Harold V. McIntosh|title=Introduction|journal=Journal of Cellular Automata|year=2008|volume=13|pages=181–186|url=http://comunidad.escom.ipn.mx/LCCOMP/Announces/Entries/2015/12/23_LCCOMP_Obituaries_2015_files/181-186pp%20JCA-HM07-00.pdf|archive-url=https://ghostarchive.org/archive/20221009/http://comunidad.escom.ipn.mx/LCCOMP/Announces/Entries/2015/12/23_LCCOMP_Obituaries_2015_files/181-186pp%20JCA-HM07-00.pdf|archive-date=2022-10-09|url-status=live|access-date=3 November 2021|quote=With the advent of microcomputers and Cromemco's graphics board, Life became a favorite display program for video monitors and led to a revival of interest in the game.}}

Two early implementations of the Game of Life on home computers were by Malcolm Banthorpe written in BBC BASIC. The first was in the January 1984 issue of Acorn User magazine, and Banthorpe followed this with a three-dimensional version in the May 1984 issue.{{cite web|url=http://8bs.com/aumags.htm|title=Acorn User Magazine Scans|author=|publisher=The BBC and Master Computer Public Domain Library|access-date=2018-12-29|archive-date=2013-01-16|archive-url=https://archive.today/20130116100942/http://8bs.com/aumags.htm|url-status=live}} 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.{{cite web|url=https://www-users.cs.york.ac.uk/susan/bib/ss/au.htm|title= AcornUser articles|last= Stepney|first= Susan|website=www-users.cs.york.ac.uk|publisher= AcornUser|access-date=2018-12-29}}

There are now thousands of Game of Life programs online, so a full list will not be provided here. The following is a small selection of programs with some special claim to notability, such as popularity or unusual features. 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.

• Golly is a cross-platform (Windows, Macintosh, Linux, iOS, and Android) open-source simulation system for the Game of Life and other cellular automata (including all Life-like cellular automata, the Generations family of cellular automata from Mirek's Cellebration, and John von Neumann's 29-state cellular automaton) built by Andrew Trevorrow and Tomas Rokicki. It includes the Hashlife algorithm for extremely fast generation, and Lua or Python scriptability for both editing and simulation.
• Mirek's Cellebration is a freeware one- and two-dimensional cellular automata viewer, explorer, and editor for Windows. It includes powerful facilities for simulating and viewing a wide variety of cellular automaton rules, including the Game of Life, and a scriptable editor.
• Xlife is a cellular-automaton laboratory by Jon Bennett. The standard UNIX X11 Game of Life simulation application for a long time, it has also been ported to Windows. It can handle cellular automaton rules with the same neighbourhood as the Game of Life, and up to eight possible states per cell.{{Cite web|url=https://conwaylife.com/wiki/Xlife|title=Xlife - LifeWiki|website=conwaylife.com}}
• Dr. Blob's Organism is a Shoot 'em up based on Conway's Life. In the game, Life continually generates on a group of cells within a "petri dish". The patterns formed are smoothed and rounded to look like a growing amoeba spewing smaller ones (actually gliders). Special "probes" zap the "blob" to keep it from overflowing the dish while destroying its nucleus.{{Cite web |title=Dr. Blob's Organism - It's free! |url=https://digital-eel.com/organism/ |website=digital-eel.com}}

Google implemented an easter egg of the Game of Life in 2012. Users who search for the term are shown an implementation of the game in the search results page.{{Cite news |last=Wasserman |first=Todd |date=12 July 2012 |title=Type 'Conway's Game of Life' on Google and See What Happens |url=https://mashable.com/2012/07/12/conways-game-of-life-google/ |access-date=1 May 2020 |work=Mashable |language=}}

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. Near the end of Anonymous;Code, a certain pattern that appears throughout the game as a tattoo on the heroine Momo Aizaki has to be entered into the Game of Life to complete the game (Kok's galaxy, the same pattern used as the logo for the open-source Game of Life program Golly).

{{cols|colwidth=26em}}

• {{annotated link|Artificial life}}
• {{annotated link|Glory Season|Glory Season}}, is set in a future society where the Game of Life is played in a competitive two-player mode
• {{annotated link|Langton's ant}}
• {{annotated link|Poietic Generator}}, a "human" Game of Life.
• {{section link|Self-organization|Computer science}}
• {{annotated link|Of_Man_and_Manta|Of Man and Manta}}; the novel 'OX' features a cellular automaton lifeform based on Game of Life
• {{annotated link|LifeWiki}}
• {{annotated link|Boids}} (simulation of flocking birds)

{{colend}}

{{Reflist|group=nb}}

{{Reflist|30em}}

{{commons}}

• [https://conwaylife.com/ref/lexicon/lex_home.htm Life Lexicon] conwaylife.com: extensive lexicon with many patterns
• [https://conwaylife.com/wiki/ LifeWiki] conwaylife.com
• [https://catagolue.appspot.com/home Catagolue] catagolue.appspot.com: online database of objects in Conway's Game of Life and similar cellular automata
• [https://cafaq.com/lifefaq/index.php Cellular Automata FAQ – Conway's Game of Life] cafaq.com
• [https://uk.mathworks.com/matlabcentral/fileexchange/80176-conways-game-of-life-equation Algebraic formula] uk.mathworks.com: recurrence relation for iterating Conway's Game of Life.

{{Conway's Game of Life}}

Category:Cellular automaton rules

Category:Self-organization

Category:Games and sports introduced in 1970

Category:John Horton Conway