Problem: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
→List of problems: Universal computation / construction
Line 27: Line 27:
| [[Coolout Conjecture]] || '''solved''' || <1992 || [[Richard Schroeppel]] || 2001 || [[Richard Schroeppel]]
| [[Coolout Conjecture]] || '''solved''' || <1992 || [[Richard Schroeppel]] || 2001 || [[Richard Schroeppel]]
|- class="expand-child"  
|- class="expand-child"  
| colspan="6" | 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 not affirmative.
| colspan="6" | 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.
|-
|-
| [[Grandfather problem]] || '''solved''' || 1972 || [[John Conway]] || 2016 || [[mtve]]
| [[Grandfather problem]] || '''solved''' || 1972 || [[John Conway]] || 2016 || [[mtve]]
|- class="expand-child"  
|- class="expand-child"  
| colspan="6" | The question ''is there a configuration which has a father but no grandfather?'' was answered in the affirmative.
| colspan="6" | The question “''is there a configuration which has a father but no grandfather?''” was answered in the affirmative.
|-
| [[Omniperiodicity]] || open || ? || ? || ||
|- class="expand-child"
| colspan="6" | The question “''do [[oscillator]]s of all [[period]]s exist?''” remains open for [[Conway's Game of Life|Life]]; no oscillators are known are [[periods]] 19, 23, 38 and 41, and no non-trivial oscillators are known for period 34.
|-
|-
| [[Unique father problem]] || open || 1972 || [[John Conway]] || ||  
| [[Unique father problem]] || open || 1972 || [[John Conway]] || ||  
|- class="expand-child"
|- class="expand-child"
| colspan="6" | The question ''Is there a stable configuration whose only father is itself?'' remains open.
| colspan="6" | The question “''is there a stable configuration whose only father is itself?''” remains open.
|-
|-
| [[Omniperiodicity]] || open || ? || ? || ||
| [[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 ''do [[oscillator]]s of all [[period]]s exist?'' remains open for [[Conway's Game of Life|Life]]; the only periods for which no oscillators are known are 19, 23, 38 and 41, and if individual cells oscillating at a set period are concerned, 34.
| colspan="6" | The question “''does [[Conway's Game of Life|Life]] support [[universal computation]] and [[universal construction]]?''” was answered in the affirmative.<ref name="winningways" />
|}
|}

Revision as of 18:59, 25 August 2017

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 adjustable-speed diagonal spaceship has been built to date, but a workable blueprint is available, and no 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
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.
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 Life; no oscillators are known are periods 19, 23, 38 and 41, and no non-trivial oscillators are known for period 34.
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 Life support universal computation and universal construction?” was answered in the affirmative.[1]
  1. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named winningways