Grandfather problem: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
← Older edit
Haycat2009 (talk | contribs)
Trusted users
4,258 edits
The content about grandfatherless moves here, and ref format
m →Optimization: Remove redundant
 
(21 intermediate revisions by 9 users not shown)
Line 6: Line 6:
|bx          = 24
|bx          = 24
|by          = 23
|by          = 23
|symmetry    = C1
|synthesis    = 0
|synthesis    = 0
|discoverer  = mtve
|discoverer  = mtve
Line 11: Line 12:
|plaintext    = true
|plaintext    = true
|rle          = true
|rle          = true
|viewerconfig = #C [[ ZOOM 16 WIDTH 500 HEIGHT 500 ]]
}}
}}
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]]:
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]]:
Line 16: Line 18:
:''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 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" />
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" /> {{POTY|name=This pattern|year=2016|rank=3|behind=the [[copperhead]] and the [[Caterloopillar]]s}}


==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]] to discover {{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]] to discover {{OEIS|A196447}}:<ref name="mtve2" />


# Try setting the next cell on and off;
# Try setting the next cell on and off;
# Skip first level [[garden of eden|gardens of eden]];
# 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.
# 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.
The final configuration has a total of 17920 parents, but no grandparents.


==Verification==
== Verification ==
"mtve"'s discovery was confirmed to solve the grandfather problem by [[Matthias Merzenich]] with [[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.
# 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==
== 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<ref name="mtve3" />.
It is possible to reduce the size of this pattern by removing some cells, and other patterns with the same property exist.<ref name="mtve3" />


==Next levels==
{{EmbedViewer
"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.
|pname        = grandfatherproblem22x22
|position    = center
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 8 ]]
|caption      = {{times|22|22}} grandfatherless pattern by mtve<ref name="mtve3" />  
|style        = width:300px;
}}


No further levels have been found yet, but they almost certainly do exist.
== Next levels ==
"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.


==References==
{|style="margin:auto;width:300px;"
|{{EmbedViewer
|pname        = greatgrandfatherproblem
|position    = center
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 8 ]]
|caption      = Pattern with a father and grandfather, but no great-grandfather, by mtve in 2016<ref name="mtve4" />
}}
|-
|{{EmbedViewer
|pname        = greatgreatgrandfatherproblem
|position    = center
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 8 ]]
|caption      = Pattern with a father, grandfather and great-grandfather, but no great-great-grandfather, by mtve in 2016<ref name="mtve5" />
}}
|}
 
On January 6, {{year|2022}}, [[Ilkka Törmä]] and [[Ville Salo]] solved a generalized version of the grandfather problem, proving that for every natural number n, there exists a pattern that has an n-tick predecessor but not an (n+1)-tick predecessor.<ref name="post139854" /> Furthermore, this pattern will fit in a box of diameter O(sqrt(log(n))).<ref name="post140273" />
 
== References ==
<references>
<references>
<ref name="lifelinevol6">{{CiteLifeline
<ref name="lifelinevol6">{{CiteLifeline
|vol  = 6
|vol  = 6
|date  = October 1972
|pages = p. 1
|pages = p. 1
}}</Ref>
}}</Ref>
Line 54: Line 79:
|author = mtve
|author = mtve
|date    = May 5, 2016
|date    = May 5, 2016
}}</ref>
<ref name="post44028">{{LinkForumThread
|format = ref
|title  = Pattern of the Year 2016 (Results)
|p      = 44028
|author = Alexey Nigin
|date  = June 3, 2017
}}</ref>
}}</ref>
<ref name="mtve2">{{LinkForumThread
<ref name="mtve2">{{LinkForumThread
Line 96: Line 114:
|date      = December 12, 2016
|date      = December 12, 2016
|accessdate = December 14, 2016
|accessdate = December 14, 2016
}}</ref>
<ref name="post139854">{{LinkForumThread
|format    = ref
|title      = Re: Unproven conjectures
|p          = 139854
|author    = Ilkka Törmä
|date      = January 6, 2022
}}</ref>
<ref name="post140273">{{LinkForumThread
|format    = ref
|title      = Re: Unproven conjectures
|p          = 140273
|author    = Adam P. Goucher
|date      = January 13, 2022
}}</ref>
}}</ref>
</references>
</references>


==External links==
== External links ==
{{LinkLexicon|filename=lex_g.htm#grandfatherless|patternname=Grandfatherless}}
{{LinkLexicon|filename=lex_g.htm#grandfatherless|patternname=Grandfatherless}}


[[Category:Patterns discovered by pseudonymous users]]
[[Category:Patterns discovered by pseudonymous users]]

Latest revision as of 08:43, 3 October 2024

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 ]] #C [[ ZOOM 16 WIDTH 500 HEIGHT 500 ]]
View static image
Pattern type Problem
Number of cells 298
Bounding box 24 × 23
Static symmetry C1
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]

  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:[5]

  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 other patterns with the same property exist.[6]

x = 22, y = 22, rule = B3/S23 4o11bobob3o$2o2b2ob3o5bo3bobo$2obob4o2bobo3b3obo$obob4ob3o3bob2obo$ob 2ob2o4bob9o$ob3o2b4ob8obo$2ob3ob4o2bob3ob2o$3o2b3obobobobob2ob2o$2ob3o 4bo2bo2bobo2bo$obo2bobob3obo3bo3bo$2ob4obob7ob2o$bobobo3b3obobob3obo$ 7obobo4bo2b3o$b5obo2b8o$2bob2ob5o2bobob2o$o2b2obo2b5o2b3obo$3bob3ob3o 3b3obo$2b7o2b6obo$2b2ob2o3bob4ob3obo$o4bob6ob3obobo$obob3o3bobo2b3obob o$b2o3bob2o2bob2obo3bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ZOOM 8 ]]
22 × 22 grandfatherless pattern by mtve[6]
(click above to open LifeViewer)
RLE: here Plaintext: here

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.

x = 29, y = 29, rule = B3/S23 3obob4obobo4bo2bo2bo3bo$3obob2ob2ob2o5b3obobobo$2bo6b2obo2b2o2b3o4b3o$ 4b3o2bobo2bo2b4o2bob3o$bo2b3o11bobob3ob3o$5o2b2ob3o5bo3bob2obo$2bobobo b4o2bobo3b3ob3o$3bobob4ob3o3bob2obob2o$2bo2b2ob2o4bob9o2b2o$2bo2b3o2b 4ob8ob2obo$4bob3ob4o2bob3ob2o2b3o$bo2b2o2b3obobobobob2ob4obo$3b2ob3o4b o2bo2bobo2bo$o2bobo2bobob3obo3bo3bo2b2o$4bob4obob7ob2o2bo2bo$bo2bobobo 3b3obobob3ob5o$2b8obobo4bo2b3ob3o$o3b5obo2b8o4b2obo$o4bob2ob5o2bobob2o 2b3o$ob2o2b2obo2b5o2b3obo$o5bob3ob3o3b3obo2b2o$2bo2b7o2b6obo6bo$2o3b2o b2o3bob4ob3obobobo$b3o4bob6ob3obobo3b2o$2b2obob3o3bobo2b3obob2ob2o$2bo b2o3bob2o2bob2obo3b2ob2o$7o5b5obo2bo2bob3o$7ob2ob2o4b2o3bob5o$bob2ob2o bob4o3bo4b2ob3o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ZOOM 8 ]]
Pattern with a father and grandfather, but no great-grandfather, by mtve in 2016[7]
(click above to open LifeViewer)
RLE: here Plaintext: here
x = 31, y = 32, rule = B3/S23 3o3b2o5b2obob2o4b3obobo$2b4obo4bo2b2o2b3o6b2o$b2o2bobo3b2obob2o2b2ob3o bobo$b5ob2o2bo2bob3o2bo4b5o$o3b4ob3o2bo2bo3bo2bo5bo$3b3obo2bobobobobo 3bob3o2b2o$3b7obobob8o4bobo$b2ob4o2bo2b4o3b5obo3bo$5b2o2b4ob6ob3o2bob 2o$obobo3bob2ob7ob5o3bo$bo7b3ob2ob3o2bo2bob2o2bo$5bobo2bobob2ob4obobo 3bo$o2bobo2b4obo2bobob3o4bobo$4ob2obob4obobo2bo2bobo2b2o$2b3o2bo2bobob 3ob6ob2obo$o2bobobobobob3ob4o4bobo$2o3b8ob5o6bobob2o$2bob6obob2ob6obob o2b2o$b6o4b2ob3o2bob3ob2o$o2bobo2b2o2b2o2bob3ob2ob2o2b2o$2bo5b3obobob 2obobo2bo4b2o$2o4bo4bobob2ob3o6bo$7obob6ob6o3bob2o$5o2b3ob2o2b2o2bo2b 4ob2obo$2b2ob4o4b3ob2o2b2ob3o$3bo2bobo2b2o5bo2b6o3bo$3b2o4bobob7o2b2ob obob2o$4o2bo2bo3bo2b5obo2b6o$o3b2o2b2o4bo2b4obobo2b2obo$bo3b6o3bob4obo 5b2o$2o4bobo5b2o2bobobobo2b3o$15ob3o7b2o2bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ZOOM 8 ]]
Pattern with a father, grandfather and great-grandfather, but no great-great-grandfather, by mtve in 2016[8]
(click above to open LifeViewer)
RLE: here Plaintext: here

On January 6, 2022, Ilkka Törmä and Ville Salo solved a generalized version of the grandfather problem, proving that for every natural number n, there exists a pattern that has an n-tick predecessor but not an (n+1)-tick predecessor.[9] Furthermore, this pattern will fit in a box of diameter O(sqrt(log(n))).[10]

References

  1. ↑ Robert Wainwright (October 1972). Lifeline, vol 6, p. 1.
  2. ↑ mtve (May 5, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
  3. ↑ Alexey Nigin (June 3, 2017). Pattern of the Year 2016 (Results) (discussion thread) at the ConwayLife.com forums
  4. ↑ mtve (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
  5. ↑ Matthias Merzenich (May 6, 2016). Re: Thread for your unsure discoveries (discussion thread) at the ConwayLife.com forums
  6. ↑ 6.0 6.1 mtve (June 2016). "Garden Of Eden 2G". Retrieved on July 8, 2016.
  7. ↑ 7.0 7.1 mtve (June 2016). "Garden Of Eden 3G". Retrieved on July 8, 2016.
  8. ↑ 8.0 8.1 mtve (December 12, 2016). "Garden Of Eden 4G". Retrieved on December 14, 2016.
  9. ↑ Ilkka Törmä (January 6, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
  10. ↑ Adam P. Goucher (January 13, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
Retrieved from "https://conwaylife.com/w/index.php?title=Grandfather_problem&oldid=156053"