![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mmcirvinAs I said in my post on Golly and Life, I completely missed the fuss that happened last spring about Andrew Wade's Gemini pattern, first revealed to the world in a forum discussion. It got written up in a typically breathless New Scientist article, then got picked up by BoingBoing and Slashdot in the usual way of such things. Most of the articles seemed unclear on what was actually interesting about the pattern; often it was identified as "first mathematical artificial life" or something along those lines. Then there ensued controversy over whether it really counted as a replicator. (Andrew Wade never claimed to have achieved the holy grail of a true Life replicator; he called it a "universal-constructor-based spaceship". In cellular-automaton jargon, a spaceship is any pattern that moves itself around intact.)
Having watched it run through a few full lifecycles in Golly, I say it's not a replicator in the sense that a living cell is one, but it's still pretty cool; it makes use of universal-construction principles in an unusually simple way for a Life pattern. I get the impression that Life tinkerers have been busy playing with the new set of toys that it implies.
Now, as it happens (though I don't think von Neumann knew it), there are cellular automata in which replicators are really easy to construct. There's a close variant of Life with a simple replicator. There are even some in which every pattern is a replicator and recursively spawns copies of itself all over the place. But it's unlikely that such a thing would provide much insight into how living replicators might work; they're more like crystal growth, with objects serving as direct templates for their descendants. Nor would you likely be able to get something that worked like that to do anything other than self-reproduce.
Von Neumann's replicator lived in a world with 29 cell states, rather more complicated in its fundamentals than Conway's Life. Von Neumann's world was designed to facilitate the building of logic circuits. His idea was that a useful replicator would be a "universal constructor", a programmable computer with an extension capable of building a wide variety of things according to the computer's program, which in the cellular automaton was stored on a kind of tape, a string of cells with various patterns of states encoded in it.
But not so fast! The tape can hold a program for constructing the constructor, but it can't hold a program for constructing the tape itself; there's no room. So there has to be some other dodge for building the new tape. Well, if you're familiar with modern computers, you know what that is: a program, like a book, a picture or a song, can be copied using the original as a simple template.
So the program tape is used two different ways. The replicator duplicates the tape by treating it as a template, then duplicates itself using the tape as coded instructions. (Douglas Hofstadter calls this type of operation "quining", in honor of the philosopher W. V. O. Quine, who talked about analogous self-negating sentences such as "'Is false when preceded by itself in quotes' is false when preceded by itself in quotes." The phrase composing half of the sentence is used two ways: mentioned as a textual object, and used as a text with meaning, allowing the sentence to indirectly refer to itself as a subject by combining the two operations. Gödel's Incompleteness Theorem uses a similar construction, as Hofstadter likes to go on about. Anyway.)
As it happens, this is pretty much what happens to DNA in a living cell. The DNA gets replicated through template copying, and it's also transcribed to RNA which gets "executed" by ribosomes when they build proteins, which form most of the functional parts of the cell. The DNA isn't, in any simple sense, a program for building a whole organism or a whole cell from scratch (there's a lot of self-organization and extranuclear information passed on as well), nor is the cell run by anything quite as conceptually clean as a CPU; but something very like von Neumann's mechanism is a key element of the replication process. John von Neumann worked all this out before many of the details of how DNA worked were known, though I do get the impression that the idea was in the air that something like this was going on.
Anyway, von Neumann designed the CA and proved that the machine could exist, but one thing he didn't do was write a detailed program tape for one (without a computer anywhere near capable of running the pattern, there would be little point). In recent years, with the computer power readily available, people have actually done this, and you can actually run the thing in Golly and see it reproduce.
It's been known for some time that Life is capable of supporting replicators constructed along von Neumann's principles. All the essential parts of a universal computer can be made from Life cells, and constructed using complicated collisions of gliders (the smallest Life spaceship, a little shape of five lit pixels that crawls diagonally). There are also "constructor arms", glider-and-block assemblies that can emit aimed gliders in a controllable way. So you could build a programmable computer-constructor that could build things from instructions on a tape, just like von Neumann's machine (only slower). Geeks of a certain age may remember the description of how such a thing might work in William Poundstone's pop book The Recursive Universe.
People have done this. Here's a popular universal computer/constructor called Spartan. Presumably one could program a Spartan to build a Spartan, though there would still be the matter of the template replication of the program tape (I'm not sure whether that problem's been thought through or not for a Spartan tape). Spartan's creator, Adam Goucher, estimates that Spartan would take about 1018 ticks to build a copy of itself, which for a pattern that complicated is a bit much even for Golly.
What simplifies the Gemini constructor considerably is that its program tape is a fat, moving swarm of intricately patterned gliders, instead of a string of stationary objects. It doesn't make any attempt to be a universal computer; it's just following the tape as it spools along, like a player piano. This means that it doesn't need a tape reader or a complicated internal state machine or anything like that; it's got three construction-arm controllers driven by the gliders in the tape, and reflectors to send the tape back the way it came, only shifted sideways a bit. (The internal logic mostly works via "Herschel conduits", weird-looking static constructions that can channel clouds of boiling gunk as steerable signals.) Meanwhile, two of the construction arms, under control of the tape, build a child constructor; the third destroys the constructor's parent. The really clever thing is that there are two of these constructors working at any given time, one at each end of a long stretch of tape about half as long as the tape's total length. Each constructor sends the tape back toward the other one, but shifted a bit to the side so that it's aimed not at the sender, but at the new child constructor that the sender is building. By the time the tape gets there, the parent is just putting the last finishing touches on the child constructor and it's ready to run! The tape starts to spool through the child, the child extends its three arms for the first time... and starts destroying its parent, while constructing its own child.
Here's an ASCII diagram of the whole thing, drawn with extreme artistic liberties. (My apologies if your font messes this up.) I've rotated and skewed the picture; really the tape goes at a 45-degree angle to the Life grid, and the direction of travel of the whole mess is at an odd oblique angle, and "not to scale" is an understatement. The diagonal lines represent the movable constructor and destructor arms. The O-shaped "rollers" are supposed to represent the mechanisms that perform a shifted reflection of the tape, and the pound signs are the internal guts of the thing that control the constructor and destructor arms under tape direction:
The tape just keeps going, reaching each new constructor just as its parent finishes constructing it (and deleting its grandparent).
Here's why I say the whole thing is not a true replicator: it never copies the tape. There's only one tape, which zigzags from constructor to constructor as they build their children and unbuild their parents. The quining operation never happens. So there can only be one functioning "genetic individual" at any one time (the tape itself, and the active constructors reading it). We could leave off the deletion operation, but the parents left behind would just be dead husks, with no tape to run them; it'd just be a puffer instead of a spaceship.
Still, I think this is probably going to lead to a true Life replicator of some sort before too long. The active tapes, and the idea of paring down the constructors to the minimum required to self-construct, are important innovations. And the whole thing actually runs in Golly and is incredibly cool to watch.
(Update, March 2025: Fixed the Life Wiki links.)
Having watched it run through a few full lifecycles in Golly, I say it's not a replicator in the sense that a living cell is one, but it's still pretty cool; it makes use of universal-construction principles in an unusually simple way for a Life pattern. I get the impression that Life tinkerers have been busy playing with the new set of toys that it implies.
The universal constructor
To understand why this is an interesting area of study, and why I say Gemini is not a replicator, it's useful to go back to the work of the amazingly polymathic John von Neumann in the late 1940s. von Neumann was interested (among many, many other things) in the question of whether one could in principle build a self-replicating machine, in part as a model of how living things reproduce. He proposed a simple mechanical replicator that could build copies of itself from pieces, then decided he could make more progress by using a simplified model of physics: a cellular automaton (CA), a sort of simulated world made of a grid of cells with a limited number of states that interacted only with their neighbors.Now, as it happens (though I don't think von Neumann knew it), there are cellular automata in which replicators are really easy to construct. There's a close variant of Life with a simple replicator. There are even some in which every pattern is a replicator and recursively spawns copies of itself all over the place. But it's unlikely that such a thing would provide much insight into how living replicators might work; they're more like crystal growth, with objects serving as direct templates for their descendants. Nor would you likely be able to get something that worked like that to do anything other than self-reproduce.
Von Neumann's replicator lived in a world with 29 cell states, rather more complicated in its fundamentals than Conway's Life. Von Neumann's world was designed to facilitate the building of logic circuits. His idea was that a useful replicator would be a "universal constructor", a programmable computer with an extension capable of building a wide variety of things according to the computer's program, which in the cellular automaton was stored on a kind of tape, a string of cells with various patterns of states encoded in it.
Two different ways
If such a constructor, suitably programmed, could build just about anything, then it could presumably build itself. (One simplifying property of the CA world is that, without anything like conservation of matter, the replicator has no need of raw materials; the only material limit on reproduction rate is space, because of the limited propagation speed of signals.)But not so fast! The tape can hold a program for constructing the constructor, but it can't hold a program for constructing the tape itself; there's no room. So there has to be some other dodge for building the new tape. Well, if you're familiar with modern computers, you know what that is: a program, like a book, a picture or a song, can be copied using the original as a simple template.
So the program tape is used two different ways. The replicator duplicates the tape by treating it as a template, then duplicates itself using the tape as coded instructions. (Douglas Hofstadter calls this type of operation "quining", in honor of the philosopher W. V. O. Quine, who talked about analogous self-negating sentences such as "'Is false when preceded by itself in quotes' is false when preceded by itself in quotes." The phrase composing half of the sentence is used two ways: mentioned as a textual object, and used as a text with meaning, allowing the sentence to indirectly refer to itself as a subject by combining the two operations. Gödel's Incompleteness Theorem uses a similar construction, as Hofstadter likes to go on about. Anyway.)
As it happens, this is pretty much what happens to DNA in a living cell. The DNA gets replicated through template copying, and it's also transcribed to RNA which gets "executed" by ribosomes when they build proteins, which form most of the functional parts of the cell. The DNA isn't, in any simple sense, a program for building a whole organism or a whole cell from scratch (there's a lot of self-organization and extranuclear information passed on as well), nor is the cell run by anything quite as conceptually clean as a CPU; but something very like von Neumann's mechanism is a key element of the replication process. John von Neumann worked all this out before many of the details of how DNA worked were known, though I do get the impression that the idea was in the air that something like this was going on.
Anyway, von Neumann designed the CA and proved that the machine could exist, but one thing he didn't do was write a detailed program tape for one (without a computer anywhere near capable of running the pattern, there would be little point). In recent years, with the computer power readily available, people have actually done this, and you can actually run the thing in Golly and see it reproduce.
Universal constructors in Life
Now, while von Neumann's CA wasn't as replicator-friendly as the everything-is-a-replicator world, it was still contrived to make it a little easier to build a replicator. It'd be mighty impressive if someone were to build a replicator in Conway Life, which was just studied because it exhibited a lot of interesting behavior from very simple rules (much simpler than von Neumann's), and in that sense is more of a "natural" little universe. While it might not provide much in the way of extra insight about natural or artificial life, it would at the very least be interesting to watch, and probably provide a lot of technical know-how about how to build things in the Life world.It's been known for some time that Life is capable of supporting replicators constructed along von Neumann's principles. All the essential parts of a universal computer can be made from Life cells, and constructed using complicated collisions of gliders (the smallest Life spaceship, a little shape of five lit pixels that crawls diagonally). There are also "constructor arms", glider-and-block assemblies that can emit aimed gliders in a controllable way. So you could build a programmable computer-constructor that could build things from instructions on a tape, just like von Neumann's machine (only slower). Geeks of a certain age may remember the description of how such a thing might work in William Poundstone's pop book The Recursive Universe.
People have done this. Here's a popular universal computer/constructor called Spartan. Presumably one could program a Spartan to build a Spartan, though there would still be the matter of the template replication of the program tape (I'm not sure whether that problem's been thought through or not for a Spartan tape). Spartan's creator, Adam Goucher, estimates that Spartan would take about 1018 ticks to build a copy of itself, which for a pattern that complicated is a bit much even for Golly.
Gemini
Now what Andrew Wade has done is to come up with a constructor capable of building itself that is simple and efficient enough to do the job in around 3×107 generations instead of 1018, which is a dramatic improvement. That's no small thing.What simplifies the Gemini constructor considerably is that its program tape is a fat, moving swarm of intricately patterned gliders, instead of a string of stationary objects. It doesn't make any attempt to be a universal computer; it's just following the tape as it spools along, like a player piano. This means that it doesn't need a tape reader or a complicated internal state machine or anything like that; it's got three construction-arm controllers driven by the gliders in the tape, and reflectors to send the tape back the way it came, only shifted sideways a bit. (The internal logic mostly works via "Herschel conduits", weird-looking static constructions that can channel clouds of boiling gunk as steerable signals.) Meanwhile, two of the construction arms, under control of the tape, build a child constructor; the third destroys the constructor's parent. The really clever thing is that there are two of these constructors working at any given time, one at each end of a long stretch of tape about half as long as the tape's total length. Each constructor sends the tape back toward the other one, but shifted a bit to the side so that it's aimed not at the sender, but at the new child constructor that the sender is building. By the time the tape gets there, the parent is just putting the last finishing touches on the child constructor and it's ready to run! The tape starts to spool through the child, the child extends its three arms for the first time... and starts destroying its parent, while constructing its own child.
Here's an ASCII diagram of the whole thing, drawn with extreme artistic liberties. (My apologies if your font messes this up.) I've rotated and skewed the picture; really the tape goes at a 45-degree angle to the Life grid, and the direction of travel of the whole mess is at an odd oblique angle, and "not to scale" is an understatement. The diagonal lines represent the movable constructor and destructor arms. The O-shaped "rollers" are supposed to represent the mechanisms that perform a shifted reflection of the tape, and the pound signs are the internal guts of the thing that control the constructor and destructor arms under tape direction:
O#
child under construction #
#
#
/ \
/ \
O##O \ /
## \ /
## child almost finished \ /
## \ /
## \ /
O# ==============================O##O
<--- |##
/ \ |##
\ / constructor arms |##
\ / |##
O##O==========================================O##O
##| motion of tape ---> /
##| /
##| \
##|
O##O============= O
/ <--- #
/ ##
\ destructor arm #
\ ##
O##O
dead parent being erased
#
## dead parent almost gone
##O
The tape just keeps going, reaching each new constructor just as its parent finishes constructing it (and deleting its grandparent).
Here's why I say the whole thing is not a true replicator: it never copies the tape. There's only one tape, which zigzags from constructor to constructor as they build their children and unbuild their parents. The quining operation never happens. So there can only be one functioning "genetic individual" at any one time (the tape itself, and the active constructors reading it). We could leave off the deletion operation, but the parents left behind would just be dead husks, with no tape to run them; it'd just be a puffer instead of a spaceship.
Still, I think this is probably going to lead to a true Life replicator of some sort before too long. The active tapes, and the idea of paring down the constructors to the minimum required to self-construct, are important innovations. And the whole thing actually runs in Golly and is incredibly cool to watch.
(Update, March 2025: Fixed the Life Wiki links.)