Remote-Url: https://cp4space.hatsya.com/2022/01/14/conway-conjecture-settled/
Retrieved-at: 2022-01-17 18:58:46.614699+00:00

Ilkka TörmäandVille Salo, a pair of researchers at the University of Turku in Finland, have found a finite configuration in Conway’s Game of Life such that, if it occurs within a universe at time T, it must have existed in that same position at time T−1 (and therefore, by induction, at time 0). Here is the configuration of live and dead cells, surrounded by an infinite background of grey “don’t care” cells:The configuration was discovered by experimenting with finite patches of repeating ‘agar’ and using a SAT solver to check whether any of them possess this property. Similarly, one can use a SAT solver to verify that Törmä and Salo’s result is correct.Since this configuration can be stabilised (by the addition of further live cells, shown in yellow) into a finite still-life, this demonstrates that not every still-life can be constructed by colliding gliders.The first finite stabilisation was 374 cells, but this was promptly reduced to 334 cells by Danielle Conway and then to the 306-cell configuration above by Oscar Cunningham. Oscar moreover proved, again using SAT solvers, that this is the minimum-population stabilisation of the Törmä-Salo configuration.Consequently, we have the following pair of bounds:Every strict still-life with ≤ 20 cells can be synthesised by gliders.There exists a strict still-life with 306 cells that cannot be synthesised.More importantly, the Törmä-Salo result positively answers a question first posed by John Conway himself on 24th August 1992:The things buildable by gliders (an idea I think first popularizedby Buckingham) are a nice class, mainly because they are provably ofinfinite “age” (at least if you define them correctly). I’m sure weshould NOT believe, however, that everything of infinite age is sobuildable (even if most of us do). I expect that there is a still lifeof such delicacy that in some essential sense it is its only ancestor –though obviously that sense must allow for fading configurations outsideit, and probably allow for more.This brings me to an interesting point – the false lessons experiencemight teach us. Experience is a bad guide to large configurations – itteaches us perhaps that there is no orphan, that almost all configurationsdie down pretty soon – whereas almost all configurations ARE orphans, ofcourse, and PROBABLY almost all configurations grow infinitely, as youasserted in your note, but I’m sure not meaning that it was provably true.A non-constructibleSorry – A non-(glider-)constructible configuration might be somethingthat’s almost an orphan, in that it can only arise from a similarconfiguration at the previous time, which itself can only arise from … .Indeed, is there a Godlike still-life, one that can only have existedfor all time (apart from things that don’t interfere with it)? I likethis one! I imagine it might be findable too, by a version of the searchesthat found the old orphans (gardens-of-eden), but restricted to still-lifes.Well, I’m going out to get a hot dog now, so will stop this. It wasoriginally intended to be only a very much shorter thank-you note, and sowas addressed only to you – please circulate it if you like. JHCThe construction also implies a solution to thegeneralised grandfather problem: a pattern which has an N-tick predecessor but not an (N+1)-tick predecessor. The diameter of such a pattern grows like Θ(sqrt(log(N))).Previous results were known for small values of N (N=0 by Roger Banks, andN=1,2,3 by mtve). Recently Törmä and Salo settled the problem for all positive integers, but the diameter of the pattern implied by their proof grows like Θ(N). A few days later they discovered the pattern in this post, which implies the stronger (and indeed optimal up to a constant factor) result above.In other GoL-related news:David Rauccidiscovered the first oscillator of period 38. The remaining unsolved periods are 19, 34, and 41.Darren Li has connectedCharity EnginetoCatagolue, providing approximately 2000 CPU cores of continuous effort and searching slightly more than 10^12 random initial configurations per day.Nathaniel Johnston and Dave Greene have publisheda bookon Conway’s Game of Life, featuring both the theoretical aspects and engineering that’s been accomplished in the half-century since its conception. Unfortunately it was released slightly too early to include the Törmä-Salo result or Raucci’s period-38 oscillator.