Grandfather problem: Difference between revisions
Apple Bottom (talk | contribs) mNo edit summary |
Apple Bottom (talk | contribs) Also see, etc. |
||
| Line 10: | Line 10: | ||
|rle = true | |rle = true | ||
}} | }} | ||
The '''grandfather problem''' is the following question, posed by [[John Conway]] in 1972 in [[Lifeline Volume 6]]: | The '''grandfather problem''' is the following question, posed by [[John Conway]] in 1972 in [[Lifeline Volume 6]],<ref name="lifelinevol06" /> along with the [[unique father problem]]: | ||
:''Is there a configuration which has a father but no grandfather?'' | :''Is there a configuration which has a father but no grandfather?'' | ||
| Line 38: | Line 38: | ||
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. | ||
==Also see== | |||
* [[Unique father problem]] | |||
==References== | ==References== | ||
<references> | <references> | ||
<ref name="lifelinevol6">{{CiteLifeline | |||
|vol = 6 | |||
|date = October 1972 | |||
|pages = p. 1 | |||
}}</Ref> | |||
<ref name="mtve1">{{cite web | <ref name="mtve1">{{cite web | ||
|url = http://conwaylife.com/forums/viewtopic.php?p=30646#p30646 | |url = http://conwaylife.com/forums/viewtopic.php?p=30646#p30646 | ||
Revision as of 10:32, 25 August 2017
| 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?
Although a 50$ cash prize was offered by Conway, the problem remained open until May 2016, when mtve presented such a pattern.[2]
Generation
The pattern was found with Mark Owen's picosat, using an algorithm similar to the one employed by Nicolay Beluchenko's 
A196447:[3]
- 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[4]:
- 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[5].
Next levels
"A father and grandfather, but no great-grandfather" pattern[6], and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern[7], have also been constructed by the same method.
No further levels have been found yet, but they almost certainly do exist.
Also see
References
- ↑ Cite error: Invalid
<ref>tag; no text was provided for refs namedlifelinevol06 - ↑ mtve (May 5, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
- ↑ mtve (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
- ↑ Matthias Merzenich (Sokwe) (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
- ↑ 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.
Cite error: <ref> tag with name "lifelinevol6" defined in <references> is not used in prior text.