29-year-old Conway conjecture settled

Ilkka Törmä and Ville 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 popularized
by Buckingham) are a nice class, mainly because they are provably of
infinite “age” (at least if you define them correctly). I’m sure we
should NOT believe, however, that everything of infinite age is so
buildable (even if most of us do). I expect that there is a still life
of such delicacy that in some essential sense it is its only ancestor –
though obviously that sense must allow for fading configurations outside
it, and probably allow for more.

This brings me to an interesting point – the false lessons experience
might teach us. Experience is a bad guide to large configurations – it
teaches us perhaps that there is no orphan, that almost all configurations
die down pretty soon – whereas almost all configurations ARE orphans, of
course, and PROBABLY almost all configurations grow infinitely, as you
asserted in your note, but I’m sure not meaning that it was provably true.

A non-constructible
Sorry – A non-(glider-)constructible configuration might be something
that’s almost an orphan, in that it can only arise from a similar
configuration at the previous time, which itself can only arise from … .

Indeed, is there a Godlike still-life, one that can only have existed
for all time (apart from things that don’t interfere with it)? I like
this one! I imagine it might be findable too, by a version of the searches
that 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 was
originally intended to be only a very much shorter thank-you note, and so
was addressed only to you – please circulate it if you like. JHC

The construction also implies a solution to the generalised 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, and N=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 Raucci discovered the first oscillator of period 38. The remaining unsolved periods are 19, 34, and 41.
  • Darren Li has connected Charity Engine to Catagolue, 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 published a book on 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.
This entry was posted in Uncategorized. Bookmark the permalink.

17 Responses to 29-year-old Conway conjecture settled

  1. Pingback: 29-year-old Conway conjecture settled - The web development company Lzo Media - Senior Backend Developer

  2. Pingback: === popurls.com === popular today

  3. sansdomino says:

    Weird that this is a ~4×5 chunk of an agar. Are e.g. the corresponding ~3×4 and ~4×4 chunks still synthesizable, and if yes, why would their synthesis not generalize to adding another column still? Would they possess “unitary” syntheses that don’t build the agar fragment up gradually but in a single step?

    • apgoucher says:

      A 1×1 chunk of the agar can be constructed in 20 gliders:

      https://catagolue.hatsya.com/object/xs28_ck3qp3ckz11642611/b3s23

      Note that this involves gliders travelling from all four directions, and the ‘explosion’ from the synthesis means that it can only be built if there’s enough surrounding empty space, so you can’t use this to incrementally construct up a larger chunk.

      It’s unknown at the time of writing whether any of the larger chunks can be synthesised (including 1×2). The 4×5 example is just the smallest that can be ruled out using the argument that it contains a subpattern that must be present in all predecessors. It could be the case that smaller chunks (such as 4×4) also have no synthesis, but require more sophisticated proof techniques.

      As you correctly remark, a synthesis of a 4×4 chunk (if such a synthesis exists) cannot be a column-by-column incremental construction, because then it would imply the synthesis of a 4×5 chunk (which we know is impossible).

      • sansdomino says:

        I think the point remains if we don’t mean glider constructibility but just the existence of any nonidentical ancestor. If smaller chunks of the agar do have nonidentical ancestors (i.e. any small parts of this pattern, too, have “local ancestors” on the edge), is the issue then that these are so limited in options that they cannot be combined in a way to complete a nonidentical ancestor of the entire 4×5 pattern?

  4. Pingback: 29-year-old Conway conjecture settled by OscarCunningham - HackTech News

  5. Congratulations on this discovery. Delighted we could help!

  6. Timothy Chow says:

    After reading this announcement, I sent a congratulatory email to Ville Salo, and learned that this problem is actually almost 50 years old. See the description of the “Unique Father Problem” here: https://www.conwaylife.com/w/images/a/aa/Lifeline_vol_6.png

    • apgoucher says:

      There’s been some confusion because Törmä and Salo simultaneously solved two open problems with this construction, one of which is a strict strengthening of the other.

      In particular, the Unique Father Problem (1972) is weaker than the conjecture in Conway’s 1992 e-mail. The statements differ in that the more recent conjecture requires that the pattern be a still-life, whereas the original statement was a ‘stable object’ (allowing for oscillators, which is why the description you linked suggests the period-2 clock as a candidate solution).

      Now, it’s possible in principle for there to exist an oscillatory configuration A with a unique father B, but where B has multiple different predecessors (so A has a unique father but multiple distinct grandfathers, and may even be synthesisable by gliders). This would satisfy the conditions of the 1972 conjecture, but not the 1992 strengthening (which stipulates ‘still-life’).

      Moreover, Conway’s 1992 e-mail explicitly made the observation that such a pattern must have existed in that location untouched since the beginning of time, and therefore not be synthesisable by gliders. The fact that a pattern can globally force its complete history seems much more deep and exciting than the existence of a stable pattern that merely determines its immediate predecessor.

  7. Pingback: A Conway 'Game of Life' Conjecture Settled After 29 years – KikiXPress

  8. Pingback: A Conway ‘Game of Life’ Conjecture Settled After 29 years – Modding The World

  9. Adam Rosenfield says:

    Every live cell in this configuration has exactly 4 neighbors, wouldn’t they all immediately die out from overpopulation? (And every dead cell has exactly 5 neighbors, so no new cells would be born.) Or is this result for some variation other than the usual B3/S23?

    Is the full paper from Törmä and Salo available online anywhere? I’m unable to find it.

    • Timothy Chow says:

      It looks like you’ve mixed up live and dead cells. Live cells are white; dead cells are black.

      I wrote to Salo and learned that they’re still in the process of writing up their results.

  10. dave cotter says:

    is someone going to provide a pre-constructed online simulator so we can see it in action?

    • A Morales says:

      I’ve tediously reconstructed the RLE sequence for the stabilized and nonstabilized Törmä-Salo Conway configuration. Go to https://copy.sh/life/ and then enter either sequence in “import”. Then you can run the simulation.

      Here you go:

      Nonstabilized:
      x=27, y = 22, rule = B3/S23
      5bo4b2o4b2o4b2o4b$2bo2bob2o2bob2o2bob2o2bobo2b$b2obo2b2obo2b2obo2b2obo2b2ob$4b2o4b2o4b2o4b2o4b$2obo2b2obo2b2obo2b2obo2b2o2b$ob2o2bob2o2bob2o2bob2o2bob2o$4b2o4b2o4b2o4b2o4b$b2o2bob2o2bob2o2bob2o2bob2ob$b2obo2b2obo2b2obo2b2obo2b2ob$4b2o4b2o4b2o4b2o4b$2obo2b2obo2b2obo2b2obo2b2obo$ob2o2bob2o2bob2o2bob2o2bob2o$4b2o4b2o4b2o4b2o4b$b2o2bob2o2bob2o2bob2o2bob2ob$b2obo2b2obo2b2obo2b2obo2b2ob$4b2o4b2o4b2o4b2o4b$2obo2b2obo2b2obo2b2obo2b2obo$2b2o2bob2o2bob2o2bob2o2bob2o$4b2o4b2o4b2o4b2o4b$b2o2bob2o2bob2o2bob2o2bob2ob$2bobo2b2obo2b2obo2b2obo2bo2b$4b2o4b2o4b2o4bo5b!

      Stabilized (Oscar Cunningham):
      x=33, y = 28, rule = B3/S23
      12b2o4b2o14b$12bo5bo15b$7b2o5bo5bo7b2o4b$6bobo4b2o4b2o4b2o2bo4b$2b2obo2bob2o2bob2o2bob2o2bobo5b$2bob2obo2b2obo2b2obo2b2obo2b2o4b$7b2o4b2o4b2o4b2o3bo3b$3b2obo2b2obo2b2obo2b2obo2b2o2bo2b$3bob2o2bob2o2bob2o2bob2o2bob3o2b$7b2o4b2o4b2o4b2o7b$4b2o2bob2o2bob2o2bob2o2bob2o4b$4b2obo2b2obo2b2obo2b2obo2b2o4b$7b2o4b2o4b2o4b2o5b2o$2b3obo2b2obo2b2obo2b2obo2b2obo2bo$o2bob2o2bob2o2bob2o2bob2o2bob3o2b$2o5b2o4b2o4b2o4b2o7b$4b2o2bob2o2bob2o2bob2o2bob2o4b$4b2obo2b2obo2b2obo2b2obo2b2o4b$7b2o4b2o4b2o4b2o7b$2b3obo2b2obo2b2obo2b2obo2b2obo3b$2bo2b2o2bob2o2bob2o2bob2o2bob2o3b$3bo3b2o4b2o4b2o4b2o7b$4b2o2bob2o2bob2o2bob2o2bob2obo2b$5bobo2b2obo2b2obo2b2obo2bob2o2b$4bo2b2o4b2o4b2o4bobo6b$4b2o7bo5bo5b2o7b$15bo5bo12b$14b2o4b2o12b!

      Additionally, you could go here to see the configuration as it is catalogued:
      https://catagolue.hatsya.com/object/xs306_wgg0g84s0gg39s0gg08o0kczw1c59cjic59cjic59cjic59aczg08objo65objo65objo65objog4cz11ggm6gdbgm6gdbgm6gdbgm6g08oz3201cd1qm1cd1qm1cd1qm1cd11zw359q3kc3pq3kc3pq3kc3pajozy032011y039cx321/b3s23

      Best wishes.

Leave a Reply