Slashdot Mirror
First Self-Replicating Creature Spawned In Conway's Game of Life
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.'"
Fortunately the glider gun is already discovered, so at least we have a means of killing this new self replicating entity. ;)
.: Max Romantschuk
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.
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.
Stylish sheet to fix many problems in Slashdot's D3: https://gist.github.com/801524
Self Replicating post! :-P :-P :-8
Self Replicating post!
Self Replicating post!
uh oh mutation...
OMG!!... What have I done... it is already mutating and evolving.
;-D
Elf Replicating Ghost
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
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
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
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 and the actual configuration can be found at https://docs.google.com/leaf?id=0B9e96aFfebqqZmY5NjBkYjctY2ViNi00NmJlLTgwZDAtNmU5OTQwYjc1OWQ0&hl=en&pli=1 Thus, this very simply system is still showing itself to have surprising and interesting behavior 30 years after the fact.
Als
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
This flash-based wireworld app is listing prime numbers.
"His name was James Damore."
And doesn't a glider do that?
Reading in between the lines of the article, it sounds like this thing manages to create the copy before the destruction of the original is complete, unlike a glider which is basically moving itself. But it seems a fairly arbitrary distinction, since that destruction is going to happen and it's not going to reverse itself.
Perhaps the trick is that this thing can _teleport_ itself a few cells away, without passing through the intervening space, but again, that seems kind of an arbitrary and unimportant distinction.
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.
If I understand correctly, it creates two copies while self-destructing in the process. So it is, indeed, replicating.
Yep, and if you read the entry on LifeWiki you would see they agree with you.
"It displaces itself by 5120 cells vertically and 1024 cells horizontally every 33,699,586 generations."
That's obviously intelligent design. Burn the heathen!
IBM has already developed a high-fidelity 3-D copier. They scrapped the project when they realized they would likely sell only two units.
What a fool believes, he sees, no wise man has the power to reason away.
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 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.
Nostalgia's not what it used to be.
Yes, you're right. TFA is rather confusing on the precise nature of the thing, but the Gemini article on LifeWiki explains what it actually is:
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.
It's Hannah Montana.
OH GOD WHAT HAVE WE DONE?!?
Kill it with fire, kill it with fire!
Try not to take me more seriously than I take myself.
If I understand correctly, it creates two copies while self-destructing in the process. So it is, indeed, replicating.
Now that's interesting.
When i first read the headline I was befuddled. The whole point of the game is that its structures replicate themselves and create other things all over the map.
But I don't recall ever seeing one that made multiple copies of itself, and then died.
This is a tricky point. The people who say that this new pattern is not ultimately different from a glider are correct, in a sense -- the Gemini spaceship is technically a spaceship, not a replicator.
It _does_ make two copies -- but the copies are of the two replicator units at the ends of the glider channels, not of the entire spaceship.
But replicator units replicating themselves, even with the help of an outside stream of instructions (which is then reflected on to the next newly-created copy of a replicator unit) are still something that hasn't been seen before in the Life universe. So this is a much more impressive technical accomplishment than, say, finding a new variety of spaceship using a search utility.
Gliders and spaceships "replicate" themselves in somewhat the same way that salt crystals or wildfires do -- that's just the way the universe works, you might say. But the Gemini pattern keeps itself going by continuously reconstructing itself, in *spite* of the way the universe normally works.
The replicator units are like robots that include all the tools needed to make more robots exactly like themselves -- but they're radio-controlled and have no internal memory, so you have to pipe the actual construction recipe in from somewhere else. That means they're not self-contained self-replicators, true -- but they're a darn sight closer than a salt crystal or a glider!
Eventually someone will build a pattern with an internal memory that can hold a complete self-construction recipe -- but the Gemini is an important milestone along the way to that goal, and the first true Life replicator will probably contain ideas taken from the Gemini, just as the Gemini contains ideas and mechanisms from preceding patterns.