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.'"
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.
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
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.
I am TheRaven on Soylent News
What are you talking about, non-existing? They both exist.
http://conwaylife.com/wiki/index.php?title=Universal_turing_machine
http://conwaylife.com/wiki/index.php?title=Turing_machine
http://www.conwaylife.com/wiki/index.php?title=P5760_unit_Life_cell
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."
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: