Forgot your password?
typodupeerror
Math Programming Games

First Self-Replicating Creature Spawned In Conway's Game of Life 241

Posted by Soulskill
from the emergent-gameplay dept.
Calopteryx writes "New Scientist has a story on a self-replicating entity which inhabits the mathematical universe known as the Game of Life. 'Dubbed Gemini, [Andrew Wade's] creature is made of two sets of identical structures, which sit at either end of the instruction tape. Each is a fraction of the size of the tape's length but, made up of two constructor arms and one "destructor," play a key role. Gemini's initial state contains three of these structures, plus a fourth that is incomplete. As the simulation progresses the incomplete structure begins to grow, while the structure at the start of the tape is demolished. The original Gemini continues to disassemble as the new one emerges, until after nearly 34 million generations, new life is born.'"
This discussion has been archived. No new comments can be posted.

First Self-Replicating Creature Spawned In Conway's Game of Life

Comments Filter:
  • Nanites (Score:3, Funny)

    by Pojut (1027544) on Thursday June 17, 2010 @12:28PM (#32603542) Homepage

    They're coming to take over. Sure, of course there are only a few hundred at first...but then those become thousands, then millions, then billions. Soon, we will all be knee deep in this shit.

    lolwut?

    • Re: (Score:3, Funny)

      by jgagnon (1663075)

      And to take care of them we'll create nannites. :p

      (or nanny-ites)

    • Re:Nanites (Score:5, Funny)

      by bunratty (545641) on Thursday June 17, 2010 @02:11PM (#32604766)
      IBM has already developed a high-fidelity 3-D copier. They scrapped the project when they realized they would likely sell only two units.
      • Re:Nanites (Score:5, Interesting)

        by smellsofbikes (890263) on Thursday June 17, 2010 @02:46PM (#32605222) Journal
        That's a superb joke, but if you're bored and want to read some extensions of the idea you should find a copy of Venus Equilateral [wikipedia.org] by George Smith some time. In one of the stories, engineers make (by mistake, basically) a device that can replicate other devices, and then realize it can replicate itself, so they build a few mostly for fun. Since they're on an isolated space station they transmit information about what they've done back to earth and then find out that earth's economy is collapsing because everyone's either duplicating money or duplicating duplication machines and there's no reason to buy anything. Smith explores how that affects the economy for a while (one character's snooty wife has to stop being a socialite and get a job as a nurse, because Smith was basically a 1930's misogynist) and then has his engineers cook up a physical item that contains energy, which the matter duplicator can't duplicate (since it only deals with matter) to act as a new basis for currency. He wrote all this in the 1940's, so, y'know, prior art and all that.
        • Re: (Score:3, Insightful)

          by bunratty (545641)
          Is the "economy collapsing" a good thing or a bad thing? A good thing because everyone has all they want for free? Or a bad thing because now that there's no incentive to pay for products (information, entertainment, ideas) that there's no incentive to create new products (information, entertainment, ideas)?
          • Re:Nanites (Score:5, Insightful)

            by selven (1556643) on Thursday June 17, 2010 @03:44PM (#32605908)

            A good thing, I say. Poverty will be eradicated, Wall Street will disappear into uselessness and everyone will have 16 hours a day of time to do whatever they want. People will want to create new stuff, even lacking any normal incentive, simply out of boredom.

            • by bunratty (545641)
              Let's just think through the repercussions of replicator technology a bit. Just because material goods are free does not mean services will be free. To get medical treatment, you would need money. To get money, you would need to do something that would enable you to get money, such as provide some kind of service to others. I don't think that just because our basic material needs would be met that we would have 16 hours a day to do what we want. Our jobs would simply change from producing goods to providing
              • Re: (Score:3, Insightful)

                by geekoid (135745)

                "To get medical treatment, you would need money. "

                No, you need something the doctor values. there is a big difference there. A doctor can replicate in car, boat, tv,, gold clubs whatever. Just like everyone else. So money, even the idea of money, looses its value.

                OTOH, he may want services., or just do it because they like to help people.

                Logically, this technology would mean that all physical items the doctor needs to treat people would be free. so his cost go down a lot.

                Many service wouldn't be needed. foo

            • Re: (Score:3, Interesting)

              by geekoid (135745)

              Poverty will be eradicated

              no, it will change because the definition of wealth will change.
              Original work, labor, land. These will be the measure of wealth.

              "Wall Street will disappear into uselessness and "

              No, it will change to be used for people to by and sell shares of things that can't be duplicated.
              Original art*, manual labor and so on. When you want landscape done, what do you use to motivate people to do the work for you? A sky scraper? Barter? Land?

              "will have 16 hours a day of time to do whatever they

              • Re: (Score:3, Interesting)

                by selven (1556643)

                Poverty will be eradicated

                no, it will change because the definition of wealth will change.

                Poverty is not about being wealthy. As Wikipedia puts it, "poverty means being unable to afford basic human needs". If the basic human needs are provided for everyone, regardless of the social structure that emerges afterward there will by definition be no poverty.

                Why do you assume they won't be beholden to a landlord?

                Because land outside of cities is very cheap, and will get even cheaper if the demand to use it for food production disappears. Since the main point of living in cities is not having to drive 3 hours to work, and work will no longer be a part of m

            • Re: (Score:3, Interesting)

              by vrmlguy (120854)

              A good thing, I say. Poverty will be eradicated, Wall Street will disappear into uselessness and everyone will have 16 hours a day of time to do whatever they want. People will want to create new stuff, even lacking any normal incentive, simply out of boredom.

              Unfortunately, history disagrees. The Samoan islands were a utopia; food was freely available by wading out into the bay and shelter was almost unnecessary due to the clement weather. So, everyone's favorite pastime was fucking and drowning the excess babies. Compare this to the Mediterranean, where earlier ecological collapse had ruined the farmlands and you needed walls to keep out hostile neighbors. The upper class'es favorite pastime? Natural philosophy.

          • Given that, in this case, "economy collapsing" seems to be a synonym for "post-scarcity economy breaking out", I'd have to go with "good".

            Even if Home Taping Is Killing Music(tm), there would be about a billion people being too busy having enough to eat for the first time in their lives to give a fuck. (Plus, of course, the "think of the poor artists" argument kind of breaks down when the artists are all sprawled out around their post-scarcity-cocaine-replicator, having a grand old time...)

            Unless you
            • by jackbird (721605)
              I dunno, while The Diamond Age and Down and Out in the Magic Kingdom were interesting places to visit, I (and most of the characters) wouldn't want to live there. Of course both of those societies had haves and have-nots based on resources that continued to be scarce (raw matter/energy in one and human regard in the other).
              • To be fair, The Diamond Age was not truly a post-scarcity society because people had to pay for the energy used for duplication (hence the scene where after the kids had created all this stuff they had to stick it all back in the compiler and destroy it again because their mom couldn't pay the bill for what they'd made.) So, what they had was an everything-available-for-a-reasonable-price society, a la iTunes. Unfortunately for our future, I think that's the most likely result if/when we DO manage to make
          • Good thing (Score:3, Interesting)

            by mangu (126918)

            Is the "economy collapsing" a good thing or a bad thing? A good thing because everyone has all they want for free? Or a bad thing because now that there's no incentive to pay for products (information, entertainment, ideas) that there's no incentive to create new products (information, entertainment, ideas)?

            If not being paid removes the incentive to create new products, then how do you explain Linux, or any other Free Software?

            Not getting paid to do it means that products, entertainment, information, ideas

        • Part of that reality is coming true...

          http://hubpages.com/hub/This-affordable-3D-printer-can-print-itself [hubpages.com]

  • by Anonymous Coward

    I thought someone had come up with a glider gun which created & shot out other glider guns... this was about 20 years ago from my memory...

    • by emurphy42 (631808) on Thursday June 17, 2010 @12:35PM (#32603638) Homepage
      TFA mentions glider guns - they're indeed an old discovery, but they just create and shoot out gliders. This thing actually creates copies of itself.
      • by durrr (1316311)
        If a glider is mutated, it most likely is not viable and dies. Perhaps the gemini have a tolerance for mutations, being a evolution-compatible replicator.
    • by Pojut (1027544)

      Sort of like a vending machine that sells other vending machines?

      With apologies to Mitch Hedberg (RIP)

      • by hitmark (640295)

        reprap?

    • Re: (Score:3, Interesting)

      http://en.wikipedia.org/wiki/Evoloop [wikipedia.org]

      Not exactly Conway's game of life, but similar concept, and it is certainly possible to encode this in Conway's game of life.
    • by ukyoCE (106879)

      You would need a glider gun that shoots out more glider guns.

      Which would be hella fun, actually.

      • Re: (Score:3, Informative)

        You would need a glider gun that shoots out more glider guns.

        Which would be hella fun, actually.

        There is a breeder pattern that uses a set of ships to produce a stream of glider guns, but (being regular Gosper Glider Guns) they don't move once they've been created.

        The applet on Paul Callahan's page [math.com] has it stored as one of the example patterns.

        • by ukyoCE (106879)

          That's an awesome pattern for sure. But to be a self-replicating pattern, the glider-gun breeder would need to breed glider-gun breeders. (did I get that right?)

          I still can't tell from the comments if the pattern in the article is *actually* self-replicating, or if it just destroys itself while creating a single copy. If that's all it does, this doesn't sound any more remarkable than your basic glider, which also "replicates and destroys itself" as it moves across the screen.

          What is actually more interes

          • I wasn't offering the breeder pattern as an example of self-replication, just as an example of a "glider gun gun". As for Wade's pattern... Well, I've been running the simulation for over an hour and it's barely past generation 10M (and the actual replication isn't supposed to be complete until almost 40M). Perhaps the construction outpaces the destruction in such a way that we do have two full copies of the original pattern, eventually.

            Wolfram did seem impressed by Wade's pattern; he just said that the int

  • by Max Romantschuk (132276) <max@romantschuk.fi> on Thursday June 17, 2010 @12:33PM (#32603612) Homepage

    Fortunately the glider gun is already discovered, so at least we have a means of killing this new self replicating entity. ;)

    • by Cecil (37810)

      Except gliders are the very fuel it uses to grow and replicate! We're DOOMED!

  • by Tacvek (948259) on Thursday June 17, 2010 @12:37PM (#32603658) Journal

    From the article:

    In fact, this is arguably the single most impressive and important pattern ever devised.

    Really? Not the universal Turing machine pattern, or the pattern that emulates the game of life itself? Those both seem more impressive to me.

    • I don't see whats impressive about it at all - but then again, I don't really see whats going on.

      I mean, we've programmed robots that can build themselves if you give them the materials. I figured that was self replicating, and that was done a couple years ago.

      So whats going on exactly thats impressive in this simulation?

      • by ari_j (90255)
        The impressive part seems to me to be that this pattern in Conway's Game of Life makes a copy of itself within the rules of the game. A robot designed to build a copy of itself does so within the much more flexible rules of real-world physics.

        Then again, maybe the impressive thing is that there are people out there with enough time on their hands to run 34 million iterations of the Game of Life with enough different patterns to find this one.
    • by SomeJoel (1061138) on Thursday June 17, 2010 @01:02PM (#32603986)

      From the article:

      In fact, this is arguably the single most impressive and important pattern ever devised.

      Really? Not the universal Turing machine pattern, or the pattern that emulates the game of life itself? Those both seem more impressive to me.

      Well, he did say "arguably", which is arguably the worst weasel word in the history of mankind.

      • by GooberToo (74388)

        Well, he did say "arguably", which is arguably the worst weasel word in the history of mankind.

        Or arguably, it means you understand both sides of the coin and are open to discussion. No weaseling required.

      • by smellsofbikes (890263) on Thursday June 17, 2010 @02:59PM (#32605410) Journal

        From the article:

        In fact, this is arguably the single most impressive and important pattern ever devised.

        Really? Not the universal Turing machine pattern, or the pattern that emulates the game of life itself? Those both seem more impressive to me.

        Well, he did say "arguably", which is arguably the worst weasel word in the history of mankind.

        FUNNY! But at the same time, I think weasel words are critically important. Science should be based on weasel words: may, could, indicates, possibly, probably, likely. When you hear someone saying non-weasel words: is, will, shall, always -- you're either talking to God or to someone who talks to God. Mathematicians, for instance, which is why they can say that in base 10, two plus two IS four. But past that, I'm all for weasel words.

    • by ukyoCE (106879)

      I've heard about the Turing machine pattern, do you have a link about the pattern that emulates the game itself?

      I searched some but only found your comment and various crawler-spam "fact" sites that crawled a page briefly mentioning such a pattern exists. :P

  • If a new pattern is created while an old one is destroyed, it's not self-replicating; it's just moving.
    • Re: (Score:2, Insightful)

      by Binder (2829)

      You mean like a human giving birth to another human and then dying off?

      • by russotto (537200) on Thursday June 17, 2010 @01:01PM (#32603984) Journal

        You mean like a human giving birth to another human and then dying off?

        If every time one human was born, an identical human died, it would be like that.

        • by Anonymous Coward on Thursday June 17, 2010 @01:12PM (#32604144)

          This is slashdot -- some people here think that's actually how it works, while many more think births are all faked by the government, and still more are arguing for more openness in the early stages of the process.

          • Re: (Score:2, Insightful)

            by Migala77 (1179151)

            still more are arguing for more openness in the early stages of the process.

            The internet is for 'more openness in the early stages of the process'!

            • still more are arguing for more openness in the early stages of the process.

              The internet is for 'more openness in the early stages of the process'!

              So that explains all the porn?

      • by ukyoCE (106879)

        Yes. Humans wouldn't be terribly interesting creatures if that's all they could do, would they? All we'd have in the world is 1 human, "Eve", who keeps dying after birthing a new Eve.

        Now a human giving birth to *multiple* humans and then dying off? THAT is what makes life "life". I'm pretty sure this is the expected definition of self replication - an entity creating multiple copies of itself before dying. This gives us robust exponential growth. In the Eve scenario, as soon as any one Eve dies before

    • by porter235 (413926) on Thursday June 17, 2010 @01:31PM (#32604356)

      Yep, and if you read the entry on LifeWiki [conwaylife.com] you would see they agree with you.

      "It displaces itself by 5120 cells vertically and 1024 cells horizontally every 33,699,586 generations."

  • some alien 43 dimensional child's entry in the local science fair

    "look: i've created self-replicating life based on a few simple rules!"

    and the judge says: "but it's only 4 dimensions, and one of the dimensions is only one way. shoddy, very simplistic, not a good middle school level effort"

    to which the alien's mom says: "don't worry honey, next year we'll put baking soda and vinegar in a paper mache cone and simulate a volcano!"

    and the alien child says: "that's ok mom, i don't like science anymore, i want to be a ranch hand. bye bye, little universe critters, i always thought you were cute"

    and then he pulls the plug on his simulation, and trillions of animal, plant, and human lives on earth and septillions of lives on the other inhabited planets cease to exist in a puff

  • by JoshuaZ (1134087) on Thursday June 17, 2010 @12:53PM (#32603864) Homepage

    The Game of Life is one of the first cellular automata discovered that had simple rules but complicated behavior. The rules very roughly mimic bacterial growth. One has an infinite lattice grid, and some starting set of cells on the grid are designated as alive (every cell on the grid is either alive or dead). Each new generation is made by the following four rules: Any live cell with fewer than two live neighbors dies. Any living cell with more than three live neighbors dies. Any living cell with two or three live neighbors lives on to the next generation. Any dead cell with three live neighbors (exactly) becomes a live cell. http://en.wikipedia.org/wiki/Conway's_Game_of_Life [wikipedia.org]

    The Game of Life is mathematically interesting because it can be shown to be Turing complete. That is, if you have a process that tells you whether any given starting configuration will eventually dieout then you can answer whether any given computer program will eventually halt. In general, there's a theorem known as the Turing Halting Theorem which says that no general procedure exists to do that for all programs.

    Prior to the work in TFA, there were known configurations called "gliders" which could replicate themselves as they moved across the grid, but they only left the same number of copies. There were also configurations which could spawn gliders (called glider guns). However, no configuration that was actually self-replicating in the sense of spawning more copies of itself was known. This work by Andrew Wade shows how to make configurations that do self-replicate. His original announcement is at http://conwaylife.com/forums/viewtopic.php?f=2&t=399&start=0 [conwaylife.com] and the actual configuration can be found at https://docs.google.com/leaf?id=0B9e96aFfebqqZmY5NjBkYjctY2ViNi00NmJlLTgwZDAtNmU5OTQwYjc1OWQ0&hl=en&pli=1 [google.com] Thus, this very simply system is still showing itself to have surprising and interesting behavior 30 years after the fact.

    Als

    • by Ether (4235) on Thursday June 17, 2010 @01:45PM (#32604486)

      Turing-complete means that it is able to perform all of the functions of a universal Turing machine, not that it is able to solve the Turing halting problem; a Turing-complete language (or system) by definition is unable to solve the halting problem expressed within that system.

    • The Google Docs page with the Gemini.zip file is not allowing any more downloads right now. Here [conwaylife.com] is another link with more info about Gemini and an alternate download hosted on drop.io. Follow the instructions on page 2 of the original article to set it up.
    • by vanyel (28049) *

      Sorry, the operation could not be performed. Please try again later.

      You've reached the bandwidth limit for viewing or downloading files that aren't in Google Docs format. Please try again later.

      It's pretty bad when Google gets slashdotted!

  • by Rockoon (1252108) on Thursday June 17, 2010 @12:58PM (#32603928)
    My favorite CA is WireWorld. The designs in the CA look and behave like circuit boards. People have designed some very complex "computers" in it.

    WireWorld on Wikipedia [wikipedia.org]

    This flash-based wireworld app is listing prime numbers. [rezmason.net]
    • by schon (31600)

      Awesome!

      I remember reading about this 20 years ago in (IIRC) Omni.. it was an introduction to circuitry (it used the rules as an example to demonstrate logic gates.) I didn't know it had a name, and while I always thought it would be a cool thing to code (now that I can) I'd never thought someone had actually done it... thanks for the links! :)

    • by drinkypoo (153816)

      Am I supposed to do anything but hit play on the prime number generator? It loads for me, and the counter in the corner of the screen goes up, but nothing happens.

      • by Rockoon (1252108)
        It takes a few hundred thousand iterations between each of the early primes.
  • The article has steps to reproduce this, but does anyone have a video or animated gif or something for those of us who are interested, but not this interested?

    I just copied the text to illustrate the steps involved, for those unfamiliar with how articles work the article has more information along with the links.

    See Gemini in action

    You can run Gemini on your own computer: just follow these simple instructions.

    First, install Golly, a Game of Life simulator, by downloading and unzipping this folder from Sourc

  • What?

    That sentence sounds like bullshit inserted to make the story appealing to people who aren't interested in the maths. Like the virus reference in the start. "Ooh, self-replicating; it's like DNA." It's the same thing that makes quantum physicists groan when the word "teleportation" is mentioned.

    This is a fascinating pattern, but there is nothing magical, otherworldly or philosophical about it.

The flow chart is a most thoroughly oversold piece of program documentation. -- Frederick Brooks, "The Mythical Man Month"

Working...