10 ms·

Building arbitrary Life patterns in 15 gliders

510 points by mikro2nd 4y ago

snoopy_telex 4y ago
Amazing accomplishment! If I didn’t know better, this could have been in the next bobiverse book!
eurasiantiger 4y ago
The 15 is strangely familiar. Hypothesis: if the interaction of any pair of oscillators can theoretically be represented by a single oscillator, this could also be possible with 4 and 6 (larger) gliders, simply because (4 over 2) = 6, (6 over 2) = 15. The above may only hold in a continuous-valued GoL, or it may not hold at all.
- anderskaseorg 4y ago
  There’s no “larger glider”. The name “glider” refers to a single specific pattern of five cells. https://en.wikipedia.org/wiki/Glider_(Conway%27s_Life) https://en.wikipedia.org/wiki/Glider_(Conway%27s_Life)
  - biggiemac42 4y ago
    LMAO I found outdated info on that wikipedia page, in the best way. "Some patterns require a very large number (sometimes hundreds) of glider collisions"
    - dvgrn 4y ago
      Ha -- when was that written?... Let's see, the original form of the statement showed up in 2012: "Some patterns require a very large number (scores, even hundreds) of glider collisions..." At that time Andrew Wade had already created the self-constructing Gemini spaceship, which needed 173449 gliders to build ( https://conwaylife.com/wiki/Glider_synthesis#Spaceship_syntheses https://conwaylife.com/wiki/Glider_synthesis#Spaceship_synth... ). The recipe could have been reworked to be a little cheaper, but nobody bothered at the time -- and now it can be done in fifteen gliders instead. If you want to see the construction happening, I'd definitely recommend the old Gemini recipe over an RCT-based one, though! RCT cuts down the cost in gliders to a minimum, but at a terrible cost in the time you have to wait around to see the completed object.
  - eurasiantiger 4y ago
    True. I was thinking about spaceships and other oscillating movers.
    - dvgrn 4y ago
      It's not impossible that we could come up with a way of crashing less than 15 moving objects together to get an alternate RCT pattern. Gliders are generally considered to be the "lowest common denominator", though, so adding complexity by allowing more types of spaceships isn't usually seen as an improvement. ... It also becomes possible to cheat: I suspect we could put together something like an "RCT8" if we allowed Corderships as well as gliders in the list of allowed moving objects that we start with. (2-engine Corderships' "engines" are switch engines, and we have to build four switch engines to get the RCT reaction started. Could probably just shoot down the extra switch engine with one glider, and go from there.)
      - eurasiantiger 4y ago
        To be honest, GoL isn’t quite as interesting as continuous-valued CAs — the latter break into quantum field territory.
pfortuny 4y ago
This is awesome. This result would fit perfectly well in Wolfram's NKS. The next question is... is this the minimum?
- rrobukef 4y ago
  Can it construct itself as some giant spaceship / oscillator?
  - pfortuny 4y ago
    Well, no idea.
  - biggiemac42 4y ago
    It can! A seed constellation for the initial gliders would be possible using the extra debris from the original collision. Without using that debris, there might be a problem reaching far enough without adding extra bits that each double the amount of reaching to get to the right starting point. So I think would be a specialized recipe for a couple reasons.
- OscarCunningham 4y ago
  We've checked every 3 glider collision. So our bounds on 'God's Number' are 4 <= N < 16.
  - gnramires 4y ago
    I find every interesting the following problem: what is the minimum universal constructor with a linear string, that is, a sequence of gliders that encode information efficiently (not using exponential space, but using a combinatorial combination of N gliders, for O(N) bits)? Bonus question: can this string be "folded" so that it occupies a radius of O(sqrt(N))? (now we have a close analogue of DNA! It's fascinating that indicates the universality of DNA and life -- we seem to be somewhat limited universal constructors) Other questions: are there "Constructor classes" -- non-universal constructors specialized in building a certain "chemistry", a useful subset of all structures? What is the minimum (restricted) efficient contructor capable of building (a) A copy of itself; (b) A Turing machines; (c) Turing machine and construction tapes. Also I've been thinking about reliability. Is there a constructor that can tolerate a flip ("error") anywhere inside? That can tolerate any single glider collision? Or can tolerate "most" bit flips? An interesting difference between CGoL and our universe is that we live in a thermal and quantum bath. So in a sense (that's up to QM metaphysics) there is inherent randomness in particles, and of course all particles chaotically "wiggle" at positive temperatures (it might be argued CGoL also has wiggle, but in CGoL you can have non-chaotic, periodic large systems -- it's essentially easy to have 0 temperature systems). I've been playing with simulation of CGoL that have a proportion of random flips each generation. I've been investigating whether interesting structures come out of the "soup" -- this is more interesting, I believe, that just starting from a soup and seeing if something survives (in a deterministic universe), because you can have "multi-step evolution": maybe some small structure comes up, and then random perturbations slowly make more interesting structures emerge -- in a faint analogue to the origin of life, or just faint analogues of chemistry/proto-evolution -- the population of patterns evolves with time. It would be really cool to have a crowdsourced set of long-time simulations of such a field. Another important open problem related is how to define a 'Life detector' (in Life). A Life detector is an algorithms that given a pattern and a few generations, tells you how complex, interesting, and 'alive' that pattern is. Very fun and significant problem I believe. Together, this means we can run massive crowdsourced searches to understand environments that tend to evolve interesting patterns (although of course anything close to a bona fide lifeform is probably still far out of reach of our computing power, and might benefit from other kinds of analysis)..
abetusk 4y ago
The basic idea is to use the distance of the gliders to encode information, so when they hit each other allows for an embedding of a Turing machine. I'm no expert here but some basic ideas are that some small number of gliders (two?) can hit each other and produce a "glider gun", allowing for just a few gliders to "upgrade" to producing a steady stream of gliders. There's a "Reverse Caber Tosser" (RCT) structure which has a stationary element that "tosses" a glider back and forth with a structure moving away (or towards?) it, emitting another glider in another direction after each toss, allowing for logarithmic glider/population growth. Another key idea looks to be the "glider producing switch engine" (GPSE) which incorporates the ideas of the RCT with a delay and some other logic? The distances involved are astronomical because they're encoding everything in the distance but they still manage to make it Turing machine equivalent with only 15 gliders. Anyway, I'm floored at the ingenuity of the GoL community. It's as close to programming with butterflies as I've ever seen [0]. [0] https://xkcd.com/378/ https://xkcd.com/378/
- hinkley 4y ago
  I might have my books mixed up but I believe this idea was a subplot in one of David Brin's early books, The Practice Effect. First Edition: 1984.
  - hakuseki 4y ago
    Might it have been Glory Season?
    - hinkley 4y ago
      Might be. It's been a long time. That one is 1993, which still means a 30 year old idea.
- biggiemac42 4y ago
  To clean up the mistakes in your summary: 4 gliders hit each other to make a stream of gliders. This isn't a gun, because a gun costs more. instead it's a GPSE, which looks like a gun from the barrel end, but has a limit. As it approaches that limit, the RCT mechanism lets another three GPSEs generate an arbitrary list of bits, controlled by the precise location of the first (as a binary number). The final count 15 comes from the naive 4×4 minus one from being able to piggyback one of the constructions off a neighbor to save a single glider. From bits to an embedded turing machine is gol magic that the blog post treats better than my comment could.
anoncow 4y ago
As a lay Comp Sci person I am wondering what this translates into? What implication does this have?
- zorked 4y ago
  It's pretty cool.
- chriswarbo 4y ago
  The principle is the same as von Neumann's "universal constructor", so it doesn't really prove anything we didn't know in theory. However, von Neumann's design uses a cellular-automaton with many more rules, and those were specifically chosen to help define that constructor (Langton Loops are a more extreme example of choosing rules to make construction easier). In constrast, the rules for Game of Life (GoL) were chosen to be simple and interesting, not fine-tuned for any particular patterns (for an even simpler set of rules, see the Rule 110 cellular-automaton). We know the GoL is Turing-complete, so it can emulate any computable system; including those other cellular-automata, e.g. von Neumann's universal constructor. Such emulations will typically use a large GoL pattern to represent each emulated cell (e.g. see "life in life"): if we emulate a universal constructor, we can use it to assemble any pattern of those emulated cells. We could also emulate GoL inside some other cellular-automaton, and hence use a universal constructor to assemble any pattern of emulated GoL cells. But the question still remains: can we assemble any pattern of "native" GoL cells? That's what the constructors in the article are doing (at least, for a broad class of patterns). The rest is a matter of "code golf", trying to make the patterns smaller and faster (and indeed feasible to run on a real PC!) https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Unit_cell https://conwaylife.com/wiki/Unit_cell
squaredot 4y ago
This result is really beautiful! At the same time, it's like GoL has been conquered, and in that it leaves me a little sad. But just a little bit. Congratulations!
- soulofmischief 4y ago
  This "conquering" is all just proof as to the fundamental nature of the Game of Life. It's not hard to imagine a working system of walking proteins and unzipping DNA structures in light of these findings. It really is beautiful.
  - biggiemac42 4y ago
    I think the portion that is fundamental is deeper than game of life itself. Game of life is a rule set with sufficient complexity to get this far, but it isn't the only one. Anything with this class of behavior will support systems including those resembling DNA, the question is at what scale it emerges. If the scale is too big (arguably the scale for the result in this post is too big), it's a less elegant kind of emergence.
    - soulofmischief 4y ago
      Agreed. One aspect of CA which interests me is robustness, the ability of a system to recover from error states. What's been done with GoL is fascinating, but I think the next emergent layer of fascination for me is universal constructors which can handle a certain level of constant distributed noise or interference. A lot of times people just shrug and say, "well this pattern will always be critical/vulnerable in these locations, and cannot be made robust. But to me that opens up the door for entire classes of patterns which measure, embed and repair state of surrounding entities.
  - galaxyLogic 4y ago
    Very interesting. A biological cell is a 3-D self-replicating pattern (or is it 2-D rather?). Does GoL give us some insight into the nature of biological cells?
biggiemac42 4y ago
Hi there, I'm the author (of the blog post, not of the achievement itself)! So glad this is spreading. Feel free to ask here or on the post for more clarification if stuff is too unclear
- Traubenfuchs 4y ago
  How much of advanced GoL is intuition and genius you were born with and how much is math/logic anyone can learn with enough time?
  - biggiemac42 4y ago
    Definitely worth trying to learn! As with most topics, it starts out seeming hard to grasp, and then you start naming things and recognizing them. What looks like jargon to an outsider is just a compressed way of communicating. The people in the community are smart and tend to compress their ideas really far which makes the jargon even more extreme. Advanced gol is just getting past that first hurdle of understanding the densely compressed info behind the jargon. And it doesn't ever need to be done for all of the concepts. You can be versed in just one. I started out in a super specialized corner in self constructing spaceships. That said I'm a bit of a whiz in other areas so I can't be used as evidence that it works for everyone..
    - dvgrn 4y ago
      I think the biggest prerequisite for getting good at "advanced GoL" is just an unreasonable amount of patience. Probably I'm a good case in point. I'm definitely not a particularly clever mathematician, but it seems like it's possible to understand any new Life technology just by tinkering with the pieces for long enough. If anyone wants to follow along with that kind of learning process, just start working through the Life textbook that kryptiskt mentioned. (Full disclosure, I'm one of the authors.)
    - isoprophlex 4y ago
      I just want to say that I love everything the GoL community has built and discovered over the years. Big crazy things like this always fill my heart with awe and wonder. Even though in my life, I can't make the time for doing something on the grandiose scale required, I can live vicariously through reading about your sheer dedication and intellectual effort expended.
Rodeoclash 4y ago
Amazing work!
NeoTar 4y ago
Do we have any idea / intuition about what proportion of patterns are build-able? If not on an infinite grid, then some subset (i.e. 100% of 1x1 patterns are build-able, 80% of 3x3 patterns, 60% of 5x5 patterns, etc.)
- biggiemac42 4y ago
  This is a really good and not at all easy to answer question. The most I can say is that folks earlier this year used some SAT solver equivalent to find notable patterns that cannot be constructed - including a still life and an oscillator https://conwaylife.com/wiki/Unsynthesizable_oscillator_1 https://conwaylife.com/wiki/Unsynthesizable_oscillator_1. This doesn't have much bearing on the probability of constructability for an arbitrary large pattern.
  - JKCalhoun 4y ago
    Yeah, I was wondering, with todays computing power, if it were possible to run outrageously large random Life universes and use some sort of software to look for "interesting patterns" (whatever that means). Or are these "discoveries" being done by hand?
    - OscarCunningham 4y ago
      A lot of discoveries have come from 'soup search' where you start with a random 16 by 16 square and let it evolve. We've run over 156 trillion soups https://catagolue.hatsya.com/statistics https://catagolue.hatsya.com/statistics. This tends not no produce complicated machines, but rather small components that can then be engineered into larger patterns.
- chriswarbo 4y ago
  There are "garden of eden" patterns which can only exist as an initial configuration: there is no pattern which evolves into a garden of eden, hence there can be no constructor capable of building them https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom... If we limit ourselves to glider interactions, the article links to the following patterns which cannot be constructed (including garden of eden patterns): https://conwaylife.com/wiki/Category:Patterns_that_can_not_be_constructed_with_gliders https://conwaylife.com/wiki/Category:Patterns_that_can_not_b...
pastrami_panda 4y ago
This is an awesome article, and Conway would've been incredibly excited about this result. Thanks for sharing!
Zenst 4y ago
Interesting when you think about DNA and how that shapes things. Equally, compression, is this an avenue worth exploring and a whole new way of doing things awaiting to be tapped?
- dvgrn 4y ago
  Heh, oddly enough, the RCT can probably be better thought of as a way of explosively _decompressing_ a glider construction recipe. There are lots and lots of reasonable-sized recipes for constructing different patterns. When you apply the RCT trick to any of them, the cost in gliders always shrinks to 15, but the pattern's bounding box always expands to something gargantuan. The Life pattern that most evokes DNA and self-replication is another megapattern from several years ago, the 0E0P metacell, which even has a visible "nucleus" for its "DNA": https://conwaylife.com/wiki/0E0P_metacell
ivoras 4y ago
Interestingly enough, the concept of placing gliders at a distance away seems to touch on the relativity of space and time. Here, with space, we are also encoding the time at which a certain pattern (a glider) appears where it's needed. In a rigid system like the GoL, we can't trade space with time easily, since everything happens at a constant speed, but it makes one wonder...
- bewresu 4y ago
  ...if there's a GoL version where time varies somehow¹ with something² ¹ directly? ² amount of activity? mass?
  - dvgrn 4y ago
    There have been a lot of GoL variants over the years, but I don't remember running into any attempts to vary the speed of evolution in different locations on the same grid. The idea that all neighbors move to the next tick simultaneously is a fundamental assumption in cellular automata in general. If you try changing that, the optimizations that allow us to simulate CAs at any kind of reasonable speed ... all stop working, pretty much. It's kind of painful even to think about. Which means there are probably very interesting rules out there somewhere, where CAs run faster/slower depending on pattern density -- it's just going to be very tricky to explore that particular search space.
    - westurner 4y ago
      The "superstep" that we practically impose upon simulations of entropy and emergence is out of accord with our modern understanding of non-regularly-quantizable spacetime. The debuggable Von Neumann instruction pipeline precludes "in-RAM computing" which conceivably does converge if consensus-level error correction is necessary.
      - OscarCunningham 4y ago
        The term 'superstep' reminds me of the HashLife algorithm https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife for computing the Game of Life. It computes multiple generations at the same time, and runs at different speeds in different parts of the universe, but only with the purpose of computing CGoL faster, not to introduce any relativity.
Ftuuky 4y ago
How do I dive into this world? Any resources for a complete noob?
- OscarCunningham 4y ago
  Not necessarily in this order: * Download Golly https://golly.sourceforge.net/ https://golly.sourceforge.net/ and play around drawing random patterns. Have a look at the example patterns. * Have a look around on the LifeWiki https://conwaylife.com/wiki/Main_Page https://conwaylife.com/wiki/Main_Page. Click anything that looks interesting. * Read the free online book https://conwaylife.com/book/ https://conwaylife.com/book/ * Make an account on the forums https://conwaylife.com/forums/ https://conwaylife.com/forums/, or just lurk and see what people are talking about. * Hang out on the Discord https://discord.gg/uA6uaGv3 https://discord.gg/uA6uaGv3
L_226 4y ago
Neat, reminds me of the 22 alpha amino acids that comprise our RNA/DNA.
tromp 4y ago
This is an incredible achievement. The most impressive piece of GoL engineering I've ever seen! Clearly, number of gliders is no longer a good measure of complexity of constructions. Perhaps one should fix a straightforward way to encode a set of gliders by position (e.g. using [1]) and orientation and take the minimum number of bits of such a description. Just one question: > 1274729 – build a DBCA and pass control to it > 192584 – build a new constructor that reads stored data instead of live data > The final 200093 bits get stored in the Binary Storage and Retrieval device, these same 200093 bits are counted below: How come this adds up to 1667406, which is 1615 more than the claimed total of 1665791 bits? [1] https://en.wikipedia.org/wiki/Levenshtein_coding https://en.wikipedia.org/wiki/Levenshtein_coding
- biggiemac42 4y ago
  Ooh, I appreciate the diligence! The numbers here came from manually fiddling with more granular output from Pavgran's special purpose "profiler" script. One of those steps, where the DBCA assumes control of the bit stream, takes 1615 gliders. I would bet I made a mistake and added it twice, probably to both the DBCA building and the task of the DBCA itself. It belongs in only one of them! I can verify this later.
iamgopal 4y ago
What’s most complex thing achieved in GOL ?
- OscarCunningham 4y ago
  Probably either this or the 0E0P metacell https://conwaylife.com/wiki/0E0P_metacell https://conwaylife.com/wiki/0E0P_metacell, a large pattern which makes copies of itself in a way that mimics another cellular automaton, or Life itself.
vanderZwan 4y ago
Whenever I read one of these deep dives into GoL achievements, and let me preface this by saying I mean this as a compliment, I feel like I'm reading the extended universe lore on a wiki page for a giant fantasy franchise. It's maths but feels so much more narratively rich than most other mathematics somehow, and the community around it has such a unique subculture vibe to it too.
- VikingCoder 4y ago
  Have you read "Permutation City"? I'm definitely reminded of it every time.
  - jiggawatts 4y ago
    There is a pattern of 15 gliders that encodes a simulation of a universe where your mind is immortal and living in an endless paradise.
    - VikingCoder 4y ago
      Oh well, time to go back to climbing the skyscraper.
- OscarCunningham 4y ago
  This is the legacy of Conway (who invented Life) and Gardner (who popularised it).
- Silverback_VII 4y ago
  in my opinion Jeffery Ventrella's clusters are a more promising avenue than Conways GoL. The rules are in comparison very interesting as well: No creation out of nothing, only particles that attract or repel each other. The pattern it generates are pretty amazing as you can see here: https://youtu.be/0Kx4Y9TVMGg https://youtu.be/0Kx4Y9TVMGg
  - robertsdionne 4y ago
tiborsaas 4y ago
Absolutely mind blowing result, looking at the video at the bottom is so hard to comprehend there's no human interaction in this besides setting up the 15 gliders. At 1:57 it even looks like someone draws a line casually with a mouse.
isoprophlex 4y ago
I had a particularly hard time grokking the way the semilator works to reduce pattern size. It's a pretty difficult term to google too, being so similar to the word 'simulator'. Does anyone well versed in GoL-ogy care to share a short ELI5? Edit: thanks you people for the explanation, makes sense. Nice hack to make it feasible.
- biggiemac42 4y ago
  Right, as far as I can tell the term "semilator" was coined for this task, so google won't help. The middle of the RCT pattern where all of the action happens, reads its first bit 2^N generations B.S (before singularity, or before splat, whichever you prefer). Next bit is 2^(N-1) B.S. Next would be 2^(N-2), but this is what the semilator changes. During the franky enormous gap between 2^(N-1) and 2^(N-2) generations B.S, extra spaceships come in at an orthogonal direction. These have two possible configurations, giving equivalent results to either of the possible bit reads. This accelerates the speed of bit reading, and means that N of millions can be emulated by a pattern with N less than 30. Much less initial distance, much less time. The addition of millions of cells of spaceships doesn't make the overall pattern smaller in an informational sense, just in the scale of time and distance between its constituent parts.
- OscarCunningham 4y ago
  So the full-size pattern works by bouncing a signal back-and-forth between the construction site and an oncoming GPSE. Each time it does this it produces either one or two gliders depending on the positioning of the GPSE. It is these gliders that do the construction. But the 'recipe' contains 1665791 bits, meaning the signal has to bounce back-and-forth 1665791 times. Because the distance to the GPSE halves every time, it would have to start at a distance of 2^1665791, which is impractically large. So instead we only have it bounce back-and-forth a small number of times (26), and insert the other 1665765 bits 'manually' by adding streams of 1665765 spaceships that collide near the construction site.
sagebird 4y ago
Can automated theorem proving software be coaxed into finding recipes for GOL constructions? I would find it interesting trying to formalize notions that we easily perceive into computer-understood definitions. May end up with strange formalizations to make things as orthogonal as possible: IE a beehive is a glider speed zero.
- OscarCunningham 4y ago
  I have a program called LLS that uses SAT solvers to find patterns with specified properties. https://conwaylife.com/wiki/Logic_Life_Search https://conwaylife.com/wiki/Logic_Life_Search But it only works cell-by-cell, so it can't make big patterns like this.
- aidenn0 4y ago
  SAT has been used to find many things in GoL. IIRC the first "grandfatherless" pattern was found with one.
kleer001 4y ago
Seeing behind the curtain on this amazing work does nothing but make me think that the universe we're in has to be some kind of higher level cellular automata, somehow.
rotexo 4y ago
As a biologist with nearly no physics knowledge, this sort of work seems to have more in common with setting up quantum computers than it does with thinking about self-replication in living organisms, at least in terms of the lack of robustness to environmental noise. Maybe that is just overly metaphorical thinking on my part.
- nneonneo 4y ago
  It’s mathematics and computer science, not biology. Nobody is claiming that a setup requiring 2^1500000 units of space to run is anywhere near a realistic simulation of biological processes :) Nevertheless, it’s a fantastic example of how simple rules can give rise to complex systems.
  - dvgrn 4y ago
    Yup, the connection to self-replication has showed up mostly in the discussion here, in relation to true self-replicating patterns like the https://conwaylife.com/wiki/0E0P_metacell https://conwaylife.com/wiki/0E0P_metacell -- which does have a few vaguely cell-like attributes. The RCT design is very much a mathematical construct, as opposed to anything with a biological inspiration. And the RCT's ability to construct itself is more of a theoretical afterthought at this point -- the engineering work hasn't been done yet to produce a demo of that kind of thing. The point is well taken, about the fragility of Conway's Life with respect to environmental noise. That topic has also come up here and there in these comments, e.g., https://news.ycombinator.com/item?id=33797799#33800301 https://news.ycombinator.com/item?id=33797799#33800301
pugworthy 4y ago
Imagine in 1970 someone reading Martin Gardner's Scientific American article describing 'John Conway's new solitaire game "life"'. Perhaps the reader played around with graph paper plus pencil and eraser to explore what could be done. "Interesting", they might say. Or, "Fascinating!" even. And then you show them this article. Just imagine how mind blowing it would be to them. Original SciAm article -> https://www.ibiblio.org/lifepatterns/october1970.html https://www.ibiblio.org/lifepatterns/october1970.html
- yarnover 4y ago
  That was me, reading the original article as a youngster, working out generations on graph paper, etc. The difference is that I have been following the progress of researchers of Life through the years. It’s still astonishing!
  - dvgrn 4y ago
    Heh, yes, same here more or less -- I wrote an assembly-code Life program for my family's first personal computer (TRS-80 Model I) in the early 1980s, then mostly forgot all about Life for almost two decades ... until it became possible to search the Internet for "Conway's Life". At that point I was completely floored by how much progress had been made since the last time I was paying attention. Ever since 2001 I've been keeping a close eye on new developments so I don't get surprised like that again.

510 points by mikro2nd 4y ago

Amazing accomplishment! If I didn’t know better, this could have been in the next bobiverse book!

The 15 is strangely familiar. Hypothesis: if the interaction of any pair of oscillators can theoretically be represented by a single oscillator, this could also be possible with 4 and 6 (larger) gliders, simply because (4 over 2) = 6, (6 over 2) = 15. The above may only hold in a continuous-valued GoL, or it may not hold at all.

anderskaseorg 4y ago
There’s no “larger glider”. The name “glider” refers to a single specific pattern of five cells. https://en.wikipedia.org/wiki/Glider_(Conway%27s_Life) https://en.wikipedia.org/wiki/Glider_(Conway%27s_Life)
- biggiemac42 4y ago
  LMAO I found outdated info on that wikipedia page, in the best way. "Some patterns require a very large number (sometimes hundreds) of glider collisions"
  - dvgrn 4y ago
    Ha -- when was that written?... Let's see, the original form of the statement showed up in 2012: "Some patterns require a very large number (scores, even hundreds) of glider collisions..." At that time Andrew Wade had already created the self-constructing Gemini spaceship, which needed 173449 gliders to build ( https://conwaylife.com/wiki/Glider_synthesis#Spaceship_syntheses https://conwaylife.com/wiki/Glider_synthesis#Spaceship_synth... ). The recipe could have been reworked to be a little cheaper, but nobody bothered at the time -- and now it can be done in fifteen gliders instead. If you want to see the construction happening, I'd definitely recommend the old Gemini recipe over an RCT-based one, though! RCT cuts down the cost in gliders to a minimum, but at a terrible cost in the time you have to wait around to see the completed object.
- eurasiantiger 4y ago
  True. I was thinking about spaceships and other oscillating movers.
  - dvgrn 4y ago
    It's not impossible that we could come up with a way of crashing less than 15 moving objects together to get an alternate RCT pattern. Gliders are generally considered to be the "lowest common denominator", though, so adding complexity by allowing more types of spaceships isn't usually seen as an improvement. ... It also becomes possible to cheat: I suspect we could put together something like an "RCT8" if we allowed Corderships as well as gliders in the list of allowed moving objects that we start with. (2-engine Corderships' "engines" are switch engines, and we have to build four switch engines to get the RCT reaction started. Could probably just shoot down the extra switch engine with one glider, and go from there.)
    - eurasiantiger 4y ago
      To be honest, GoL isn’t quite as interesting as continuous-valued CAs — the latter break into quantum field territory.

pfortuny 4y ago

This is awesome. This result would fit perfectly well in Wolfram's NKS. The next question is... is this the minimum?

rrobukef 4y ago
Can it construct itself as some giant spaceship / oscillator?
- pfortuny 4y ago
  Well, no idea.
- biggiemac42 4y ago
  It can! A seed constellation for the initial gliders would be possible using the extra debris from the original collision. Without using that debris, there might be a problem reaching far enough without adding extra bits that each double the amount of reaching to get to the right starting point. So I think would be a specialized recipe for a couple reasons.
OscarCunningham 4y ago
We've checked every 3 glider collision. So our bounds on 'God's Number' are 4 <= N < 16.
- gnramires 4y ago
  I find every interesting the following problem: what is the minimum universal constructor with a linear string, that is, a sequence of gliders that encode information efficiently (not using exponential space, but using a combinatorial combination of N gliders, for O(N) bits)? Bonus question: can this string be "folded" so that it occupies a radius of O(sqrt(N))? (now we have a close analogue of DNA! It's fascinating that indicates the universality of DNA and life -- we seem to be somewhat limited universal constructors) Other questions: are there "Constructor classes" -- non-universal constructors specialized in building a certain "chemistry", a useful subset of all structures? What is the minimum (restricted) efficient contructor capable of building (a) A copy of itself; (b) A Turing machines; (c) Turing machine and construction tapes. Also I've been thinking about reliability. Is there a constructor that can tolerate a flip ("error") anywhere inside? That can tolerate any single glider collision? Or can tolerate "most" bit flips? An interesting difference between CGoL and our universe is that we live in a thermal and quantum bath. So in a sense (that's up to QM metaphysics) there is inherent randomness in particles, and of course all particles chaotically "wiggle" at positive temperatures (it might be argued CGoL also has wiggle, but in CGoL you can have non-chaotic, periodic large systems -- it's essentially easy to have 0 temperature systems). I've been playing with simulation of CGoL that have a proportion of random flips each generation. I've been investigating whether interesting structures come out of the "soup" -- this is more interesting, I believe, that just starting from a soup and seeing if something survives (in a deterministic universe), because you can have "multi-step evolution": maybe some small structure comes up, and then random perturbations slowly make more interesting structures emerge -- in a faint analogue to the origin of life, or just faint analogues of chemistry/proto-evolution -- the population of patterns evolves with time. It would be really cool to have a crowdsourced set of long-time simulations of such a field. Another important open problem related is how to define a 'Life detector' (in Life). A Life detector is an algorithms that given a pattern and a few generations, tells you how complex, interesting, and 'alive' that pattern is. Very fun and significant problem I believe. Together, this means we can run massive crowdsourced searches to understand environments that tend to evolve interesting patterns (although of course anything close to a bona fide lifeform is probably still far out of reach of our computing power, and might benefit from other kinds of analysis)..

abetusk 4y ago

The basic idea is to use the distance of the gliders to encode information, so when they hit each other allows for an embedding of a Turing machine. I'm no expert here but some basic ideas are that some small number of gliders (two?) can hit each other and produce a "glider gun", allowing for just a few gliders to "upgrade" to producing a steady stream of gliders. There's a "Reverse Caber Tosser" (RCT) structure which has a stationary element that "tosses" a glider back and forth with a structure moving away (or towards?) it, emitting another glider in another direction after each toss, allowing for logarithmic glider/population growth. Another key idea looks to be the "glider producing switch engine" (GPSE) which incorporates the ideas of the RCT with a delay and some other logic? The distances involved are astronomical because they're encoding everything in the distance but they still manage to make it Turing machine equivalent with only 15 gliders. Anyway, I'm floored at the ingenuity of the GoL community. It's as close to programming with butterflies as I've ever seen [0]. [0] https://xkcd.com/378/ https://xkcd.com/378/

hinkley 4y ago
I might have my books mixed up but I believe this idea was a subplot in one of David Brin's early books, The Practice Effect. First Edition: 1984.
- hakuseki 4y ago
  Might it have been Glory Season?
  - hinkley 4y ago
    Might be. It's been a long time. That one is 1993, which still means a 30 year old idea.
biggiemac42 4y ago
To clean up the mistakes in your summary: 4 gliders hit each other to make a stream of gliders. This isn't a gun, because a gun costs more. instead it's a GPSE, which looks like a gun from the barrel end, but has a limit. As it approaches that limit, the RCT mechanism lets another three GPSEs generate an arbitrary list of bits, controlled by the precise location of the first (as a binary number). The final count 15 comes from the naive 4×4 minus one from being able to piggyback one of the constructions off a neighbor to save a single glider. From bits to an embedded turing machine is gol magic that the blog post treats better than my comment could.

anoncow 4y ago

As a lay Comp Sci person I am wondering what this translates into? What implication does this have?

zorked 4y ago
It's pretty cool.
chriswarbo 4y ago
The principle is the same as von Neumann's "universal constructor", so it doesn't really prove anything we didn't know in theory. However, von Neumann's design uses a cellular-automaton with many more rules, and those were specifically chosen to help define that constructor (Langton Loops are a more extreme example of choosing rules to make construction easier). In constrast, the rules for Game of Life (GoL) were chosen to be simple and interesting, not fine-tuned for any particular patterns (for an even simpler set of rules, see the Rule 110 cellular-automaton). We know the GoL is Turing-complete, so it can emulate any computable system; including those other cellular-automata, e.g. von Neumann's universal constructor. Such emulations will typically use a large GoL pattern to represent each emulated cell (e.g. see "life in life"): if we emulate a universal constructor, we can use it to assemble any pattern of those emulated cells. We could also emulate GoL inside some other cellular-automaton, and hence use a universal constructor to assemble any pattern of emulated GoL cells. But the question still remains: can we assemble any pattern of "native" GoL cells? That's what the constructors in the article are doing (at least, for a broad class of patterns). The rest is a matter of "code golf", trying to make the patterns smaller and faster (and indeed feasible to run on a real PC!) https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Langton%27s_loops https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Turing_machine https://conwaylife.com/wiki/Unit_cell https://conwaylife.com/wiki/Unit_cell

squaredot 4y ago

This result is really beautiful! At the same time, it's like GoL has been conquered, and in that it leaves me a little sad. But just a little bit. Congratulations!

soulofmischief 4y ago
This "conquering" is all just proof as to the fundamental nature of the Game of Life. It's not hard to imagine a working system of walking proteins and unzipping DNA structures in light of these findings. It really is beautiful.
- biggiemac42 4y ago
  I think the portion that is fundamental is deeper than game of life itself. Game of life is a rule set with sufficient complexity to get this far, but it isn't the only one. Anything with this class of behavior will support systems including those resembling DNA, the question is at what scale it emerges. If the scale is too big (arguably the scale for the result in this post is too big), it's a less elegant kind of emergence.
  - soulofmischief 4y ago
    Agreed. One aspect of CA which interests me is robustness, the ability of a system to recover from error states. What's been done with GoL is fascinating, but I think the next emergent layer of fascination for me is universal constructors which can handle a certain level of constant distributed noise or interference. A lot of times people just shrug and say, "well this pattern will always be critical/vulnerable in these locations, and cannot be made robust. But to me that opens up the door for entire classes of patterns which measure, embed and repair state of surrounding entities.
- galaxyLogic 4y ago
  Very interesting. A biological cell is a 3-D self-replicating pattern (or is it 2-D rather?). Does GoL give us some insight into the nature of biological cells?

biggiemac42 4y ago

Hi there, I'm the author (of the blog post, not of the achievement itself)! So glad this is spreading. Feel free to ask here or on the post for more clarification if stuff is too unclear

Traubenfuchs 4y ago
How much of advanced GoL is intuition and genius you were born with and how much is math/logic anyone can learn with enough time?
- biggiemac42 4y ago
  Definitely worth trying to learn! As with most topics, it starts out seeming hard to grasp, and then you start naming things and recognizing them. What looks like jargon to an outsider is just a compressed way of communicating. The people in the community are smart and tend to compress their ideas really far which makes the jargon even more extreme. Advanced gol is just getting past that first hurdle of understanding the densely compressed info behind the jargon. And it doesn't ever need to be done for all of the concepts. You can be versed in just one. I started out in a super specialized corner in self constructing spaceships. That said I'm a bit of a whiz in other areas so I can't be used as evidence that it works for everyone..
  - dvgrn 4y ago
    I think the biggest prerequisite for getting good at "advanced GoL" is just an unreasonable amount of patience. Probably I'm a good case in point. I'm definitely not a particularly clever mathematician, but it seems like it's possible to understand any new Life technology just by tinkering with the pieces for long enough. If anyone wants to follow along with that kind of learning process, just start working through the Life textbook that kryptiskt mentioned. (Full disclosure, I'm one of the authors.)
  - isoprophlex 4y ago
    I just want to say that I love everything the GoL community has built and discovered over the years. Big crazy things like this always fill my heart with awe and wonder. Even though in my life, I can't make the time for doing something on the grandiose scale required, I can live vicariously through reading about your sheer dedication and intellectual effort expended.

Rodeoclash 4y ago

Amazing work!

NeoTar 4y ago

Do we have any idea / intuition about what proportion of patterns are build-able? If not on an infinite grid, then some subset (i.e. 100% of 1x1 patterns are build-able, 80% of 3x3 patterns, 60% of 5x5 patterns, etc.)

biggiemac42 4y ago
This is a really good and not at all easy to answer question. The most I can say is that folks earlier this year used some SAT solver equivalent to find notable patterns that cannot be constructed - including a still life and an oscillator https://conwaylife.com/wiki/Unsynthesizable_oscillator_1 https://conwaylife.com/wiki/Unsynthesizable_oscillator_1. This doesn't have much bearing on the probability of constructability for an arbitrary large pattern.
- JKCalhoun 4y ago
  Yeah, I was wondering, with todays computing power, if it were possible to run outrageously large random Life universes and use some sort of software to look for "interesting patterns" (whatever that means). Or are these "discoveries" being done by hand?
  - OscarCunningham 4y ago
    A lot of discoveries have come from 'soup search' where you start with a random 16 by 16 square and let it evolve. We've run over 156 trillion soups https://catagolue.hatsya.com/statistics https://catagolue.hatsya.com/statistics. This tends not no produce complicated machines, but rather small components that can then be engineered into larger patterns.
chriswarbo 4y ago
There are "garden of eden" patterns which can only exist as an initial configuration: there is no pattern which evolves into a garden of eden, hence there can be no constructor capable of building them https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom... If we limit ourselves to glider interactions, the article links to the following patterns which cannot be constructed (including garden of eden patterns): https://conwaylife.com/wiki/Category:Patterns_that_can_not_be_constructed_with_gliders https://conwaylife.com/wiki/Category:Patterns_that_can_not_b...

pastrami_panda 4y ago

This is an awesome article, and Conway would've been incredibly excited about this result. Thanks for sharing!

Zenst 4y ago

Interesting when you think about DNA and how that shapes things. Equally, compression, is this an avenue worth exploring and a whole new way of doing things awaiting to be tapped?

dvgrn 4y ago
Heh, oddly enough, the RCT can probably be better thought of as a way of explosively _decompressing_ a glider construction recipe. There are lots and lots of reasonable-sized recipes for constructing different patterns. When you apply the RCT trick to any of them, the cost in gliders always shrinks to 15, but the pattern's bounding box always expands to something gargantuan. The Life pattern that most evokes DNA and self-replication is another megapattern from several years ago, the 0E0P metacell, which even has a visible "nucleus" for its "DNA": https://conwaylife.com/wiki/0E0P_metacell

ivoras 4y ago

Interestingly enough, the concept of placing gliders at a distance away seems to touch on the relativity of space and time. Here, with space, we are also encoding the time at which a certain pattern (a glider) appears where it's needed. In a rigid system like the GoL, we can't trade space with time easily, since everything happens at a constant speed, but it makes one wonder...

bewresu 4y ago
...if there's a GoL version where time varies somehow¹ with something² ¹ directly? ² amount of activity? mass?
- dvgrn 4y ago
  There have been a lot of GoL variants over the years, but I don't remember running into any attempts to vary the speed of evolution in different locations on the same grid. The idea that all neighbors move to the next tick simultaneously is a fundamental assumption in cellular automata in general. If you try changing that, the optimizations that allow us to simulate CAs at any kind of reasonable speed ... all stop working, pretty much. It's kind of painful even to think about. Which means there are probably very interesting rules out there somewhere, where CAs run faster/slower depending on pattern density -- it's just going to be very tricky to explore that particular search space.
  - westurner 4y ago
    The "superstep" that we practically impose upon simulations of entropy and emergence is out of accord with our modern understanding of non-regularly-quantizable spacetime. The debuggable Von Neumann instruction pipeline precludes "in-RAM computing" which conceivably does converge if consensus-level error correction is necessary.
    - OscarCunningham 4y ago
      The term 'superstep' reminds me of the HashLife algorithm https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife for computing the Game of Life. It computes multiple generations at the same time, and runs at different speeds in different parts of the universe, but only with the purpose of computing CGoL faster, not to introduce any relativity.

Ftuuky 4y ago

How do I dive into this world? Any resources for a complete noob?

OscarCunningham 4y ago
Not necessarily in this order: * Download Golly https://golly.sourceforge.net/ https://golly.sourceforge.net/ and play around drawing random patterns. Have a look at the example patterns. * Have a look around on the LifeWiki https://conwaylife.com/wiki/Main_Page https://conwaylife.com/wiki/Main_Page. Click anything that looks interesting. * Read the free online book https://conwaylife.com/book/ https://conwaylife.com/book/ * Make an account on the forums https://conwaylife.com/forums/ https://conwaylife.com/forums/, or just lurk and see what people are talking about. * Hang out on the Discord https://discord.gg/uA6uaGv3 https://discord.gg/uA6uaGv3

L_226 4y ago

Neat, reminds me of the 22 alpha amino acids that comprise our RNA/DNA.

tromp 4y ago

This is an incredible achievement. The most impressive piece of GoL engineering I've ever seen! Clearly, number of gliders is no longer a good measure of complexity of constructions. Perhaps one should fix a straightforward way to encode a set of gliders by position (e.g. using [1]) and orientation and take the minimum number of bits of such a description. Just one question: > 1274729 – build a DBCA and pass control to it > 192584 – build a new constructor that reads stored data instead of live data > The final 200093 bits get stored in the Binary Storage and Retrieval device, these same 200093 bits are counted below: How come this adds up to 1667406, which is 1615 more than the claimed total of 1665791 bits? [1] https://en.wikipedia.org/wiki/Levenshtein_coding https://en.wikipedia.org/wiki/Levenshtein_coding

biggiemac42 4y ago
Ooh, I appreciate the diligence! The numbers here came from manually fiddling with more granular output from Pavgran's special purpose "profiler" script. One of those steps, where the DBCA assumes control of the bit stream, takes 1615 gliders. I would bet I made a mistake and added it twice, probably to both the DBCA building and the task of the DBCA itself. It belongs in only one of them! I can verify this later.

iamgopal 4y ago

What’s most complex thing achieved in GOL ?

OscarCunningham 4y ago
Probably either this or the 0E0P metacell https://conwaylife.com/wiki/0E0P_metacell https://conwaylife.com/wiki/0E0P_metacell, a large pattern which makes copies of itself in a way that mimics another cellular automaton, or Life itself.

vanderZwan 4y ago

Whenever I read one of these deep dives into GoL achievements, and let me preface this by saying I mean this as a compliment, I feel like I'm reading the extended universe lore on a wiki page for a giant fantasy franchise. It's maths but feels so much more narratively rich than most other mathematics somehow, and the community around it has such a unique subculture vibe to it too.

VikingCoder 4y ago
Have you read "Permutation City"? I'm definitely reminded of it every time.
- jiggawatts 4y ago
  There is a pattern of 15 gliders that encodes a simulation of a universe where your mind is immortal and living in an endless paradise.
  - VikingCoder 4y ago
    Oh well, time to go back to climbing the skyscraper.
OscarCunningham 4y ago
This is the legacy of Conway (who invented Life) and Gardner (who popularised it).
Silverback_VII 4y ago
in my opinion Jeffery Ventrella's clusters are a more promising avenue than Conways GoL. The rules are in comparison very interesting as well: No creation out of nothing, only particles that attract or repel each other. The pattern it generates are pretty amazing as you can see here: https://youtu.be/0Kx4Y9TVMGg https://youtu.be/0Kx4Y9TVMGg
- robertsdionne 4y ago

tiborsaas 4y ago

Absolutely mind blowing result, looking at the video at the bottom is so hard to comprehend there's no human interaction in this besides setting up the 15 gliders. At 1:57 it even looks like someone draws a line casually with a mouse.

isoprophlex 4y ago

I had a particularly hard time grokking the way the semilator works to reduce pattern size. It's a pretty difficult term to google too, being so similar to the word 'simulator'. Does anyone well versed in GoL-ogy care to share a short ELI5? Edit: thanks you people for the explanation, makes sense. Nice hack to make it feasible.

biggiemac42 4y ago
Right, as far as I can tell the term "semilator" was coined for this task, so google won't help. The middle of the RCT pattern where all of the action happens, reads its first bit 2^N generations B.S (before singularity, or before splat, whichever you prefer). Next bit is 2^(N-1) B.S. Next would be 2^(N-2), but this is what the semilator changes. During the franky enormous gap between 2^(N-1) and 2^(N-2) generations B.S, extra spaceships come in at an orthogonal direction. These have two possible configurations, giving equivalent results to either of the possible bit reads. This accelerates the speed of bit reading, and means that N of millions can be emulated by a pattern with N less than 30. Much less initial distance, much less time. The addition of millions of cells of spaceships doesn't make the overall pattern smaller in an informational sense, just in the scale of time and distance between its constituent parts.
OscarCunningham 4y ago
So the full-size pattern works by bouncing a signal back-and-forth between the construction site and an oncoming GPSE. Each time it does this it produces either one or two gliders depending on the positioning of the GPSE. It is these gliders that do the construction. But the 'recipe' contains 1665791 bits, meaning the signal has to bounce back-and-forth 1665791 times. Because the distance to the GPSE halves every time, it would have to start at a distance of 2^1665791, which is impractically large. So instead we only have it bounce back-and-forth a small number of times (26), and insert the other 1665765 bits 'manually' by adding streams of 1665765 spaceships that collide near the construction site.

sagebird 4y ago

Can automated theorem proving software be coaxed into finding recipes for GOL constructions? I would find it interesting trying to formalize notions that we easily perceive into computer-understood definitions. May end up with strange formalizations to make things as orthogonal as possible: IE a beehive is a glider speed zero.

OscarCunningham 4y ago
I have a program called LLS that uses SAT solvers to find patterns with specified properties. https://conwaylife.com/wiki/Logic_Life_Search https://conwaylife.com/wiki/Logic_Life_Search But it only works cell-by-cell, so it can't make big patterns like this.
aidenn0 4y ago
SAT has been used to find many things in GoL. IIRC the first "grandfatherless" pattern was found with one.

kleer001 4y ago

Seeing behind the curtain on this amazing work does nothing but make me think that the universe we're in has to be some kind of higher level cellular automata, somehow.

rotexo 4y ago

As a biologist with nearly no physics knowledge, this sort of work seems to have more in common with setting up quantum computers than it does with thinking about self-replication in living organisms, at least in terms of the lack of robustness to environmental noise. Maybe that is just overly metaphorical thinking on my part.

nneonneo 4y ago
It’s mathematics and computer science, not biology. Nobody is claiming that a setup requiring 2^1500000 units of space to run is anywhere near a realistic simulation of biological processes :) Nevertheless, it’s a fantastic example of how simple rules can give rise to complex systems.
- dvgrn 4y ago
  Yup, the connection to self-replication has showed up mostly in the discussion here, in relation to true self-replicating patterns like the https://conwaylife.com/wiki/0E0P_metacell https://conwaylife.com/wiki/0E0P_metacell -- which does have a few vaguely cell-like attributes. The RCT design is very much a mathematical construct, as opposed to anything with a biological inspiration. And the RCT's ability to construct itself is more of a theoretical afterthought at this point -- the engineering work hasn't been done yet to produce a demo of that kind of thing. The point is well taken, about the fragility of Conway's Life with respect to environmental noise. That topic has also come up here and there in these comments, e.g., https://news.ycombinator.com/item?id=33797799#33800301 https://news.ycombinator.com/item?id=33797799#33800301

pugworthy 4y ago

Imagine in 1970 someone reading Martin Gardner's Scientific American article describing 'John Conway's new solitaire game "life"'. Perhaps the reader played around with graph paper plus pencil and eraser to explore what could be done. "Interesting", they might say. Or, "Fascinating!" even. And then you show them this article. Just imagine how mind blowing it would be to them. Original SciAm article -> https://www.ibiblio.org/lifepatterns/october1970.html https://www.ibiblio.org/lifepatterns/october1970.html

yarnover 4y ago
That was me, reading the original article as a youngster, working out generations on graph paper, etc. The difference is that I have been following the progress of researchers of Life through the years. It’s still astonishing!
- dvgrn 4y ago
  Heh, yes, same here more or less -- I wrote an assembly-code Life program for my family's first personal computer (TRS-80 Model I) in the early 1980s, then mostly forgot all about Life for almost two decades ... until it became possible to search the Internet for "Conway's Life". At that point I was completely floored by how much progress had been made since the last time I was paying attention. Ever since 2001 I've been keeping a close eye on new developments so I don't get surprised like that again.