Difference between revisions of "Grandfather problem"

From LifeWiki
Jump to navigation Jump to search
(Use {{OEIS}} template)
m
(16 intermediate revisions by 4 users not shown)
Line 2: Line 2:
|name        = Grandfather problem
|name        = Grandfather problem
|pname        = grandfatherproblemsolved
|pname        = grandfatherproblemsolved
|type        = Problem
|c            = 298
|c            = 298
|bx          = 24
|bx          = 24
|by          = 23
|by          = 23
|synthesis    = 0
|discoverer  = mtve
|discoverer  = mtve
|discoveryear = 2016
|discoveryear = 2016
|nofile      = 1
|plaintext    = 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="lifelinevol6" /> 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]]?''


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" />  
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 "[[User:Mtve|mtve]]" presented such a pattern.<ref name="mtve1" />  


==Generation==
==Generation==
The pattern was found with [[Mark Owen]]'s picosat, using an algorithm similar to the one employed by [[Nicolay Beluchenko]]'s {{OEIS|A196447}}:<ref name="mtve2" />
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]]'s {{OEIS|A196447}}:<ref name="mtve2" />


# Try setting the next cell on and off;
# Try setting the next cell on and off;
Line 25: Line 28:


==Verification==
==Verification==
mtve's discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[WLS|JLS]], using the following steps<ref name="sokwe" />:
"mtve"'s discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[JLS]], using the following steps<ref name="sokwe" />:


# 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.
Line 31: Line 34:


==Optimization==
==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" />.
It is 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==
==Next levels==
"A father, grandfather, but no grand-grand-father" pattern also has been constructed by the same method<ref name="mtve4" />.
"A father and grandfather, but no great-grandfather" pattern<ref name="mtve4" />, and a "father, grandfather and great-grandfather, but no great-great-grandfather" pattern<ref name="mtve5" />, have also been constructed by the same method.


No further levels are found yet, but they almost probably 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
Line 77: Line 88:
|date      = June 2016
|date      = June 2016
|accessdate = July 8, 2016
|accessdate = July 8, 2016
}}</ref>
<ref name="mtve5">{{cite web
|url        = http://frox25.no-ip.org/~mtve/wiki/GardenOfEden4G.html
|author    = mtve
|title      = Garden Of Eden 4G
|date      = December 12, 2016
|accessdate = December 14, 2016
}}</ref>
}}</ref>
</references>
</references>
[[Category:Patterns discovered by pseudonymous users]]

Revision as of 23:40, 29 March 2019

Grandfather problem
x = 24, y = 23, rule = B3/S23 8ob5ob4ob3o$obo2b2o2b3o2b4ob2o2bo$2obob4ob4ob2obo2b3o$3obobobobo2bob3o b3o$ob2o6bo2b5o3b2o$bobob9obobo$obob2o4bo2bob4obo$obobo2b3ob3ob2o$4o2b 2ob3ob4o4bo$4ob6o2bo6bo$obob3ob2ob2ob3ob2o3bo$ob3obob6ob4obo$2b6obob2o 2b3o$2o2bobobob4o$b4ob4o2b6o4b2o$obobobo2b2ob2o2b2o2b3o$o3b2ob2o2b3ob 2o3bo$2ob2o4b2o4b3o$3obob5o3b4obobobo$ob4o2b2o3bobo4bo2bo$2ob2o4b2o3bo 5b2obo$b4obo2bobo4bob2o2b2o$3o3b2ob3o2bobo6bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]]
View static image
Pattern type Problem
Number of cells 298
Bounding box 24 × 23
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 remained open until May 2016, when "mtve" presented such a pattern.[2]

Generation

The pattern was found with the PicoSAT SAT solver, using an algorithm similar to the one employed by Nicolay Beluchenko's OEISicon light 11px.png A196447:[3]

  1. Try setting the next cell on and off;
  2. Skip first level gardens of eden;
  3. 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]:

  1. 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.
  2. 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

  1. ↑ Robert Wainwright (October 1972). Lifeline, vol 6, p. 1.
  2. ↑ mtve (May 5, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
  3. ↑ mtve (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
  4. ↑ Matthias Merzenich (Sokwe) (May 6, 2016). "Re: Thread for your unsure discoveries". ConwayLife.com forums. Retrieved on June 22, 2016.
  5. ↑ mtve (June 2016). "Garden Of Eden 2G". Retrieved on July 8, 2016.
  6. ↑ mtve (June 2016). "Garden Of Eden 3G". Retrieved on July 8, 2016.
  7. ↑ mtve (December 12, 2016). "Garden Of Eden 4G". Retrieved on December 14, 2016.
Retrieved from "https://conwaylife.com/w/index.php?title=Grandfather_problem&oldid=59561"