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"
.
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).
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.
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.
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.
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.
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