Remote-Url: https://cp4space.hatsya.com/2022/01/14/conway-conjecture-settled/ Retrieved-at: 2022-01-17 18:58:46.614699+00:00 Complex Projective 4-Space Where exciting things happen [cropped-banner-xmas2] Skip to content • Home • About • Cipher solvers □ Season IV ☆ Solved cipher 71 □ Season III ☆ Solved cipher 70 ☆ Solved cipher 69 ☆ Solved cipher 68 ☆ Solved cipher 67 ☆ Solved cipher 66 ☆ Solved cipher 65 ☆ Solved cipher 64 ☆ Solved cipher 63 ☆ Solved cipher 62 ☆ Solved cipher 61 ☆ Solved cipher 60 ☆ Solved cipher 59 ☆ Solved cipher 58 ☆ Solved cipher 57 ☆ Solved cipher 56 ☆ Solved cipher 55 ☆ Solved cipher 54 ☆ Solved cipher 53 ☆ Solved cipher 52 ☆ Solved cipher 51 □ Season II ☆ Solved cipher 50 ☆ Solved cipher 49 ☆ Solved cipher 48 ☆ Solved cipher 47 ☆ Solved cipher 46 ☆ Solved cipher 45 ☆ Solved cipher 44 ☆ Solved cipher 43 ☆ Solved cipher 42 ☆ Solved cipher 41 ☆ Solved cipher 40 ☆ Solved cipher 39 ☆ Solved cipher 38 ☆ Solved cipher 37 ☆ Solved cipher 36 ☆ Solved cipher 35 ☆ Solved cipher 34 ☆ Solved cipher 33 ☆ Solved cipher 32 ☆ Solved cipher 31 □ Season I ☆ Solved cipher 30 ☆ Solved cipher 29 ☆ Solved cipher 28 ☆ Solved cipher 27 ☆ Solved cipher 26 ☆ Solved cipher 25 ☆ Solved cipher 24 ☆ Solved cipher 23 ☆ Solved cipher 22 ☆ Solved cipher 21 ☆ Solved cipher 20 ☆ Solved cipher 19 ☆ Solved cipher 18 ☆ Solved cipher 17 ☆ Solved cipher 16 ☆ Solved cipher 15 ☆ Solved cipher 14 ☆ Solved cipher 13 ☆ Solved cipher 12 ☆ Solved cipher 11 ☆ Solved cipher 10 ☆ Solved cipher 9 ☆ Solved cipher 8 ☆ Solved cipher 7 ☆ Solved cipher 6 ☆ Solved cipher 5 ☆ Solved cipher 4 • Contact • Publications • Revision □ IA revision □ IB revision • Skydive ← Training a random Gaussian generator 29-year-old Conway conjecture settled Posted on January 14, 2022 by apgoucher 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: [torma-salo] 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. [cunningham] 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. Share this: • Twitter • Facebook • Like this: Like Loading... This entry was posted in Uncategorized. Bookmark the permalink. ← Training a random Gaussian generator 5 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. [797d] sansdomino says: January 16, 2022 at 3:44 pm 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? Reply □ [fc95] apgoucher says: January 16, 2022 at 7:32 pm 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). Reply 4. Pingback: 29-year-old Conway conjecture settled by OscarCunningham - HackTech News Leave a Reply Cancel reply • Search for: [ ] [Search] • Recent Posts □ 29-year-old Conway conjecture settled □ Training a random Gaussian generator □ Involutions on a finite set □ Hamming backups: a 2-of-3 variant of SeedXOR □ An efficient prime for number-theoretic transforms • Subscribe to Complex Projective 4-Space Enter your email address to subscribe to this blog and receive notifications of new posts by email. Join 2,751 other subscribers Email Address [ ] Subscribe • Archives □ January 2022 □ December 2021 □ September 2021 □ July 2021 □ June 2021 □ May 2021 □ February 2021 □ January 2021 □ December 2020 □ November 2020 □ October 2020 □ September 2020 □ August 2020 □ July 2020 □ June 2020 □ May 2020 □ June 2019 □ May 2019 □ March 2019 □ November 2018 □ September 2018 □ July 2018 □ June 2018 □ May 2018 □ April 2018 □ March 2018 □ February 2018 □ November 2017 □ October 2017 □ November 2016 □ May 2016 □ March 2016 □ February 2016 □ December 2015 □ September 2015 □ March 2015 □ February 2015 □ January 2015 □ December 2014 □ November 2014 □ October 2014 □ September 2014 □ August 2014 □ July 2014 □ June 2014 □ May 2014 □ April 2014 □ March 2014 □ February 2014 □ January 2014 □ December 2013 □ November 2013 □ October 2013 □ September 2013 □ August 2013 □ July 2013 □ June 2013 □ May 2013 □ April 2013 □ March 2013 □ February 2013 □ January 2013 □ December 2012 □ November 2012 □ October 2012 □ September 2012 □ August 2012 • Recent Comments □ Craig Wright And The BlackNet Lie – Crypto Bullish Bears on Is Craig Wright? □ apgoucher on 29-year-old Conway conjecture settled □ 29-year-old Conway conjecture settled by OscarCunningham - HackTech News on 29-year-old Conway conjecture settled □ sansdomino on 29-year-old Conway conjecture settled □ === popurls.com === popular today on 29-year-old Conway conjecture settled Complex Projective 4-Space Proudly powered by WordPress. %d bloggers like this: