Unique father problem: Difference between revisions
No edit summary |
adjust minimal patch for self-forcing 154 live cells -- 252 specified cells are needed rather than 251 |
||
| Line 60: | Line 60: | ||
On March 12, {{year|2024}}, [[400spartans]] reduced this once more to a patch of 389 specified cells with a population-236 stabilisation.<ref name="p180119" /> 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 have related infinite agars with this property.<ref name="p180133" /> | On March 12, {{year|2024}}, [[400spartans]] reduced this once more to a patch of 389 specified cells with a population-236 stabilisation.<ref name="p180119" /> 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 have related infinite agars with this property.<ref name="p180133" /> | ||
On September 2, {{year|2024}}, 400spartans found a population-184 stabilization of a self-forcing patch with 283 specified cells.<ref name="p193366" /> The discovery process for the new unconstructible still life involved the use of a hybrid tool incorporating ideas from Törmä and Salo's gol-agars program and [[mtve]]'s grandfatherless pattern algorithm, which builds up a pattern by adding overlapping 3x3 squares while keeping track of the number of predecessors within the same bounding box. A self-forcing patch with as few as 271 specified cells exists for this still life.<ref name="p193510" /> In January | On September 2, {{year|2024}}, 400spartans found a population-184 stabilization of a self-forcing patch with 283 specified cells.<ref name="p193366" /> The discovery process for the new unconstructible still life involved the use of a hybrid tool incorporating ideas from Törmä and Salo's gol-agars program and [[mtve]]'s grandfatherless pattern algorithm, which builds up a pattern by adding overlapping 3x3 squares while keeping track of the number of predecessors within the same bounding box. A self-forcing patch with as few as 271 specified cells exists for this still life.<ref name="p193510" /> | ||
In January 2025, 400spartans reduced the population record again to 162 live cells.<ref name="message1330285175996940398" /> On April 4, they reduced the population record to 154 cells by identifying small regions that don't appear in known self-forcing patches, searching for large irregular agars without these, finding each one's maximal self-forcing subset and checking whether random {{times|24|24}} subsections of this are self-forcing.<ref name="message1357522386236477543" /> The smallest known total required number of specified cells for the 154-live-cell patch is 272 -- i.e., 118 dead cells must also be specified.<ref name="post231519" /> | |||
{{gallery top}} | {{gallery top}} | ||
{{gallery item|{{EmbedViewer | {{gallery item|{{EmbedViewer | ||
| Line 103: | Line 105: | ||
{{gallery item|{{EmbedViewer | {{gallery item|{{EmbedViewer | ||
|rle = x = 23, y = 22, rule = LifeHistory | |rle = x = 23, y = 22, rule = LifeHistory | ||
6.2A$5.A2.A3.2A$4.DC2DCD2.A3.2A$3.ACD2CD2CDCD.C2.A$ | 6.2A$5.A2.A3.2A$4.DC2DCD2.A3.2A$3.ACD2CD2CDCD.C2.A$2.DC2DC2DC2D2C2DC2D | ||
C$.AC2DC2DC2DC2D2CD2CDA$A.D2CD2CD2CDC2DC2DCDA$.A.C2DC2DC2D2C2DC2DC$2A | |||
.2DC2DC2DC2D2CD2CD$.A.D2CD2CD2C2DC2DC2D.2A$.A.C2DC2DC2D2C2DC2DA2.A$2. | |||
ADC2DC2DC2DCD2CDACDA$3.D2CD2CD2C2DC2DC2DC$3.A2DC2DC2D2C2DC2DCD$3.2A.2D | |||
C2DC2D2CD2CD$7.2CD2C2DC2DC2D$6.A2DC2D2C2DC2DC$5.A.C2DC2DCD2C.2A$5.A.2C | |||
D2C2DCD.A$6.A.DCD4.A.A$7.A.A6.A$8.A! | |||
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 16 WIDTH 600 HEIGHT 600 THEME LifeHistory ]] | |viewerconfig = #C [[ THUMBSIZE 2 ZOOM 16 WIDTH 600 HEIGHT 600 THEME LifeHistory ]] | ||
|caption = A population-154 unconstructible still life, with a self-forcing patch of | |caption = A population-154 unconstructible still life, with a self-forcing patch of 252 specified cells. | ||
|style = width:300px; | |style = width:300px; | ||
}}}} | }}}} | ||
| Line 188: | Line 195: | ||
|channel = cgol | |channel = cgol | ||
|id = 1357522386236477543 | |id = 1357522386236477543 | ||
}}</ref> | |||
<ref name="post231519">{{LinkForumThread | |||
|format = ref | |||
|p = 231519 | |||
|title = Re: Stable patterns which are not glider-constructible | |||
|author = Keith Amling | |||
|date = July 15, 2026 | |||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
Revision as of 13:27, 5 August 2026
| 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 mostly of repeated four snakes around block units 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 have related infinite agars with this property.[7]
On September 2, 2024, 400spartans found a population-184 stabilization of a self-forcing patch with 283 specified cells.[8] The discovery process for the new unconstructible still life involved the use of a hybrid tool incorporating ideas from Törmä and Salo's gol-agars program and mtve's grandfatherless pattern algorithm, which builds up a pattern by adding overlapping 3x3 squares while keeping track of the number of predecessors within the same bounding box. A self-forcing patch with as few as 271 specified cells exists for this still life.[9]
In January 2025, 400spartans reduced the population record again to 162 live cells.[10] On April 4, they reduced the population record to 154 cells by identifying small regions that don't appear in known self-forcing patches, searching for large irregular agars without these, finding each one's maximal self-forcing subset and checking whether random 24 × 24 subsections of this are self-forcing.[11] The smallest known total required number of specified cells for the 154-live-cell patch is 272 -- i.e., 118 dead cells must also be specified.[12]
(click above to open LifeViewer)
(click above to open LifeViewer)
(click above to open LifeViewer)
(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
- ↑ 400spartans (September 2, 2024). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ Matthias Merzenich (September 4, 2024). Re: Unproven conjectures (discussion thread) at the ConwayLife.com forums
- ↑ mu.sicman (January 18, 2025). Message in #cgol on the Conwaylife Lounge Discord server
- ↑ mu.sicman (April 4, 2025). Message in #cgol on the Conwaylife Lounge Discord server
- ↑ Keith Amling (July 15, 2026). Re: Stable patterns which are not glider-constructible (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.