Problem
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:
- 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, until DOGun SaGaQR, no quadratic growth replicator had been constructed, but a workable blueprint was available, and no really large new technical problems would have had 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.
- Minimization problems: Find an object that satisfies some criterion that fits within a certain bounding box/minimum population. 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:
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.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
- ↑ Nick Gotts (November 28, 2018). Systematic survey of small patterns (discussion thread) at the ConwayLife.com forums
- ↑ Martin Grant (December 28, 2019). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ Noam D. Elkies (May 31, 1999). "The still-Life density problem and its generalizations". Retrieved on May 26, 2022.
- ↑ Hartmut Holzwart (June 22, 2022). Re: Can we substantiate this claim? (discussion thread) at the ConwayLife.com forums
- ↑ 400spartans (December 16, 2023). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ Keith Amling (January 9, 2024). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ "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).
- ↑ Adam P. Goucher (January 20, 2024), Every finite phoenix has period 2, Complex Projective 4-Space
- ↑ Ilkka Törmä (January 13, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ Ville Salo, Ilkka Törmä (August 20, 2023), Computing backwards with Game of Life, part 1: wires and circuits
- ↑ Mike Playle (April 27, 2013). Re: Just the place for a Snark! (discussion thread) at the ConwayLife.com forums
- ↑ Mike Playle (September 11, 2020). Re: Execution of Old Guns by Variable-Speed Firing Squad (discussion thread) at the ConwayLife.com forums
- ↑ Nathaniel Johnston, Dave Greene. Conway's Game of Life: Mathematics and Construction (2022), 4.5.1. (Theorem 4.2)
- ↑ Arie Paap (February 15, 2017). Re: How about searching light speed signals with various speed? (discussion thread) at the ConwayLife.com forums
External links
- Unproven conjectures (discussion thread) at the ConwayLife.com forums
- Life has been proven omniperiodic. What next? (discussion thread) at the ConwayLife.com forums