Grandfather problem: Difference between revisions
Jump to navigation
Jump to search
Apple Bottom (talk | contribs) New entry, mostly about mtve's pattern. |
information about more 2G patterns and also 3G |
||
| Line 13: | Line 13: | ||
:''Is there a configuration which has a father but no grandfather?'' | :''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 | Although a 50$ cash prize was offered by Conway, the problem remained open until May 2016, when [[User:Mtve|Mtve]] presented such a pattern.<ref name="mtve1" /> | ||
==Generation== | ==Generation== | ||
| Line 29: | Line 29: | ||
# 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. | # 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". | # 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's possible to reduce the size of this pattern by removing some cells, and also some other patterns with the same property exist<ref name="mtve3" />. | |||
==Next levels== | |||
"A father, grandfather, but no grand-grand-father" pattern also has been constructed by the same method<ref name="mtve4" />. | |||
No further levels are found yet, but they almost probably do exist. | |||
==References== | ==References== | ||
| Line 55: | Line 63: | ||
|date = May 6, 2016 | |date = May 6, 2016 | ||
|accessdate = June 22, 2016 | |accessdate = June 22, 2016 | ||
}}</ref> | |||
<ref name="mtve3">{{cite web | |||
|url = http://frox25.no-ip.org/~mtve/wiki/GardenOfEden2G.html | |||
|author = mtve | |||
|title = Garden Of Eden 2G | |||
|date = June 2016 | |||
|accessdate = July 8, 2016 | |||
}}</ref> | |||
<ref name="mtve4">{{cite web | |||
|url = http://frox25.no-ip.org/~mtve/wiki/GardenOfEden3G.html | |||
|author = mtve | |||
|title = Garden Of Eden 3G | |||
|date = June 2016 | |||
|accessdate = July 8, 2016 | |||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
Revision as of 19:14, 8 July 2016
| Grandfather problem | |||||
| View static image | |||||
| Pattern type | Miscellaneous | ||||
|---|---|---|---|---|---|
| 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:
- 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.[1]
Generation
The pattern was found with Mark Owen's picosat, using an algorithm similar to the one employed by Nicolay Beluchenko's OEIS sequence A196447:[2]
- 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[3]:
- 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's possible to reduce the size of this pattern by removing some cells, and also some other patterns with the same property exist[4].
Next levels
"A father, grandfather, but no grand-grand-father" pattern also has been constructed by the same method[5].
No further levels are found yet, but they almost probably do exist.
References
- ↑ 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.