First Self-Replicating Creature Spawned In Conway's Game of Life 241
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.'"
Re:I thought someone had a glider gun... (Score:5, Informative)
For those who don't know about the Game of Life (Score:5, Informative)
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
Re:Most impressive and important pattern? (Score:5, Informative)
Those are patterns in the game of life itself. The Turing Machine one is particularly impressive. It demonstrates that the game itself is a Turing-complete computation engine - the more complex version is a Universal Turing Machine, so you can encode any arbitrary algorithm on the 'tape' (a streak of cells that runs diagonally across the grid).
Given that it demonstrated the Turing completeness of the system, it's probably the most important pattern, as it shows that you can create a pattern with any algorithmic behaviour that you want. This includes providing a proof that the pattern discussed in TFA is possible, although not (of course) telling you how to create it. This pattern is interesting, but knowing that it's possible is more interesting than knowing exactly what it is.
Re:Most impressive and important pattern? (Score:5, Informative)
What are you talking about, non-existing? They both exist.
http://conwaylife.com/wiki/index.php?title=Universal_turing_machine [conwaylife.com]
http://conwaylife.com/wiki/index.php?title=Turing_machine [conwaylife.com]
http://www.conwaylife.com/wiki/index.php?title=P5760_unit_Life_cell [conwaylife.com]
Displacement not Self-Replicating (Score:4, Informative)
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."
Re:For those who don't know about the Game of Life (Score:5, Informative)
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.
Google Docs is slashdotted... Alternate download (Score:2, Informative)
Re:I thought someone had a glider gun... (Score:4, Informative)
Check out the forum where it was posted: http://conwaylife.com/forums/viewtopic.php?f=2&t=399&start=0 [conwaylife.com]
That's the game of life forum - Conway is the guy who invented it.
It may be a popular forum, but the domain conwaylife.com is not owned by Conway.
Re:I thought someone had a glider gun... (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.
Re:I thought someone had a glider gun... (Score:5, Informative)
Yes, you're right. TFA is rather confusing on the precise nature of the thing, but the Gemini article [conwaylife.com] on LifeWiki explains what it actually is:
toggle overdrive (Score:3, Informative)
beside the rabbit is the radiation-looking thing. Toggle it and it runs 100x faster.
The number 2 pops out at around 11000 or so.
Re:I thought someone had a glider gun... (Score:3, Informative)
But the Gemini pattern keeps itself going by continuously reconstructing itself, in *spite* of the way the universe normally works.
how so?
I was hoping someone would ask that. Let me start out with a comparison to other cellular automata. Conway's Life is B3/S23 -- "born if 3 neighbors, survives if 2 or 3 neighbors". There are other rules, such as HighLife [wikipedia.org] (B36/S23, very close to Conway's Life) in which a 12-cell pattern can replicate itself -- after 12 generations there are 2 copies, after 36 ticks there are 4 copies, and so on. This pattern regularly evolves from random starting states.
There's even a rule, Fredkin's parity rule (B1357/S1257) where every possible pattern is a replicator -- an extreme example of replication being "just the way the universe works". But these replicators are, in some sense, too simple to be very interesting! They replicate the way crystals grow, and it's hard to harness that kind of low-level behavior. If you wanted a HighLife replicator with 13 cells, or one that would replicate in 13 ticks, instead of 12, you'd be out of luck. By comparison, the Gemini spaceship is extraordinarily adjustable.
will this pattern repair itself if anything happens to it? will it protect itself from outside influences? like a cell wall protects the inside of a cell?
No to all of the above. Conway's Life is not amenable to error-correction of this kind, because small changes have such huge consequences. Kind of like building machinery out of chunks of sub-critical enriched uranium: you can design it so that during normal operation the various pieces never come close enough together to start a chain reaction, but if any little thing goes wrong, you end up with high-energy particles flying all over the place, spreading the reaction to other nearby machinery, which then contributes to the explosion.
so how is it reconstructing itself in spite of the things around it?
Well, I didn't say "in spite of the things around it" -- it was "in spite of the way the universe normally works." The Life universe, for random patterns anyway, normally settles into a scattering of stable or P2-oscillating ash after a few hundred or a few thousand generations. There are any number of "lucky" self-perpetuating stationary and moving patterns that are exceptions to this general rule, but they're all very delicately balanced on the edge of chaos.
how is this anything but a different kind of glider?
The Gemini spaceship contains a large amount of data in its glider channels that is recognizably information about its own structure. Change that data, and the replicator unit will (usually) build something different. Most other gliders and spaceships in Conway's Life don't have anything like this -- all the other hundreds of patterns in Golly's Spaceships folder, or the tens of thousands in Koenig's Life Object database, are "naturally" self-perpetuating, because a future generation of the pattern happens to be identical to the original.
The Gemini spaceship has a significantly higher degree of control over its environment: with the right change to its program, a Gemini replicator unit could construct anything that can be built by colliding gliders, in any empty space in the Life universe. The Gemini contains most or all of the construction tools that a Conway's Life self-replicator will need; it's just a few short steps away from being a true replicator. Mostly it just doesn't have the right program -- yet.
There are a few other large patterns, especially Gabriel Nivasch's Caterpillar [yucs.org], that blur this line to some extent. However, the pi-climber "data" in the Caterpillar is much more difficult to reprogram than the gliders in the Gemini. Several new variants of the Gemini with different speeds and angles of travel have already been built -- with a lot of help from the Python scripts that Andrew Wade made available along with the pattern..