From LifeWiki
Jump to navigation Jump to search

An open problem is a problem for which no solution has been found. An example is "Do oscillators of all periods exist in Conway's Game of Life?".

Unsolved problems can be subdivided into several basic categories:

  • Periods: Do oscillators, spaceships, guns or puffers exist of a particular period?
  • Unusual-growth patterns: What is the long-term effect of a predefined pattern? For example, it is unknown whether the Fermat prime calculator grows indefinitely.
  • Solvable problems: Some problems are known to have a solution, but as yet no pattern has been built. For instance, no Conway's Life quadratic growth replicator has been built to date, but a workable blueprint is available, and no really large new technical problems would have to be overcome to complete the construction.
  • Construction and destruction problems: These include finding the smallest Garden of Eden, building a stable eater that can absorb any single glider aimed at it, determining whether a particular object has a glider synthesis, or discovering an unstoppable-growth pattern.
  • Spatial minimization problems: Find an object that satisfies some criterion that fits within a certain bounding box. Examples include Mike Playle's prize for a small stable reflector.
  • Temporal minimization problems: As above, but concentrating on speed rather than size.

List of problems

Open and previously open problems include:

Problem Status Year posed Posed by Year solved Solved by
one cell thick infinite growth solved ? Nick Gotts 1998 Stephen Silver
The question “is there a one-cell-thick pattern exhibiting infinite growth?was answered in the affirmative.
Coolout Conjecture solved <1992 Richard Schroeppel 2001 Richard Schroeppel
The question “given a partial Life pattern that's internally consistent with being part of a still life (stable pattern), is there always a way to add a stabilizing boundary?” was answered in the negative.
The Immovable Object Problem open 1972 John Conway
Does there exist a bounded pattern such that the central cell will never change state no matter what is placed outside the pattern's boundary?
Garden of Eden solved ? ? <1970 Edward Moore
The existence of a Garden of Eden in Conway's Game of Life was known from the start because of a 1962 theorem by Edward Moore that guarantees their existence in a wide class of cellular automata.
Grandfather problem solved 1972 John Conway 2016 mtve
The question “is there a configuration which has a father but no grandfather?” was answered in the affirmative.
Omniperiodicity open ? ?
The question “do oscillators of all periods exist?” remains open for Conway's Game of Life; no oscillators are known for period 19 and 41.
Replicators solved ? ? 1982 Elwyn R. Berlekamp, John Conway, Richard K. Guy
The question “do replicators exist in Conway's Game of Life?” was answered in the affirmative.[1]
Still life finitization problem open ? Dean Hickerson
The question "given a still life without finite boundaries, can any MxN finite window of it be preserved within a finite still life by adding appropriate unchanging cells around it?" remains open. It has been shown that the margin around a window needed to stabilise it might be arbitrarily large.[2]
Unique father problem solved 1972 John Conway 2022 Ilkka Törmä, Ville Salo
The question “is there a stable configuration whose only father is itself?” was answered in the affirmative.[3]
Universal computer / Universal constructor solved ? John Conway 1982 Elwyn R. Berlekamp, John Conway, Richard K. Guy
The question “does Conway's Game of Life support universal computation and universal construction?” was answered in the affirmative.[1]
Small glider reflector / duplicator open 2013, 2020 Mike Playle
After the discovery of the color-preserving Snark in 2013, Mike Playle offered 100 USD for a stable 90-degree colour-changing glider reflector that fits in a 25x25 bounding box and has a repeat time of 50 generations or less.[4] When the 0-degree Bandersnatch was found in 2020, he released another prize of 200 USD for a stable pattern which fits in a 25x25 bounding box, has a repeat time of 50 generations or less, and produces two output gliders that emerge in different directions and do not affect input gliders from infinity.[5]


  1. 1.0 1.1 Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2004), Winning Ways for Your Mathematical Plays, 4 (2nd ed.), pp. 927-961
  2. Martin Grant (December 28, 2019). Re: Unproven conjectures (discussion thread) at the forums
  3. Ilkka Törmä (January 13, 2022). Re: Unproven conjectures (discussion thread) at the forums
  4. Mike Playle (April 27, 2013). Re: Just the place for a Snark! (discussion thread) at the forums
  5. Mike Playle (September 11, 2020). Re: Execution of Old Guns by Variable-Speed Firing Squad (discussion thread) at the forums

External links