Grandfather problem: Difference between revisions
Jump to navigation
Jump to search
third place in POTY 2016 |
The content about grandfatherless moves here, and ref format |
||
| Line 16: | Line 16: | ||
:''Is there a configuration which has a father but no [[grandfather]]?'' | :''Is there a configuration which has a father but no [[grandfather]]?'' | ||
Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem remained open until May 2016, when "[[ | Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem of a '''grandfatherless''' pattern remained open until May {{year|2016}}, when "[[mtve]]" presented such a pattern.<ref name="mtve1" /> This pattern ranked third place in the [[Pattern of the Year]] 2016 competition on the [[ConwayLife.com]] forums, behind the [[copperhead]] and the [[caterloopillar]]s.<ref name="post44028" /> | ||
==Generation== | ==Generation== | ||
The pattern was found with the [http://fmv.jku.at/picosat/ PicoSAT] SAT solver, using an algorithm similar to the one employed by [[Nicolay Beluchenko]] | The pattern was found with the [http://fmv.jku.at/picosat/ PicoSAT] SAT solver, using an algorithm similar to the one employed by [[Nicolay Beluchenko]] to discover {{OEIS|A196447}}:<ref name="mtve2" /> | ||
# Try setting the next cell on and off; | # Try setting the next cell on and off; | ||
| Line 40: | Line 40: | ||
No further levels have been found yet, but they almost certainly do exist. | No further levels have been found yet, but they almost certainly do exist. | ||
==References== | ==References== | ||
| Line 51: | Line 48: | ||
|pages = p. 1 | |pages = p. 1 | ||
}}</Ref> | }}</Ref> | ||
<ref name="mtve1">{{ | <ref name="mtve1">{{LinkForumThread | ||
| | |format = ref | ||
|title = Re: Thread for your unsure discoveries | |title = Re: Thread for your unsure discoveries | ||
| | |p = 30646 | ||
|date | |author = mtve | ||
|date = May 5, 2016 | |||
}}</ref> | }}</ref> | ||
<ref name="post44028">{{LinkForumThread | <ref name="post44028">{{LinkForumThread | ||
| Line 66: | Line 62: | ||
|date = June 3, 2017 | |date = June 3, 2017 | ||
}}</ref> | }}</ref> | ||
<ref name="mtve2">{{ | <ref name="mtve2">{{LinkForumThread | ||
| | |format = ref | ||
|title = Re: Thread for your unsure discoveries | |||
|p = 30667 | |||
|author = mtve | |author = mtve | ||
|date = May 6, 2016 | |date = May 6, 2016 | ||
}}</ref> | }}</ref> | ||
<ref name="sokwe">{{ | <ref name="sokwe">{{LinkForumThread | ||
| | |format = ref | ||
|title = Re: Thread for your unsure discoveries | |title = Re: Thread for your unsure discoveries | ||
| | |p = 30694 | ||
|author = Matthias Merzenich | |||
|date = May 6, 2016 | |date = May 6, 2016 | ||
}}</ref> | }}</ref> | ||
<ref name="mtve3">{{cite web | <ref name="mtve3">{{cite web | ||
| Line 104: | Line 98: | ||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
==External links== | |||
{{LinkLexicon|filename=lex_g.htm#grandfatherless|patternname=Grandfatherless}} | |||
[[Category:Patterns discovered by pseudonymous users]] | [[Category:Patterns discovered by pseudonymous users]] | ||
Revision as of 16:45, 30 May 2020
| Grandfather problem | |||||||
| View static image | |||||||
| Pattern type | Problem | ||||||
|---|---|---|---|---|---|---|---|
| Number of cells | 298 | ||||||
| Bounding box | 24 × 23 | ||||||
| Static symmetry | Unspecified | ||||||
| Discovered by | mtve | ||||||
| Year of discovery | 2016 | ||||||
| |||||||
| |||||||
The grandfather problem is the following question, posed by John Conway in 1972 in Lifeline Volume 6,[1] along with the unique father problem:
- Is there a configuration which has a father but no grandfather?
Conway offered a $50 cash prize to "the first person to settle the grandfather problem either way". But the problem of a grandfatherless pattern remained open until May 2016, when "mtve" presented such a pattern.[2] This pattern ranked third place in the Pattern of the Year 2016 competition on the ConwayLife.com forums, behind the copperhead and the caterloopillars.[3]
Generation
The pattern was found with the PicoSAT SAT solver, using an algorithm similar to the one employed by Nicolay Beluchenko to discover 
A196447:[4]
- Try setting the next cell on and off;
- Skip first level gardens of eden;
- Choose the minimum number of grandparents, where "minimum number" is not the exact number but a minimal distance between first and last.
The final configuration has a total of 17920 parents, but no grandparents.
Verification
"mtve"'s discovery was confirmed to solve the grandfather problem by Matthias Merzenich with JLS, using the following steps[5]:
- Run a search to find all 1-generation predecessors of mtve's pattern. Copy the cells that had the same setting in all solutions to the pattern.
- Mark all of unset cells with "X", increase the period by 1 and shift the pattern to the future by 1 generation. Set the outer cells to "X" in generation 0 and run another search, which eventually gives "Search finished: 0 solutions found".
Optimization
It is possible to reduce the size of this pattern by removing some cells, and also some other patterns with the same property exist[6].
Next levels
"A father and grandfather, but no great-grandfather" pattern[7], and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern[8], have also been constructed by the same method.
No further levels have been found yet, but they almost certainly do exist.
References
- ↑ Robert Wainwright (October 1972). Lifeline, vol 6, p. 1.
- ↑ mtve (May 5, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
- ↑ Alexey Nigin (June 3, 2017). Pattern of the Year 2016 (Results) (discussion thread) at the ConwayLife.com forums
- ↑ mtve (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
- ↑ Matthias Merzenich (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
- ↑ mtve (June 2016). "Garden Of Eden 2G". Retrieved on July 8, 2016.
- ↑ mtve (June 2016). "Garden Of Eden 3G". Retrieved on July 8, 2016.
- ↑ mtve (December 12, 2016). "Garden Of Eden 4G". Retrieved on December 14, 2016.
External links
- Grandfatherless at the Life Lexicon