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] | ||||||
Still lifes / constructability | Block array syntheses | open | ≤ 2005 | — | — | |
Can every m × n array of blocks spaced one cell apart be constructed by gliders? In 2005, Jason Summers found a construction for 2 × n block arrays.[4] In 2015, Martin Grant found a construction for 3 × n block arrays.[5] In 2020, Goldtiger997 found a construction for 4 × n block arrays.[6] | ||||||
Still lifes / constructability | Finitude of spanning set of synthesis stages | open | 2024 | H. H. P. M. P. Cole and DroneBetter | — | — |
Is there a pair of constants c0,c1, such that for any synthesisable still life, there exists a sequence of constellations (with the last being the still life itself), such that a set of ≤ c0 gliders may be added around the nth member to produce the n+1th, whose effect in each stage is constrained to a c1 × c1 bounding box? Put another way, this implies that there are a finite set of forms that stages in still life syntheses may be constrained to, while still being able to construct any. | ||||||
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.[7] 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,[8] which was improved to ≤ 1728 ≈ 0.6071... on December 16, 2023 by 400spartans,[9] then to ≤ 11762087 ≈ 0.5634... on January 9, 2024 by Keith Amling.[10] | ||||||
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.[11] | ||||||
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.[12] (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.[13] | ||||||
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.[14] | ||||||
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.[15] 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.[16] | ||||||
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),[17] 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.[18] | ||||||
Waves | Orthogonal wave speeds between c/2 and c | open | 2023 | Keith Amling | — | — |
No such speeds are currently known. Keith disproved all other speeds of period ≤ 10, but found that the partials reported for 6c/10 were surprisingly close to being complete, implying that another speed could exist.[19] | ||||||
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
- ↑ Heinrich Koenig (April 20, 2005). "Block Array Constructions". Game of Life News.
- ↑ Martin Grant (December 3, 2015). Re: Synthesising Oscillators (discussion thread) at the ConwayLife.com forums
- ↑ Goldtiger997 (May 6, 2020). Re: Synthesising Oscillators (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
- ↑ Keith Amling (February 13, 2023). Re: Level wave speed limit? (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