Unique father problem: Difference between revisions
→Reductions: technical corrections |
No edit summary |
||
| Line 7: | Line 7: | ||
|bx = 28 | |bx = 28 | ||
|by = 22 | |by = 22 | ||
|symmetry = C2_4 | |||
|synthesis = 0 | |synthesis = 0 | ||
|discoverer = Ilkka Törmä | |discoverer = Ilkka Törmä | ||
| Line 38: | Line 39: | ||
{{gallery bottom}} | {{gallery bottom}} | ||
==Reductions== | == Reductions == | ||
On September 4, {{year|2023}}, [[400spartans]] used a modified version of Törmä and Salo's "gol-agars" search program to find several more self-forcing agar patches, including one that allowed for the creation of a 278-cell unsynthesizable still life.<ref name="message1148473397018370048" /> | On September 4, {{year|2023}}, [[400spartans]] used a modified version of Törmä and Salo's "gol-agars" search program to find several more self-forcing agar patches, including one that allowed for the creation of a 278-cell unsynthesizable still life.<ref name="message1148473397018370048" /> | ||
| Line 74: | Line 75: | ||
}} | }} | ||
==See also== | == See also == | ||
* [[Grandfather problem]] | * [[Grandfather problem]] | ||
* [[Unsynthesizable oscillator 1]] | * [[Unsynthesizable oscillator 1]] | ||
==References== | == References == | ||
<references> | <references> | ||
<ref name="lifelinevol6">{{CiteLifeline | <ref name="lifelinevol6">{{CiteLifeline | ||
| Line 130: | Line 131: | ||
</references> | </references> | ||
==External links== | == External links == | ||
* {{LinkCatagolue|xs374_ck3qp3ck3qp3ck3qp3ck3qp3ckzp96ki6p96ki6p96ki6p96ki6p9zijc95cijc95cijc95cijc95cijz56ojbo56ojbo56ojbo56ojbo56zbdg6mgbdg6mgbdg6mgbdg6mgbdzmq1dc1mq1dc1mq1dc1mq1dc1mqzw3213w3213w3213w3213|patternname=374-cell unconstructible still life}} (by Ilkka Törmä) | * {{LinkCatagolue|xs374_ck3qp3ck3qp3ck3qp3ck3qp3ckzp96ki6p96ki6p96ki6p96ki6p9zijc95cijc95cijc95cijc95cijz56ojbo56ojbo56ojbo56ojbo56zbdg6mgbdg6mgbdg6mgbdg6mgbdzmq1dc1mq1dc1mq1dc1mq1dc1mqzw3213w3213w3213w3213|patternname=374-cell unconstructible still life}} (by Ilkka Törmä) | ||
* {{LinkCatagolue|xs306_wgg0g84s0gg39s0gg08o0kczw1c59cjic59cjic59cjic59aczg08objo65objo65objo65objog4cz11ggm6gdbgm6gdbgm6gdbgm6g08oz3201cd1qm1cd1qm1cd1qm1cd11zw359q3kc3pq3kc3pq3kc3pajozy032011y039cx321|patternname=306-cell unconstructible still life}} (by Oscar Cunningham) | * {{LinkCatagolue|xs306_wgg0g84s0gg39s0gg08o0kczw1c59cjic59cjic59cjic59aczg08objo65objo65objo65objog4cz11ggm6gdbgm6gdbgm6gdbgm6g08oz3201cd1qm1cd1qm1cd1qm1cd11zw359q3kc3pq3kc3pq3kc3pajozy032011y039cx321|patternname=306-cell unconstructible still life}} (by Oscar Cunningham) | ||
* [[Adam P. Goucher]]. [https://cp4space.hatsya.com/2022/01/14/conway-conjecture-settled/ 29-year-old Conway conjecture settled]. January 14, 2022. | * [[Adam P. Goucher]]. [https://cp4space.hatsya.com/2022/01/14/conway-conjecture-settled/ 29-year-old Conway conjecture settled]. January 14, 2022. | ||
[[Category:Synthesis]] | [[Category:Synthesis]] | ||
Revision as of 16:39, 21 August 2024
| Unique father problem | |||||||
| View static image | |||||||
| Pattern type | Problem | ||||||
|---|---|---|---|---|---|---|---|
| Number of cells | 258 | ||||||
| Bounding box | 28 × 22 | ||||||
| Static symmetry | C2_4 | ||||||
| Discovered by | Ilkka Törmä Ville Salo | ||||||
| Year of discovery | 2022 | ||||||
| |||||||
| |||||||
The unique father problem is the following question, posed by John Conway in 1972 in Lifeline Volume 6 with an associated $50 cash prize,[1] along with the grandfather problem:
- Is there a stable configuration whose only father is itself (with some fading junk some distance away not being counted)?
The problem was answered positively by Ilkka Törmä and Ville Salo on January 13, 2022, with a 22 × 28 region that must appear in all of its predecessors. This is shown in the infobox to the right, with the gray cells indicating the boundary of this region. This can be stabilized to form a 26 × 32 still life consisting of blocks and snakes with population 374, which cannot be constructed from scratch by any means.[2] Dani reduced this still life by 40 cells within the same bounding box.[3] It was further reduced by Oscar Cunningham to its provably minimum population of 306 but with a larger bounding box.[4] In particular, there is no glider synthesis for any still life that contains this region.
| 26 × 32 unconstructible still life with population 334 (minimum bounding box) (click above to open LifeViewer) RLE: here Plaintext: here |
| 34 × 28 unconstructible still life with population 306 (minimum population) (click above to open LifeViewer) RLE: here Plaintext: here |
Reductions
On September 4, 2023, 400spartans used a modified version of Törmä and Salo's "gol-agars" search program to find several more self-forcing agar patches, including one that allowed for the creation of a 278-cell unsynthesizable still life.[5]
| 21 × 6 self-forcing agar found by 400spartans, and 23 × 20 self-forcing patch made from the agar (click above to open LifeViewer) RLE: here Plaintext: here |
| 31 × 28 unconstructible still life, stabilizing the 23 × 20 self-forcing patch (click above to open LifeViewer) RLE: here Plaintext: here |
On March 12, 2024, 400spartans reduced this once more to a patch of 389 specified cells with a population-236 stabilisation.[6] The self-forcing region was found as a finite subset of a self-forcing agar with the constraint that all live cells in the agar have three living neighbours, and all dead cells have four. All known self-forcing still life patches are derived from agars with this property.[7]
| A population-236 unconstructible still life displayed in LifeHistory. The self-forcing patch is highlighted, with live cells being white and dead cells being red. (click above to open LifeViewer) |
See also
References
- ↑ Robert Wainwright (October 1972). Lifeline, vol 6, p. 1.
- ↑ Ilkka Törmä (January 13, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ dani (January 14, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ Oscar Cunningham (January 14, 2022). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ mu.sicman (September 4, 2023). Message in #cgol on the Conwaylife Lounge Discord server
- ↑ 400spartans (March 12, 2024). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ 400spartans (March 12, 2024). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
External links
- 374-cell unconstructible still life at Adam P. Goucher's Catagolue (by Ilkka Törmä)
- 306-cell unconstructible still life at Adam P. Goucher's Catagolue (by Oscar Cunningham)
- Adam P. Goucher. 29-year-old Conway conjecture settled. January 14, 2022.