Problem

From LifeWiki
Jump to navigation Jump to search

An open problem is a problem for which no solution has been found. A current example is "What is the smallest still life that cannot be destroyed by two gliders?".

Unsolved problems can be subdivided into several basic categories:

  • Temporal minimization problems: As above, but concentrating on speed rather than size.

List of problems

Open and previously open problems include:

Category Problem Status Year posed Posed by Year solved Solved by
Description
Infinite growth 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]
Infinite growth Minimal-population infinite growth solved ? ? 1997 Paul Callahan
The question "What is the minimum population necessary for a pattern to exhibit infinite growth?" was found to be 10 cells by an exhaustive search.[2] There are 24 such patterns, with 17 unique evolution sequences. (The equivalent question for quadratic growth is thus between 11 and 20.)
Infinite growth 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.
Still lifes 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.
Still lifes 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.[3]
Density Still life conjecture solved ? ? 1999 Noam D. Elkies
The question "What is the maximum density of a still life agar?" has been answered to be 12.[4]
The proof requires only that no living cell has more than three living neighbours (including itself), so provides that the maximal density is 12 in all rules with survival conditions constrained to a subset of S0123.
Density Oscillator conjecture open ? ?
What is the maximum average density of an oscillating agar?
The conjectured value is 12, the maximum that has been achieved. It was proven to be 813 ≈ 0.6153... on September 18, 1992,[5] which was improved to 1728 ≈ 0.6071... on December 16, 2023 by 400spartans,[6] then to 11762087 ≈ 0.5634... on January 9, 2024 by Keith Amling.[7]
Density Still life density problem solved ? ? 2012 Geoffrey Chu, Peter J. Stuckey
The question "What is the maximum number of cells in a still life fitting in an n × n bounding box?" has been solved. As a sequence with respect to n, after the first 60 terms, the sequence's second differences oscillate with period 54.[8]
Oscillators Omniperiodicity solved ? ? 2023 various people
The question “do oscillators of all periods exist?” has been answered in the affirmative.
Oscillators Non-p2 phoenix solved ? ? 2024 Adam P. Goucher, Keith Amling, Alex Greason, Stephen Silver
The question “Does there exist a finite oscillator of period > 2 such that no cell remains on contiguously for more than one generation?” was answered in the negative.[9] (The question for infinite agars and wicks was previously answered in the affirmative.)
Predecessors 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.
Predecessors 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.
Predecessors 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.[10]
Computation 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]
Computation Universality of predecessor-finding solved ? ? 2023 Ville Salo and Ilkka Törmä
The question "can problems of finding predecessors of specific patterns be equivalent to arbitrary Boolean satisfiability problems?" was answered in the affirmative, with the corollary that the process of reversing a single iteration (or otherwise proving that a pattern is a Garden of Eden) is computationally universal.[11]
Circuitry 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.[12] 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.[13]
Agar crawlers Minimum speed open ? ?
Does there exist a negative spaceship in an agar of density 12 that travels at a speed ≤ c/2?
In zebra stripes, a with-the-grain agar crawler must travel at c (making it a lightspeed bubble),[14] but Hartmut Holzwart proved in 2006 that an against-the-grain agar crawler's speed is ≤ 2c/3.
Agar crawlers Bound-height lightspeed bubbles solved ? ? 2017 Arie Paap
The question "Does there exist an n such that a lightspeed bubble containing an empty region of any width may be constructed with height ≤ n?" was answered in the positive, with n ≤ 37.[15]
Indestructibility 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?
Indestructibility The Single-Glider-Proof Object Problem open ? ?
Does there exist a bounded pattern such that a collision with a nonempty glider approaching from infinity (at any direction and offset) results in the glider's destruction and the pattern's eventual evolution being unaffected?

References

  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. Nick Gotts (November 28, 2018). Systematic survey of small patterns (discussion thread) at the ConwayLife.com forums
  3. Martin Grant (December 28, 2019). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
  4. Noam D. Elkies (May 31, 1999). "The still-Life density problem and its generalizations". Retrieved on May 26, 2022.
  5. Hartmut Holzwart (June 22, 2022). Re: Can we substantiate this claim? (discussion thread) at the ConwayLife.com forums
  6. 400spartans (December 16, 2023). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
  7. Keith Amling (January 9, 2024). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
  8. "A Complete Solution to the Maximum Density Still Life Problem". Geoffrey Chu, Peter J. Stuckey, NICTA Victoria Laboratory, Department of Computing and Information Systems, University of Melbourne, Australia (November 8, 2013).
  9. Adam P. Goucher (January 20, 2024), Every finite phoenix has period 2, Complex Projective 4-Space
  10. Ilkka Törmä (January 13, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
  11. Ville Salo, Ilkka Törmä (August 20, 2023), Computing backwards with Game of Life, part 1: wires and circuits
  12. Mike Playle (April 27, 2013). Re: Just the place for a Snark! (discussion thread) at the ConwayLife.com forums
  13. Mike Playle (September 11, 2020). Re: Execution of Old Guns by Variable-Speed Firing Squad (discussion thread) at the ConwayLife.com forums
  14. Nathaniel Johnston, Dave Greene. Conway's Game of Life: Mathematics and Construction (2022), 4.5.1. (Theorem 4.2)
  15. Arie Paap (February 15, 2017). Re: How about searching light speed signals with various speed? (discussion thread) at the ConwayLife.com forums

External links