Difference between revisions of "Problem"
Jump to navigation
Jump to search
Apple Bottom (talk | contribs) (→List of problems: 1-cell thick infinite growth) |
(red link removal and link clean-up) |
||
(7 intermediate revisions by 4 users not shown) | |||
Line 4: | Line 4: | ||
Unsolved problems can be subdivided into several basic categories: | Unsolved problems can be subdivided into several basic categories: | ||
* ''Periods'': Do | * ''Periods'': Do [[oscillator]]s, [[spaceship]]s, [[gun]]s or [[puffer]]s 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. | * ''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 | * ''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 [http://conwaylife.com/forums/viewtopic.php?f=2&t=1641&start=50#p44985 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. | * ''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]]. | * ''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. | * ''Temporal minimization problems:'' As above, but concentrating on speed rather than size. | ||
==List of problems== | ==List of problems== | ||
Open and previously open problems include: | Open and previously open problems include: | ||
{| class="sortable wikitable" style="margin-left: auto; margin-right: auto" | {| class="sortable wikitable" style="margin-left: auto; margin-right: auto" | ||
|- | |- | ||
Line 25: | Line 24: | ||
! class="unsortable" colspan="6" | Description | ! class="unsortable" colspan="6" | Description | ||
|- | |- | ||
| | | one cell thick infinite growth || solved || ? || [[Nick Gotts]] || 1998 || [[Stephen Silver]] | ||
|- class="expand-child" | |- class="expand-child" | ||
| colspan="6" | The question “''is there a [[ | | colspan="6" | The question “''is there a [[one-cell-thick pattern]] exhibiting [[infinite growth]]?''” [[1×N quadratic growth|was answered in the affirmative]]. | ||
|- | |- | ||
| [[Coolout Conjecture]] || solved || data-sort-value=1992 | <1992 || [[Richard Schroeppel]] || 2001 || [[Richard Schroeppel]] | | [[Coolout Conjecture]] || solved || data-sort-value=1992 | <1992 || [[Richard Schroeppel]] || 2001 || [[Richard Schroeppel]] | ||
Line 35: | Line 34: | ||
| [[Garden of Eden]] || solved || ? || ? || data-sort-value=1970 | <1970 || [[Edward Moore]] | | [[Garden of Eden]] || solved || ? || ? || data-sort-value=1970 | <1970 || [[Edward Moore]] | ||
|- class="expand-child" | |- class="expand-child" | ||
| colspan="6" | The existence of a | | colspan="6" | 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]] | | [[Grandfather problem]] || solved || 1972 || [[John Conway]] || 2016 || [[mtve]] | ||
Line 43: | Line 42: | ||
| [[Omniperiodicity]] || '''open''' || data-sort-value=0 | ? || ? || data-sort-value=0 | — || — | | [[Omniperiodicity]] || '''open''' || data-sort-value=0 | ? || ? || data-sort-value=0 | — || — | ||
|- class="expand-child" | |- class="expand-child" | ||
| colspan="6" | The question “''do | | colspan="6" | The question “''do oscillators of all periods exist?''” remains open for Conway's Game of Life; no oscillators are known for period 19, 38 and 41, and no non-[[trivial]] oscillators are known for period 34. | ||
|- | |- | ||
| [[Replicator]]s || solved || data-sort-value=0 | ? || ? || 1982 || [[Elwyn R. Berlekamp]], [[John Conway]], [[Richard K. Guy]] | | [[Replicator]]s || solved || data-sort-value=0 | ? || ? || 1982 || [[Elwyn R. Berlekamp]], [[John Conway]], [[Richard K. Guy]] | ||
|- class="expand-child" | |- class="expand-child" | ||
| colspan="6" | The question “''do | | colspan="6" | The question “''do replicators exist in Conway's Game of Life?''” was answered in the affirmative.<ref name="winningways" /> | ||
|- | |||
| Still life finitization problem || solved || data-sort-value=0 | ? || [[Dean Hickerson]] || 2019 || [[Martin Grant]] | |||
|- class="expand-child" | |||
| colspan="6" | 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?''" was answered in the negative.<ref name="post86644" /> | |||
|- | |- | ||
| [[Unique father problem]] || '''open''' || 1972 || [[John Conway]] || data-sort-value=0 | — || — | | [[Unique father problem]] || '''open''' || 1972 || [[John Conway]] || data-sort-value=0 | — || — | ||
Line 55: | Line 58: | ||
| [[Universal computer]] / [[Universal constructor]] || solved || ? || [[John Conway]] || 1982 || [[Elwyn R. Berlekamp]], [[John Conway]], [[Richard K. Guy]] | | [[Universal computer]] / [[Universal constructor]] || solved || ? || [[John Conway]] || 1982 || [[Elwyn R. Berlekamp]], [[John Conway]], [[Richard K. Guy]] | ||
|- class="expand-child" | |- class="expand-child" | ||
| colspan="6" | The question “''does | | colspan="6" | The question “''does Conway's Game of Life support universal computation and universal construction?''” was answered in the affirmative.<ref name="winningways" /> | ||
|} | |} | ||
Line 72: | Line 75: | ||
|title = Winning Ways for Your Mathematical Plays | |title = Winning Ways for Your Mathematical Plays | ||
|pages = 927-961 | |pages = 927-961 | ||
}}</ref> | |||
<ref name="post86644">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Unproven conjectures | |||
|p = 86644 | |||
|author = Martin Grant | |||
|date = December 28, 2019 | |||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
==External links== | |||
{{LinkForumThread|f=7|t=3180|title=Unproven conjectures}} |
Revision as of 13:45, 12 May 2020
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 |
---|---|---|---|---|---|
Description | |||||
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. | |||||
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, 38 and 41, and no non-trivial oscillators are known for period 34. | |||||
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 | solved | ? | Dean Hickerson | 2019 | Martin Grant |
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?" was answered in the negative.[2] | |||||
Unique father problem | open | 1972 | John Conway | — | — |
The question “is there a stable configuration whose only father is itself?” remains open. | |||||
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] |
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
- ↑ Martin Grant (December 28, 2019). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
External links
- Unproven conjectures (discussion thread) at the ConwayLife.com forums