Grandfather problem/Snippet: Difference between revisions
Jump to navigation
Jump to search
snippet for 'grandfather problem' |
Added note on generalized grandfather solution |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
<noinclude>{{Snippet}}</noinclude>[[Image:Grandfatherproblemsolved_small.png|right]] | |||
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]]: | ||
:''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 [[User:Mtve|mtve]] presented such a pattern -- and, soon after that, a pattern with a grandfather but no great-grandfather, and another pattern with a great-grandfather but no great-great-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 [[User:Mtve|mtve]] presented such a pattern -- and, soon after that, a pattern with a grandfather but no great-grandfather, and another pattern with a great-grandfather but no great-great-grandfather. 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. | ||
Latest revision as of 06:22, 13 January 2025
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?
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 -- and, soon after that, a pattern with a grandfather but no great-grandfather, and another pattern with a great-grandfather but no great-great-grandfather. 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.