In a previous article, an announcement was made of a complex self-replicating machine (known as the 0E0P metacell) in a simple 2-state cellular automaton. In the interim between then and now, Thomas Cabaret has prepared a most illuminating video* explaining the method with which the machine copies itself:
Note: the video is in French; recently, Dave Greene added an English translation of the subtitles.
* the video is part of Cabaret’s Passe-Science series. You may enjoy some of his other videos, including an explanation of the P vs NP problem and a reduction of Boolean satisfiability to the 3-colourability of planar graphs.
In related news, Michael Simkin recently created a wonderfully anachronistic self-propagator entitled Remini: it uses the same single-channel/slow-salvo construction mechanism as the 0E0P metacell, but it is built from oscillatory components instead of static ones. That is to say, it implements modern ideas using components available in the 1970s.
The project involved slmake together with a suite of additional tools developed by Simkin. There isn’t a video of this machine self-replicating, so you’d need to download a program such as Golly in order to watch it running.
For further reading, I recommend (in order):
- The wiki entry (under construction) for the 0E0P metacell;
- An article unveiling various simpler examples of self-constructing circuitry;
- The slmake repository;
- A tutorial on effective use of slmake;
- A challenge thread proposing another contraption, that no-one has yet built. This would require the use of slmake followed by some ‘DNA-splicing’ to interleave the construction recipe with extra operations.
I am a physicist, not a specialist on cellular automation. Growth of anything ( from the physics point of view) assumes an energy exchange process which enables the phenomenon of growth in real physical world. So, where is the energy which sustain self replication process?
In the physical world, our world, conserved quantity like energy comes from continuous symmetries. Energy by example is the conserved quantity we can derived from the continuous translation symmetry through time (see Noether theorem). In cellular automata there is no such a things like the Noether theorem, mainly because we are not dealing with continuous world. Most of the time nothing has to be conserved. But if you want example of cellular automata with some common points with physics, I suggest my other video on cellular automata (same channel), in which I describe “single-rotation” cellular automata, a reversible kind of cellular automata with “matter” conservation and other derived conservation properties. It is also a good illustration of entropy. Regards.
I think I would answer more succinctly that we’re not dealing with physics here. Conway’s Game of Life (CGOL) does not conserve matter or energy. It is just a deterministic system with a particular set of rules. So “where is the energy” is not a question that applies here.
CGOL is also irreversible, unlike most of physics. I have wondered what it would take to get self-replication in a reversible system. It should be possible, but it introduces technical challenges. In CGOL, you can make unwanted debris vanish and often do. In a reversible system, all “reaction products” need to persist in some form so they can determine the outcome of reversed steps.
I spent a little recently on the reversible Margolus rule “Critters” (which has the additional problem that cell count is preserved, so you need both an explicit source of the new matter to organize into copies as well as a way to move debris outside the area of interest. The best I could construct explicitly was a signal fanout with the Critters equivalent of gliders. However, there is no reason that could not be extended to self-replication. We would also have close analogs to energy conservation and entropy (the “heat” consisting of discarded reaction products).
I feel , I offended somebody when I mentioned about physics and energy necessary to drive life processes . As a game set by your rules I can agree with you, but remember please that moving your cells on the computer display you inevitably consume electrical power or energy if you wish. So I an still not convinced however impressed by your software skills.
Great! thx Adam!
I’m not sure anyone is offended, or what you are not convinced of. The existence of self-replicating Life patterns is not intended to demonstrate the existence of such structures in physics-like systems with conservation laws (though it may provide some hints to how to make them). Are you at least convinced that it works in Life?
Hello “The best I could construct explicitly was a signal fanout” could you describe what you mean by that? Very interesting the challenge of self replicator in CA with conservation of alive cells (I would have preferred single-rotation to critters :P). Indeed there is organisational challenges, as you said matter pool garbage pool and also some kind of “memory management” what is been taken where what has been discarded where.
The machine would be really awesome. I asked recently myself a quite similar question: how does real world living cells deal with the “matter” needed for their replication.
I was writing about it in this thread. http://www.conwaylife.com/forums/viewtopic.php?f=11&t=3918 There didn’t seem to be much interest, though I think it is worth exploring.
Since you cannot create new cells in Critters, I have to assume that the constructors are fed by periodic streams coming from infinity. (It should go without saying, but this is not “cheating” just using an energy source as we do in the real world).
This has wrapped boundary conditions so it eventually crashes into itself.
I had a long reply with links, but it said “awaiting moderation” and (may have) disappeared. In case the problem was links, I wrote about this in a conwaylife thread in Other Cellular Automata called “Any serious survey of constructions in Margolus Critters?” The most difficult task I accomplished was to copy the bits of a recirculating loop into a periodic stream (assuming a “power source” of incoming gliders and throwing off garbage bits). (If anyone is actually moderating, please feel free to use the other comment, not this one.)
Thx (I can see the reply with the links) I’ll explore that!