[HN Gopher] Building arbitrary Life patterns in 15 gliders
___________________________________________________________________
Building arbitrary Life patterns in 15 gliders
Author : mikro2nd
Score : 486 points
Date : 2022-11-30 07:04 UTC (15 hours ago)
(HTM) web link (btm.qva.mybluehost.me)
(TXT) w3m dump (btm.qva.mybluehost.me)
| isoprophlex wrote:
| 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 wrote:
| 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 wrote:
| 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.
| rotexo wrote:
| 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 wrote:
| 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 wrote:
| 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
| -- 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
| pugworthy wrote:
| 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
| yarnover wrote:
| 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 wrote:
| 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.
| snoopy_telex wrote:
| Amazing accomplishment! If I didn't know better, this could have
| been in the next bobiverse book!
| pastrami_panda wrote:
| This is an awesome article, and Conway would've been incredibly
| excited about this result. Thanks for sharing!
| NeoTar wrote:
| 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.)
| chriswarbo wrote:
| 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_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_b...
| knome wrote:
| I wonder if you could bypass this with a level of
| indirection.
|
| If the GoL wizards can construct an expanding and initially
| configurable 'GoL in GoL' grid [1], they could configure the
| 'garden of eden' as the initial configuration for their 'GoL
| in GoL' simulation.
|
| It's not the same thing, of course, but it would allow you to
| run Garden of Eden patterns still starting with just your
| initial 15 gliders.
|
| To construct a garden of eden pattern, you must first
| construct the universe :)
|
| [1] similar to https://www.youtube.com/watch?v=xP5-iIeKXE8
| chriswarbo wrote:
| Sure, we can build them with "meta cells"; but that's just
| emulation (the same way a SNES emulator doesn't make my
| laptop a SNES).
|
| We already have GoL turing machines (with "tape factories"
| that travel faster than the read/write head); we could
| likewise use those to emulate GoL with arbitrary input,
| just by setting up an appropriate "tape". The result is far
| less pretty though ;)
|
| I touched on this in a sibling comment:
| https://news.ycombinator.com/item?id=33799084
| OscarCunningham wrote:
| There exists an 'orphan' pattern that cannot arise in any
| configuration after the first generation. When we look at large
| patterns, the proportion of them that contain an orphan tends
| to 1.
|
| On the other hand the smallest known orphan is 12 by 8, and we
| also know that all still lifes (unchanging patterns) with up to
| 21 cells can be built.
| enkid wrote:
| 21 cells would be a 3 by 7?
| OscarCunningham wrote:
| Gardens of Eden can be arbitrary patterns, whereas only the
| 21-cell _still lifes_ are known to be constructible.
| enkid wrote:
| Ok, but what do you mean by a "still life" of 21 cells?
| Is that a rectangle in a larger field or is it an
| arbitrary set of cells?
| OscarCunningham wrote:
| A pattern with 21 live cells in any bounding box.
| enkid wrote:
| Thanks for answering!
| dvgrn wrote:
| (Not just any such pattern, though -- a still life also
| means that it doesn't change when you evolve it according
| to Life rules.)
| OscarCunningham wrote:
| Also we can only do the _strict_ still lives (i.e. those
| which are connected https://conwaylife.com/wiki/Still_lif
| e#Strict_still_lifes). We can't necessarily put down a
| 10-cell still life and an 11-cell still life near to each
| other.
| dvgrn wrote:
| Heh, not _necessarily_ , that's true, in the sense that
| all the possible arrangements haven't been tested and
| shown to be constructible.
|
| On the other hand, pseudo-still-life and quasi-still-life
| arrangements are much easier to construct on average than
| strict still lifes with the same number of cells.
|
| I think the consensus is that someone _could_ figure out
| how to construct any given stable 21-bit configuration.
| The non-strict cases are just a bit too numerous and not
| interesting enough, so nobody has gone through and
| formally checked them off the list.
| dvgrn wrote:
| If you want to see what these 21-bit still lifes look
| like, their glider construction recipes are all stored
| online, on Catagolue (no, that's not a misspelling):
|
| https://catagolue.appspot.com/census/b3s23/synthesis-
| costs/x...
| biggiemac42 wrote:
| 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. This
| doesn't have much bearing on the probability of
| constructability for an arbitrary large pattern.
| JKCalhoun wrote:
| 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 wrote:
| 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. This tends not no
| produce complicated machines, but rather small components
| that can then be engineered into larger patterns.
| iamgopal wrote:
| What's most complex thing achieved in GOL ?
| OscarCunningham wrote:
| Probably either this or the 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.
| anoncow wrote:
| As a lay Comp Sci person I am wondering what this translates
| into? What implication does this have?
| zorked wrote:
| It's pretty cool.
| chriswarbo wrote:
| 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_construc...
|
| https://en.wikipedia.org/wiki/Langton%27s_loops
|
| https://en.wikipedia.org/wiki/Rule_110
|
| https://conwaylife.com/wiki/Turing_machine
|
| https://conwaylife.com/wiki/Unit_cell
| tiborsaas wrote:
| 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.
| squaredot wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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?
| dvgrn wrote:
| Definitely! It's hard to summarize that insight in any kind
| of concise way, though ... The Game of Life universe seems
| a bit too "fragile" to allow for the kind of emergent
| complexity that real-world physics supports. We can build
| self-constructing things like the
| https://conwaylife.com/wiki/0E0P_metacell , but if anything
| gets slightly out of place, the usual result is a truly
| horrific catastrophic explosion.
|
| Conway's Life design work is kind of like building robots
| out of masses of subcritical uranium. Everything's fine
| until two robots unexpectedly bump into each other... which
| means you have to start out with everything very carefully
| balanced, such that that never happens.
|
| So I guess one fairly obvious insight is that real-world
| physics supports more reliable and less explosive low-level
| structures than Conway's Life does, and those low-level
| structures can then safely be used as the basis for new
| levels of organization -- atoms -> molecules -> DNA ->
| bacteria -> eukaryotic cells -> multicellular organisms ->
| colonies of organisms -> ecosystems.
|
| It's not clear how those higher levels of organization
| would work in Conway's Life. If they're possible, then they
| seem to be far beyond our current ability to simulate them
| -- though there's some recent research vaguely along these
| lines, about self-replicators that might be able to exert
| some control over the space around them:
|
| https://conwaylife.com/forums/viewtopic.php?f=2&t=5364
| galaxyLogic wrote:
| Fascinating
| OscarCunningham wrote:
| There are still plenty of open problems! Here are some of my
| favourites:
|
| * Is there an oscillator of every possible period? (We have
| them all except 19 and 41.)
|
| * If you start off the entire plane in a random starting state,
| does its density tend to a limit as time goes to infinity?
|
| * Is there a 'phoenix' oscillator, in which every live cell
| dies every generation, of period greater than 2?
|
| * Can every pattern be destroyed by bombarding it with gliders?
|
| * Is there an indestructible pattern?
|
| At the moment people are working on building a spaceship which
| is only 1 cell tall in its starting state:
| https://conwaylife.com/forums/viewtopic.php?f=2&t=2040.
| Strilanc wrote:
| I'd be surprised if there was a computable density limit for
| the random plane, just because the system is Turing complete
| so the answer could easily end up being like Chaitin's
| contant where it depends on halting problems. For example,
| note that an infinite random plane will contain, with
| probability 1, purely-by-chance prebuilt artificial
| intelligences with goals like "maximize number of blinkers in
| the plane". Though I guess it's also an open question if such
| a system could even survive and spread, as opposed to just
| getting eventually crushed by the surrounding noise.
| OscarCunningham wrote:
| Right, but I'm hoping it might be possible to prove that
| the limit _exists_ (even if it 's an uncomputable number),
| as opposed to some oscillating behaviour where the density
| infinitely often goes up to 70% and then back down to 30%
| for example.
| isoprophlex wrote:
| If it can be proven that there are no indestructible
| patterns, your AI can clean up everything around it!
|
| (... and encounter other AIs that act as hegemonising
| swarms, eg. that populate the plane with copies of
| themselves)
| biggiemac42 wrote:
| 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
| Grustaf wrote:
| Almost everything was unclear to me, but then I'm not familiar
| with the Game of Life lingo. Perhaps it would make sense to
| write a version that the educated public can understand, even
| without any Life background?
| phkahler wrote:
| Funny. I first saw life over 40 years ago. I saw some crazy
| objects creates in my college days. I've seen occasional
| articles about breakthroughs over the years. Understanding
| gliders and spaceships has been my foundation to grok
| everything since. Being able to think in the abstract was a
| key to understanding this article for me, but without a few
| concrete foundational concepts... I stopped a few times
| reading it to laugh at how absurdly abstract and full of
| jargon it is. Completely meaningless techno-babble to the
| uninitiated. How much of my own specialization sounds so
| opaque to outsiders? Maybe all of it ;-)
| biggiemac42 wrote:
| I would say "the educated public" is already the target
| audience for my blog. Game of life topics are notoriously
| hard to disentangle from their jargon, and I went to some
| effort here but needed to balance that against the goal to
| remain accurate.
|
| My hope is that by reading only the amount of background on
| the blog already in the Waterbear post (referenced
| immediately in the introduction), you have all you need to
| grok the post. But that's certainly an optimistic hope, and
| maybe unfounded.
| a_t48 wrote:
| No questions, just "zig" saying hi :) Nice article.
| Traubenfuchs wrote:
| 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?
| kryptiskt wrote:
| I can recommend the recent book "Conway's Game of Life:
| Mathematics and Construction" (downloadable free at
| https://conwaylife.com/book/), it starts gently and builds up
| to these kind of constructions (minus what has been
| discovered in the last year or so).
| biggiemac42 wrote:
| 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..
| isoprophlex wrote:
| 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.
| dvgrn wrote:
| 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.)
| kimburgess wrote:
| To be fair, that's the definition of jargon. Using domain
| specific language is something that's universal - it's a
| compression technique you see any domain where there's a
| need to communicate dense information. Abstraction affords
| precision, not ambiguity.
| Zenst wrote:
| Do you see this as a form of geometric compression in the
| future?
| dvgrn wrote:
| It's a bit hard to see how this RCT trick could be useful for
| reducing anything besides the number of gliders.
|
| RCT is basically one very unreasonable end of a wide
| spectrum: you can use a very small number of gliders to build
| something, as long as you're content to have the construction
| take a ridiculously long time. Conversely, you can build that
| same thing in a lot less time, but it will take a lot more
| gliders.
| geysersam wrote:
| Also, even if the maximum number of gliders is fixed (15),
| that does not imply any limit on the amount of information
| needed to store their positions.
|
| The glider positions might very well require more storage
| than the desired pattern itself.
| dvgrn wrote:
| That's definitely completely true. We can specify the
| relative positions of the initial gliders at each of the
| three corners of the RCT pattern in just a few dozen
| bytes.
|
| But the number that says how far apart those corners are
| from each other has very roughly half a million digits.
| The exact number depends on exactly what pattern is being
| encoded by the RCT pattern -- I think the example
| construction of Alan Hensel's decimal counter pattern
| needs somewhere around a 450,000-digit number.
|
| There are some optimizations underway to decrease that
| number by a few percentage points, but it's always going
| to be a very big number!
| eurasiantiger wrote:
| 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 wrote:
| 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)
| biggiemac42 wrote:
| 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 wrote:
| 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#Spa
| ceship_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 wrote:
| True. I was thinking about spaceships and other oscillating
| movers.
| dvgrn wrote:
| 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 wrote:
| To be honest, GoL isn't quite as interesting as
| continuous-valued CAs -- the latter break into quantum
| field territory.
| vanderZwan wrote:
| 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.
| Silverback_VII wrote:
| 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
| robertsdionne wrote:
| Also "Lenia": https://en.wikipedia.org/wiki/Lenia
| https://www.youtube.com/watch?v=HT49wpyux-k
| OscarCunningham wrote:
| This is the legacy of Conway (who invented Life) and Gardner
| (who popularised it).
| VikingCoder wrote:
| Have you read "Permutation City"? I'm definitely reminded of it
| every time.
| jiggawatts wrote:
| 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.
| Ftuuky wrote:
| How do I dive into this world? Any resources for a complete noob?
| OscarCunningham wrote:
| Not necessarily in this order:
|
| * Download Golly 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. Click anything that
| looks interesting.
|
| * Read the free online book https://conwaylife.com/book/
|
| * Make an account on the forums https://conwaylife.com/forums/,
| or just lurk and see what people are talking about.
|
| * Hang out on the Discord https://discord.gg/uA6uaGv3
| kleer001 wrote:
| 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.
| pfortuny wrote:
| This is awesome. This result would fit perfectly well in
| Wolfram's NKS. The next question is... is this the minimum?
| rrobukef wrote:
| Can it construct itself as some giant spaceship / oscillator?
| pfortuny wrote:
| Well, no idea.
| biggiemac42 wrote:
| 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.
| dvgrn wrote:
| 15 is probably not the minimum. There are some ideas floating
| around for getting down to 14, and some wilder ideas that might
| get to 13 or 12.
|
| Below that we'd need some significantly different mechanism
| that nobody has thought of yet. It doesn't seem likely that
| anyone will be able to _prove_ that universal construction is
| impossible with a single-digit number of gliders -- but if a
| solution exists it might take an omniscient being to find it.
|
| ... Or maybe some clever hacker will figure it out tomorrow!
| That 's what happened to get us to the current minimum. We were
| stuck at a minimum of 32 for quite a while, until Daniel Vargas
| (MathAndCode) suddenly showed up with a new idea.
| OscarCunningham wrote:
| We've checked every 3 glider collision. So our bounds on 'God's
| Number' are 4 <= N < 16.
| Rodeoclash wrote:
| Amazing work!
| Zenst wrote:
| 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 wrote:
| 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
| L_226 wrote:
| Neat, reminds me of the 22 alpha amino acids that comprise our
| RNA/DNA.
| sagebird wrote:
| 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.
| aidenn0 wrote:
| SAT has been used to find many things in GoL. IIRC the first
| "grandfatherless" pattern was found with one.
| OscarCunningham wrote:
| I have a program called LLS that uses SAT solvers to find
| patterns with specified properties.
| https://conwaylife.com/wiki/Logic_Life_Search But it only works
| cell-by-cell, so it can't make big patterns like this.
| tromp wrote:
| 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
| biggiemac42 wrote:
| 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.
| ivoras wrote:
| 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 wrote:
| ...if there's a GoL version where time varies somehow1 with
| something2
|
| 1 directly?
|
| 2 amount of activity? mass?
| dvgrn wrote:
| 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 wrote:
| 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 wrote:
| The term 'superstep' reminds me of the HashLife algorithm
| 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.
| hansworst wrote:
| Well, there is SmoothLife (e.g. https://www.arxiv-
| vanity.com/papers/1111.1567/#S4) where the time step is
| also made continuous. I suppose you could extend this so
| that this isn't some uniform value across the entire space,
| but instead a value that is constantly recomputed based on
| neighbourhood density.
| andrepd wrote:
| How does it "touch on relativity of space and time"?
| dvgrn wrote:
| I think that was just saying "more space between initial
| gliders implies a longer time needed to complete
| construction". There's no Einsteinian relativity to be found
| here.
|
| (A Doppler effect does show up in Conway's Life sometimes,
| but that's about as far as we get with analogies to the
| physical universe...!)
| westurner wrote:
| How nonlocal are the entanglements in Conway's game of
| cellular automata, if they're entanglements with symmetry;
| conservation but emergence? TIL about the effect of two
| Hadamard gates upon a zero.
|
| Quantum discord:
| https://en.wikipedia.org/wiki/Quantum_discord :
|
| > _In quantum information theory, quantum discord is a
| measure of nonclassical correlations between two subsystems
| of a quantum system. It includes correlations that are due
| to quantum physical effects but do not necessarily involve
| quantum entanglement._
|
| From "Convolution Is Fancy Multiplication"
| https://news.ycombinator.com/item?id=25194658 :
|
| > _FWIW, (bounded) Conway 's Game of Life can be
| efficiently implemented as a convolution of the board
| state: https://gist.github.com/mikelane/89c580b7764f04cf73b
| 32bf4e94... _
|
| Conway's Game is a 2D convolution; without complex phase or
| constructive superposition.
|
| Convolution theorem:
| https://en.wikipedia.org/wiki/Convolution_theorem :
|
| > _In mathematics, the convolution theorem states that
| under suitable conditions the Fourier transform of a
| convolution of two functions (or signals) is the pointwise
| product of their Fourier transforms. More generally,
| convolution in one domain (e.g., time domain) equals point-
| wise multiplication in the other domain (e.g., frequency
| domain). Other versions of the convolution theorem are
| applicable to various Fourier-related transforms._
|
| From _Quantum_ Fourier transform:
| https://en.wikipedia.org/wiki/Quantum_Fourier_transform :
|
| > _The quantum Fourier transform can be performed
| efficiently on a quantum computer with a decomposition into
| the product of simpler unitary matrices. The discrete
| Fourier transform on 2^{n} amplitudes can be implemented as
| a quantum circuit consisting of only O(n^2) Hadamard gates
| and controlled phase shift gates, where n is the number of
| qubits.[2] This can be compared with the classical discrete
| Fourier transform, which takes O(n*(2^n)) gates (where n is
| the number of bits), which is exponentially more than
| O(n^2)._
| [deleted]
| mannykannot wrote:
| Far from being relativistic, it is a miniature simulated
| universe with a rigid flat geometry and a universal clock. it
| is interesting precisely because it is very simple and yet
| permits remarkably complex events.
| abetusk wrote:
| 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/
| biggiemac42 wrote:
| 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 4x4 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.
| robertsdionne wrote:
| It's like how a Turing machine tape can be represented by two
| natural numbers (or even a single natural number via
| interleaving).
| dvgrn wrote:
| The reference that comes to mind for me is something out of
| one of Martin Gardner's _Aha! Insight_ books from decades ago
| -- the idea of encoding something like the Encyclopedia
| Britannica into one big long bitstring, then converting it
| into a fraction... and putting one single very careful mark
| on a stick to represent that fraction.
|
| The difference is that where the real world doesn't allow for
| storing anywhere near that level of precision in a mark on a
| stick, the Conway's Life universe is considered to be
| unbounded, so there's as much room as we need to implement
| this RCT trick.
| hinkley wrote:
| 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 wrote:
| Might it have been Glory Season?
___________________________________________________________________
(page generated 2022-11-30 23:02 UTC)