Self-Replication loops in Cellular Space


You will choose cellular automata model type For start/stop used "Start"/"Stop" button.
For step-by-step generation "Step" button is used (when apllication stopped).

This Java applet written by Eli Bachmutsky, (see source code here) for Computational and Biochemical Theories of the Origin of Life course at the Weizmann Institute of Science, Israel.
Checked with Netscape Communicator 4.5 Browser (not worked properly with Netscape 3 Java). Sometimes this applet not worked properly with version 4 too, but under the standard ''appletviewer'' from Java JDK 1.2 it always worked well.
This applet is viewed better on 1024x768 pixels screen.


Self-Replication Loops Bibliography

Most of Self-Replication Loops references extracted from Moshe Sipper's,

"Artificial Self-Replicacion Page Bibliography"

.


Byl's Self-Replication Loop

Reference(s):
J. Byl. ``Self-Reproduction in small cellular automata.'' Physica D, Vol. 34, pages 295-299, 1989.

Description: Essentially, a simplification of
Langton's loop using less cellular states (6 as compared with Langton's 8) and a smaller replicating loop (12 cells as compared with Langton's 86).


Small Self-Replication Loops (Chou,Reggia, et al.)

Reference(s):
J. A. Reggia, S.L.Armentrout, H.-H. Chou, and Y. Peng. ``Simple systems that exhibit self-directed replication.'' Science, Vol. 259, pages 1282-1287, February 1993.

Description: Reggia et al. presented several small self-replicating loops, essentially based on Langton's work. Their smallest demonstrated loop consists of 5 cells, embedded in 6-state cellular space. Most of their loops are unsheathed, as opposed to those of Langton and Byl. They also studied cellular spaces exhibiting both weak and strong rotational symmetry (briefly, weak rotational symmetry means that some cell states are directionally oriented while with strong rotational symmetry all cell states are viewed as being unoriented).

A downloadable demo is available here.


Langton's Self-Replication Loop and Ant

Reference(s):
1.
C.G.Langton. ``Self-reproduction in cellular automata.'' Physica D, Vol. 10, pages 135-144, 1984.
2. C.G.Langton. ``Studying artificial life with cellular automata'' Physica D,Vol.22,pages 120-149,1986

Description: Langton observed that although the capacity for universal construction, as studied by von Neumann and Codd, is a sufficient condition for self-replication, it is not a necessary one. Furthermore, natural systems are probably not capable of universal construction. Langton and his successors Byl, Reggia et al., developed self-replicating automata which are much simpler than the universal constructor. These machines, however, lack any computing and constructing capabilities, their sole functionality being that of self-replication.

Langton's self-replicating structure is a loop constructed in two-dimensional, 8-state, 5-neighbor cellular space, based on one of Codd's elements, known as a periodic emitter. The 86-cell loop is basically a closed data path, consisting of a string of core cells in state 1, surrounded by sheath cells in state 2. Data paths are capable of transmitting data in the form of signals, which are packets of two co-traveling states: the signal state itself (state 4, 5, 6, or 7) followed by the state 0. The signals contained within the loop cycle through it, comprising the instructions for replication, i.e., the ``genome.'' As each such signal encounters the arm junction it is duplicated, with one copy propagating back around the loop again and the other copy propagating down the arm, where it is translated as an instruction when it reaches the end of the arm. In executing the instructions the arm extends itself and folds, ultimately resulting in a daughter loop, also containing the genome needed to replicate.

A primary characteristic emphasized by Langton is the two different modes in which information is used, interpreted and uninterpreted, which he compared with the biological processes of translation and transcription, respectively. In Langton's loop, translation is accomplished when the instruction signals are executed as they reach the end of the construction arm, and upon collision of signals with other signals. Transcription is accomplished by the duplication of signals at the arm junctions.

Langton's ant described in second article. The ant starts with one direction (north,south,west,east) on any cell. After many steps (~10000) ant's trajectory become periodic and unbounded ( Cohen-Kung theorem). His behavior described by 2 rules:
1. If the ant gets onto a empty (gray) cell, the ant change the color to red (occupied) and turn 90(I0(B clockwise. Then the ant moves onto the cell, which is in this direction and follows the rules, depending on the cell's color.
2. If the ant gets onto a occupied (red) cell, the ant will change the color to gray (empty) and will turn 90(I0(B counterclockwise. Then the ant moves onto the cell, which is in this direction and follows the rules, depending on the cell's color.


Self-Replication Loop with programming capabilities

Reference(s):
1.
G. Tempesti ``A new self-reproducing cellular automaton capable of construction and computation.'' In F. Morán, A.Moreno, J.J.Merelo,and P.Chacón, editors, ECAL'95: Third European Conference on Artificial Life, volume 929 of Lecture Notes in Computer Science, pages 555-563. Springer-Verlag, 1995.
2. G. Tempesti "A Self-Repairing Multiplexer-Based FPGA Inspired by Biological Processes"
[Acrobat PDF file,~1 MB,166 pages]
Ph.D. Thesis,1998

Description: The loops designed by Langton, Byl, and Reggia et al. lack any computing and constructing capabilities, their sole functionality being that of self-replication. Tempesti developed a self-replicating CA, similar to that of Langton's, yet with the added capability of attaching to the automaton an executable program which is duplicated and executed in each of its copies. The program is stored within the loop, interlaced with the replication code. This was demonstrated for a simple program that writes out (after the loop's replication) LSL, acronym of the Logic Systems Laboratory.


Self-replication loop with universal computer capabilities

Reference(s):
J.-Y. Perrier,
M. Sipper, and J. Zahnd. "Toward a viable, self-reproducing universal computer". Physica D, Vol. 97, pages 335-352, 1996.

Description: While Tempesti's loop has finite computational capabilities, Perrier et al. demonstrated a self-replicating loop that is capable of implementing any program, written in a simple yet universal programming language. The system consists of three parts, loop, program, and data, all of which are replicated, followed by the program's execution on the given data. The system has been simulated in its entirety, thus attaining a viable, self-replicating machine with programmable capabilities. Note that though the number of states seems prohibitive (63), the vast majority of entries in the rule table are identity transformations (i.e., ones that do not change the state of the central cell). This renders the automaton completely realizable.


SDSR Loop and Evoloops

Reference(s):
1.
Hiroki Sayama. "Introduction of Structural Dissolution into Langton's Self-Reproducing Loop." Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life, C. Adami, R. K. Belew, H. Kitano, and C. E. Taylor, eds., pp.114-122, Los Angeles, California, 1998, MIT Press.
2. Hiroki Sayama: "Spontaneous Evolution of Self-Reproducing Loops Implemented on Cellular Automata: A Preliminary Report", Proceedings of the Second International Conference on Complex Systems, Y. Bar-Yam, ed., Nashua, New Hampshire, 1998, Perseus Books, in press / InterJournal of Complex Systems, BArticle, submitted, 236.
3. Hiroki Sayama "Toward the Realization of an Evolving Ecosystem on Cellular Automata", Proceedings of the Fourth International Symposium on Artificial Life and Robotics (AROB 4th '99), M. Sugisaka and H. Tanaka, eds., pp.254-257, Beppu, Oita, Japan, 1999.

Description: The ``structurally dissolvable self-reproducing (SDSR) loop'' is a kind of revision of Langton's self-reproducing (SR) loop, which has the ability to dissolve its own structure, as well as to reproduce itself. Specifically, the author introduced a dissolving state `8' into the set of states of Langton's CA, in addition to modifying the transition rules. Through this improvement, the SDSR loop can dissolve its own structure when faced with difficult situations such as a shortage of space for self-reproduction. This mechanism (disappearance of a subsystem of the whole system) induces, for the first time, dynamically stable and potentially evolvable behavior into the colony of loops.

The evoloop is a new version of the SDSR loop which spontaneously varies by direct interaction of phenotypes and evolves toward fitter species through natural selection, in a simple deterministic 9-state 5-neighbor cellular automata space. It has been realized by enhancing the "adaptability" of the state-transition rules and modifying the initial configuration of the loop slightly.

More information about the SDSR loop and Evoloops is available here.


Last modified: February 15 1999
Eli Bachmutsky