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.
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:
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.
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.
Last modified: February 15 1999
Eli Bachmutsky