Editing Conway's Game of Life (section)

==Examples of patterns==
Many different types of patterns occur in the Game of Life, which are classified according to their behaviour. Common pattern types include: ''[[Still life (cellular automaton)|still lifes]]'', which do not change from one generation to the next; ''[[Oscillator (cellular automaton)|oscillators]]'', which return to their initial state after a finite number of generations; and ''[[spaceship (cellular automaton)|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]], [[blackboard]]s, and physical game boards, such as those used in [[Go (board game)|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 [[Glider (Conway's Life)|gliders]];<ref>{{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}}</ref> these were the first spaceships ever discovered.<ref>{{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}}</ref>

Frequently occurring<ref>{{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}}
</ref><ref>{{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}}</ref> 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}}
{|class="wikitable"
|-
!colspan="2"|Still lifes
|-
|Block
|[[File:Game of life block with border.svg]]
|-
|Bee-<br>hive
|[[File:Game of life beehive.svg]]
|-
|Loaf
|[[File:Game of life loaf.svg]]
|-
|Boat
|[[File:Game of life boat.svg]]
|-
|Tub
|[[File:Game of life flower.svg]]
|}
{{col-break|gap=1em}}
{|class="wikitable"
|-
|!colspan="2"|Oscillators
|-
|Blinker<br>(period 2)
|[[File:game of life blinker.gif]]
|-
|Toad<br>(period 2)
|[[File:game of life toad.gif]]
|-
|Beacon<br>(period 2)
|[[File:game of life beacon.gif]]
|-
|Pulsar<br>(period 3)
|[[File:game of life pulsar.gif]]
|-
|Penta-<br>decathlon<br>(period&nbsp;15)
|[[File:I-Column.gif]]
|}
{{col-break|gap=1em}}
{|class="wikitable"
|-
|!colspan="2"|Spaceships
|-
|Glider
|[[File:Game of life animated glider.gif]]
|-
|Light-<br>weight<br>spaceship<br>(LWSS)
|[[File:Game of life animated LWSS.gif]]
|-
|Middle-<br>weight<br>spaceship<br>(MWSS)
|[[File:Animated Mwss.gif]]
|-
|Heavy-<br>weight<br>spaceship<br>(HWSS)
|[[File:Animated Hwss.gif]]
|}
{{col-end}}

The ''pulsar''<ref>{{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}}
</ref> 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,<ref>{{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}}</ref><ref>{{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}}</ref><ref>{{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 }}</ref> and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions.<ref>{{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}}</ref> Patterns which evolve for long periods before stabilizing are called ''[[Methuselah (cellular automaton)|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.<ref>
{{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}}</ref> ''Acorn'' takes 5,206 generations to generate 633 cells, including 13 escaped gliders.<ref>{{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}}</ref>

{|style="margin:auto; text-align:center;"
|-
|[[File:Game of life fpento.svg|framed|The R-pentomino]]
|[[File:game of life diehard.svg|framed|Diehard]]
|[[File:game of life acorn.svg|framed|Acorn]]
|}

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.<ref>{{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}}</ref> 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.<ref>[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").</ref>
{|style="margin:auto; text-align:center;"
|-
|[[File:Game of life glider gun.svg|thumb|500px|Gosper glider gun]]
|-
|[[File:Game of life Simkin glider gun.svg|thumb|500px|Simkin glider gun]]
|}

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.<ref>
{{cite web|url=https://conwaylife.com/wiki/Block-laying_switch_engine|title=Block-laying switch engine|publisher=LifeWiki|access-date=December 5, 2021}}</ref> The third configuration creates two such patterns. The first has only ten live cells, which has been proven to be minimal.<ref>{{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}}</ref> The second fits in a five-by-five square, and the third is only one cell high.

{|style="margin:auto; text-align:center;"
|-
|[[File:game of life infinite1.svg]] [[File:game of life infinite2.svg]]
|-
|<br>[[File:game of life infinite3.svg]]
|}
Later discoveries included other ''[[Gun (cellular automaton)|guns]]'', which are stationary, and which produce gliders or other spaceships; ''[[puffer train]]s'', which move along leaving behind a trail of debris; and ''[[rake (cellular automaton)|rakes]]'', which move and emit spaceships.<ref>{{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}}</ref> Gosper also constructed the first pattern with an [[Asymptotically optimal algorithm|asymptotically optimal]] [[quadratic growth|quadratic growth rate]], called a ''[[Breeder (cellular automaton)|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 (digital)|counter]]. It is possible to construct [[logic gate]]s such as ''[[logical conjunction|AND]]'', ''[[Logical disjunction|OR]]'', and ''[[Negation|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]].<ref name="chapman"/><ref name="bcg"/> In fact, several different programmable computer architectures<ref>{{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}}</ref><ref>{{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}}</ref> have been implemented in the Game of Life, including a pattern that simulates [[Tetris]].<ref>{{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}}</ref>

===Oblique spaceships===
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''.<ref>{{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}}</ref><ref name=":1">{{cite web|title=Gemini – LifeWiki|url=https://conwaylife.com/wiki/Gemini|access-date=2013-10-16|publisher=Conwaylife.com}}</ref> 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.<ref>{{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}}</ref><ref name=":1"/> 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.<ref>{{cite web|title=Demonoid|url=https://conwaylife.com/wiki/Demonoid|access-date=18 June 2016|publisher=LifeWiki}}</ref>

A more specific case is a ''knightship'', a spaceship that moves two squares left for every one square it moves down (like a [[Knight (chess)|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.<ref>{{cite web|url=https://conwaylife.com/forums/viewtopic.php?f=2&t=3303|title=Elementary knightship|access-date=9 March 2018}}</ref> 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.<ref>[https://conwaylife.com/wiki/Elementary "Elementary"], LifeWiki. Retrieved 2018-11-21</ref>

===Self-replication===

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.<ref name="bcg"/> On November 23, 2013, Dave Greene built the first [[replicator (cellular automaton)|replicator]] in the Game of Life that creates a complete copy of itself, including the instruction tape.<ref>{{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}}</ref> 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.<ref>{{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}}</ref> 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.<ref>{{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}}</ref> 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.<ref>{{Cite web|url=https://conwaylife.com/wiki/0E0P|title=0E0P metacell - LifeWiki|website=conwaylife.com|access-date=2019-06-24}}</ref>