|
 |
|
by Moshe Sipper
-
... living organisms are very complicated aggregations of elementary
parts, and by any reasonable theory of probability or thermodynamics
highly improbable. That they should occur in the world at all is a
miracle of the first magnitude; the only thing which removes, or
mitigates, this miracle is that they reproduce themselves. Therefore,
if by any peculiar accident there should ever be one of them, from
there on the rules of probability do not apply, and there will be many
of them, at least if the milieu is reasonable.
John von Neumann, Theory of Self-Reproducing Automata.
In the late 1940's eminent mathematician and physicist John von Neumann had become interested in the question of whether a machine can self-replicate, that is, produce copies of itself. Von Neumann wished to investigate the logic necessary for replication - he was not interested, nor did he have the tools, in building a working machine at the bio-chemical or genetic level. Remember that at the time DNA had not yet been discovered as the genetic material in nature.
The study of artificial self-replicating structures or machines has been taking place now for almost half a century. Much of this work is motivated by the desire to understand the fundamental information-processing principles and algorithms involved in self-replication, independent of their physical realization. An understanding of these principles could prove useful in a number of ways. It may advance our knowledge of biological mechanisms of replication by clarifying the conditions that any self-replicating system must satisfy and by providing alternative explanations for empirically observed phenomena. The fabrication of artificial self-replicating machines can also have diverse applications, ranging from nanotechnology to space exploration.
One of the central models used to study self-replication is that of cellular automata (CA). CAs are dynamical systems in which space and time are discrete. A cellular automaton consists of an array of cells, each of which can be in one of a finite number of possible states, updated synchronously in discrete time steps, according to a local, identical interaction rule. The state of a cell at the next time step is determined by the current states of a surrounding neighborhood of cells. This transition is usually specified in the form of a rule table, delineating the cell's next state for each possible neighborhood configuration. The cellular array (grid) is n-dimensional, where n=1,2,3 is used in practice. For more information on CAs click here. One of the reasons for the ubiquitous use of CAs as a vehicle for studies in self-replication seems to be historical: von Neumann chose it for its simplicity and rigor - one can create a scenario, or ``universe,'' as it is sometimes referred to, using simple basic ingredients in a model that is mathematically rigorous. Other models, however, have also been used in the study of self-replication, as can be seen in this page.
A note concerning terminology: in a recent paper, Sipper et al. (1997 - see POE page for exact reference) made a distinction between two terms, replication and reproduction, which are often considered synonymous. Replication is an ontogenetic, developmental process, involving no genetic operators, resulting in an exact duplicate of the parent organism. Reproduction, on the other hand, is a phylogenetic (evolutionary) process, involving genetic operators such as crossover and mutation, thereby giving rise to variety and ultimately to evolution. In most works described herein these two terms are considered synonymous and are used interchangeably (indeed, most researchers seem to have opted for the somewhat less correct term of reproduction).
The following page summarizes research on self-replicating systems, arranged in chronological order. Each system is described by the following items: title, author(s), year, model, implementation (e.g., theoretical work, computer simulation, hardware, bioware), reference(s), a short description, and related work. You will also find a listing of some general references and events related to self-replication.
The figures cited herein are available in the following file.
If you have an additional entry to suggest, I would appreciate your sending it in html, adhering to the format below. ☺
Thanks to the following people for their suggestions: Eli Bachmutsky, John Case, Robert A. Freitas Jr., Chris Langton, Jason Lohn, Tom Ray, Hiroki Sayama, Marco Tomassini, Paul M. B. Vitányi.
Last updated: 17-Feb-2015.
Von Neumann used two-dimensional CAs with 29 states per cell and a
neighborhood consisting of 5 cells (the neighborhood consists of the
cell itself together with its four immediate nondiagonal neighbors).
He showed that a universal computer can be embedded in such
cellular space, namely, a device whose computational power is
equivalent to that of a universal Turing machine. He also described
how a universal constructor may be built, namely, a machine
capable of constructing, through the use of a ``constructing arm,''
any configuration whose description can be stored on its input
tape. The universal constructor is therefore capable, given its own
description, of constructing a copy of itself, i.e., of
self-replicating. Note that terms such as machine and tape refer
to configurations of CA states - indeed the ability to formally
describe such structures served as a major motivation for von
Neumann's choice of the CA model. It has been noted that the basic
mechanisms von Neumann proposed for attaining self-replication in
cellular automata bear strong resemblance to those employed by
biological life, discovered during the following decade.
Barricelli ran computer simulations between 1953-1956 in Princeton,
New Jersey, using the electronic computer of the Institute for
Advanced Study. To get a flavor of what was meant by ``computer
simulations'' in those days, here's a quote from Reference 1: ``Part of
an evolution process developed in Princeton in 1956 is described in
fig. 24. The figure is obtained by a photographic method from IBM
cards punched by the computer and represents a part of the memory of
the computer at various stages during the evolution process.''
(In the related paper Vitányi showed that in a cellular space
the number of active units arising from a given number of active units
is a function that rises faster than any computable function. This
holds also for the function that gives the size of a steady-state
population of reproducing automata as a function of a given start
population. That is the relevance to self-replicating CA's. This
holds even under the most severe restrictions on neighborhood and
dimension of the CA.)
Replication in Laing's model is achieved by self-inspection,
where the description of the object to be replicated (the ``genome'')
is dynamically constructed concomitantly with its interpretation.
This is different than the other systems described herein (except that
of
Ibáñez et al.) where the genome is essentially
predetermined (either by direct design or by artificial evolution).
Laing (1977) noted that ``The capacity of a system generally to
explore its own structure and produce a complete description of it for
its perusal and use (for example, in generation and evaluation of
behavioral options open to it) seems a valuable one, and if such a
prima facie advantageous capacity is not exhibited
anywhere in naturally occurring systems, this in itself seems of
interest.''
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 (this latter state is represented by
dots in Figure 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.
An online demo is available
here.
An online demo is available
here.
An online demo is available
here.
The embryonics team developed an artificial cell, dubbed
biodule (biological module), that is used as an elementary unit
from which multicellular organisms can
ontogenetically develop to perform useful tasks. Cellular
differentiation takes place by having each cell compute its
coordinates (i.e., position) within a one- or two-dimensional space,
after which it can extract the specific gene within the artificial
genome responsible for the cell's functionality. Cellular division
occurs when a mother cell, the zygote, arbitrarily placed
within the grid, multiplies to fill a large portion of the space, thus
forming a multicellular organism. In addition to self-replication,
this artificial organism also exhibits self-repair capabilities,
another biologically inspired phenomenon,
lacking in the other systems presented herein. Such self-replicating
machines are multicellular artificial organisms, in the sense
that each of the several cells comprising the organism contains one
copy of the complete genome. In this respect, most other
self-replicating automata described herein can be considered
unicellular organisms: there is a single genome describing (and
contained within) the entire machine (for example,
Langton's
loop).
Each von Neumann module is composed of two units, a computation
unit and a display unit. The computation unit, implemented
using a reconfigurable processor known as a field-programmable gate
array (FPGA) calculates the cell's next state by directly
communicating with the adjacent, neighboring cells. The cell's state
is stored and sent to the display unit, implemented using a dot-matrix
display, a microcontroller, and a small number of latches. This
latter unit constantly reads the current state of the cell, and
updates the display accordingly.
To date, Beuchat and Haenni used this module to implement a
25-cell ``organ.''
Von Neumann's machine
is divided into many
functional blocks, such as decoders and pulsers, known as organs. For
example, a pulser P(11001) generates at a designated output cell the
sequence of excitations (signals) 11001 a fixed number of time steps
after receiving an excitation (i.e., a 1 signal) at a designated input
cell.
More information about the SDSR loop is available
here.
More information about the evoloop is available
here.
More information plus simulation is available
here.
General references
(includes a short review section).
Events related to self-replication
Research on self-replicating systems
Title: Universal constructor-computer.
Author(s): John von Neumann (this work was completed
posthumously by Arthur Burks).
Year(s): Late 1940's.
Model: Two-dimensional, 5-neighbor, cellular automaton with 29
states per cell.
Implementation: Theoretical work (cf.
Signorini,
Pesavento,
Beuchat and Haenni).
Reference(s): J. von Neumann.
Theory of Self-Reproducing Automata.
University of Illinois Press, Illinois, 1966.
Edited and completed by A. W. Burks.
See also Burks.
Description:
Von Neumann is credited with being the first to conduct a formal
investigation of self-replication by machines. In particular he asked
whether we can use purely mathematical-logical considerations to
discover the specific features of biological automata that make them
self-replicating. To conduct a formal investigation of this issue,
von Neumann used the cellular automaton model, conceived by Stanislaw
Ulam.
Figure(s): 1.
Title: Mechanical self-replication.
Author(s): Lionel S. Penrose and Roger Penrose.
Year(s): 1959.
Model: Simple mechanical units.
Implementation: Plywood.
Reference(s):
L. S. Penrose.
``Self-reproducing machines.''
Scientific American, Vol. 200, No. 6., pages 105-114, June 1959.
Description: Lionel Penrose, aided by his son Roger
Penrose, built simple mechanical units or bricks. An ensemble of such
units were placed in a box, which was then shaken. As described by
Penrose (1959): ``In fanciful terms, we visualized the process of
mechanical self-replication proceeding somewhat as follows: Suppose we
have a sack or some other container full of units jostling one another
as the sack is shaken and distorted in all manner of ways. In spite of
this, the units remain detached from one another. Then we put into the
sack a prearranged connected structure made from units exactly similar
to those already within the sack... Now we agitate the sack again in
the same random and vigorous manner, with the seed structure jostling
about among the neutral units. This time we find that replicas of the
seed structure have been assembled from the formerly neutral or
``lifeless'' material.''
Title: Some other early references.
Year(s): 1950s.
Model: Various.
Implementation: Various.
Reference(s):
1. J. Kemeny, ``Man viewed as a machine,''
Scientific American, Vol. 192, April 1955,
pages 58-67.
(Described, among others, von Neumann's work.)
2. E. F. Moore, ``Artificial living plants,'' Scientific American,
Vol. 195, October 1956, pages 118-126.
(Speculations on applications for machines that can reproduce.)
3. H. Jacobson, ``On models of reproduction,'' American Scientist,
Vol. 46, 1958, pages 255-284.
(Built a replicator using toy train parts running around a track.)
4. H. J. Morowitz, ``A model of reproduction,''
American Scientist, Vol. 47, 1959,
pages 261-263.
(Another construction of a simple physical replicator.)
Title: Numerical testing of evolution theories.
Author(s): Nils Aall Barricelli.
Year(s): 1950s, 1960s.
Model: Array of self-reproducing numbers.
Implementation: Computer simulation.
Reference(s):
1. N. A. Barricelli. ``Numerical testing of evolution theories. Part I.
Theoretical introduction and basic tests.''
Acta Biotheoretica, Vol. XVI, Parts I/II, pages 69-98, 1962.
2. N. A. Barricelli. ``Numerical testing of evolution theories.
Part II. Preliminary tests of performance. Symbiogenesis and
terrestrial life.'' Acta Biotheoretica, Vol. XVI, Parts III/IV,
pages 99-126. 1963.
3. J. Reed, R. Toombs, and N. A. Barricelli. ``Simulation
of biological evolution and machine learning. I. Selection
of self-reproducing numeric patterns by data processing machines,
effects of hereditary control, mutation type and crossing.''
Journal of Theoretical Biology, Vol. 17, pages 319-342. 1967.
4. Barricelli's work is described in detail in the book by George B. Dyson
Darwin Among the Machines: The Evolution of Global Intelligence
(Perseus Press, Reading, MA, 1997).
Description: In the 1950s Nils Aall Barricelli
performed experiments in artificial life and artificial evolution,
being among the first (if not the first) to actually run
computer simulations. From Reference 1: ``The problem of testing
evolution phenomena and theories by using artificial self-reproducing
entities is discussed... It is shown that the variability problem can
be solved assuming that self-reproducing patterns (called
symbio-organisms) of any complexity can be formed by a symbiotic
association of several self-reproducing entities, each with very low
variability or no variability at all (symbiogenesis theory)... Once
the variability problem was overcome, it was possible to design
artificial (e.g. numerical) self-reproducing entities able to develop
a variety of evolutionary phenomena.''
Title: Self-replicating universal automata.
Author(s): Michael A. Arbib.
Year(s): 1966.
Model: Universal array with programmable cells.
Implementation: Theoretical work.
Reference(s):
M. A. Arbib.
``Simple self-reproducing universal automata.''
Information and Control, Vol. 9, pages 177-189, 1966.
Description:
Arbib presented a universal array in which the self-replicating structure
is simpler to program (with respect to
Von Neumann's system), yet built of more complex elemental cells.
The basic unit, or cell, is a finite automaton which can execute an
internal program of up to 20 instructions. Arbib (1966) noted that
von Neumann had ``... shown that one may construct self-reproducing
universal arrays using as basic cells finite automata with only 29
states. The price we pay for the simplicity of the components is that
the coding of the array is enormously complicated, and the operation
of the array requires many many steps to simulate one cycle of an
ordinary Turing machine.'' With respect to his model he noted that
``The price we pay for the simplicity of programming and operation is
that our cells are more complicated... The point of our construction
is not that very simple or very complex components can be used to build
a self-reproducing automaton; but rather that, given components of one level
of complexity, we may use them to obtain self-reproducing aggregates
of an arbitrarily higher level of complexity...''
Related work:
Sipper,
Lohn and Reggia.
Title: Universal constructor-computer.
Author(s): E. F. Codd.
Year(s): 1968.
Model: Two-dimensional, 5-neighbor cellular automaton with 8
states per cell.
Implementation: Theoretical work.
Reference(s): E. F. Codd.
Cellular Automata.
Academic Press, New York, 1968.
Description:
Von Neumann's universal constructor-computer
was simplified by Codd who used an 8-state,
5-neighbor cellular space. Self-replication is obtained as a special
case of universal construction, just as with von Neumann's work.
Title: Simple nontrivial self-replicating machines.
Author(s): Alvy Ray Smith.
Year(s): 1968-69.
Model: Cellular automata.
Implementation: Theoretical work.
Reference(s): The original work was carried out in
the late 1960's as part of Smith's Ph.D. dissertation, but was made
widely available in 1992.
A. R. Smith.
``Simple nontrivial self-reproducing machines.''
In C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, editors,
Artificial Life II, volume X of SFI Studies in the Sciences
of Complexity, pages 709-725, Redwood City, CA, 1992. Addison-Wesley.
Description:
Von Neumann's proof of the possibility of machine self-replication
is achieved via a book-length constructive proof. Smith provided a
two-page proof of the possibility of machine self-replication (thus
his proof is existence rather than constructive). Whereas von Neumann
required both computation universality and construction universality
of his self-replicating machines, Smith showed that computational
universality alone suffices. Smith (1992) noted that ``the proof here
reduces the problem of self-construction to a computation problem,
which means that no machinery beyond ordinary computation theory is
required for self-reproduction.''
Title: Essays on cellular automata.
Author(s):
Arthur W. Burks (editor).
Year(s): 1970.
Model: Cellular automata.
Implementation: Theoretical work.
Reference(s):
A. W. Burks. Essays on Cellular Automata, University of Illinois Press,
Urbana, Illinois, 1970.
Description:
A compendium of works on cellular automata, in particular drawing
inspiration from von Neumann's
work. Chapters dealing specifically with self-replication:
Chapter 1: ``Von Neumann's self-reproducing automata,`` Arthur W. Burks,
pages 3-64.
Chapter 4: ``Self-describing Turing machines and self-reproducing cellular
automata,`` J. W. Thatcher, pages 103-131.
Chapter 6: ``Machine models of self-reproduction,`` Edward F. Moore,
pages 187-203.
Chapter 8: ``The abstract theory of self-reproduction,'' John Myhill,
pages 206-218.
Title: Periodicity in generations of automata.
Author(s):
John Case.
Year(s): 1971-74.
Model: Universal constructors with Turing Machines for
brains and for (generating) blueprints.
Implementation: Theoretical work.
Reference(s):
1. J. Case. ``A note on degrees of self-describing Turing machines.''
Journal of the Association for Computing Machinery, Vol. 18,
pages 329-338, 1971.
2. J. Case. ``Recursion theorems and automata which construct.''
Proceedings of the 1974 Conference on Biologically Motivated Automata
Theory, IEEE, New York, N.Y., 1974.
3. J. Case. ``Periodicity in generations of automata.'' Mathematical
Systems Theory, Vol. 8, pages 15-32, 1974.
Description: This work was partly inspired by Myhill's
paper reprinted as Chapter 8 in Burks's Essays on
Cellular Automata.
Considered are machines which construct distortions of themselves.
This includes the cases of machines that eventually have a sterile
descendant, those which after a delay of m generations repeat
every n generations, and those that are aperiodic over generations.
The third reference contains discussion of the meaning for biology of the
case of periodicity in generations, where the period n is greater
than 1.
It is shown that there are no algorithms for deciding of a progenitor
machine many things about its descendants. For example, there is no
algorithm for deciding of a progenitor which does not have sterile
descendants whether its descendants are periodic or aperiodic in
generations.
The third reference also introduces the author's operator recursion theorem,
an infinitary analog of Kleene's recursion theorem. This tool
subsequently found application in abstract complexity theory and in
computational learning
theory.
Title: Self-replicating programs.
Author(s): Paul Bratley and Jean Millo.
Year(s): 1972.
Model: Computer program.
Implementation: Computer simulation.
Reference(s):
P. Bratley and J. Millo. ``Computer recreations: Self-reproducing
programs.'' Software Practice and Experience, Vol. 2, pages
397-400, 1972.
See
The Quine Page for several examples of self-replicating programs.
Title: Self-replicating computer.
Author(s): John Devore.
Year(s): Early 1970's.
Model: Two-dimensional, 5-neighbor cellular automaton with 8
states per cell.
Implementation: Theoretical work.
Reference(s):
Apparently never published.
J. Devore and R. Hightower. ''The Devore variation of the Codd self-replicating
computer.'' Presented at Artificial Life III, Santa Fe, New
Mexico, 1992.
Description:
A simplification of Codd's automaton.
Title: Sexually reproducing cellular automata.
Author(s):
Paul M. B. Vitányi.
Year(s): 1973-74.
Model: Two-dimensional, 5-neighbor, cellular
automaton with 29 states per cell (like
von Neumann) or
two-dimensional, 5-neighbor cellular automaton with 8 states per cell
(like Codd).
Implementation: Theoretical work.
Reference(s):
1. P. M. B. Vitanyi. ``Sexually reproducing cellular automata.''
Mathematical Biosciences, Vol. 18, pages 23-54, 1973.
2. P. M. B. Vitanyi. ``Genetics of reproducing automata.'' In:
Proc. 1974 Conference on Biologically Motivated Automata Theory,
IEEE, New York, N. Y., 1974, pages 166-171.
(Related paper: P. M. B. Vitanyi. ``On a problem in the collective behavior
of automata.'' Discrete Mathematics, Vol. 14, pages 99-101 (1976). )
Description: Sexual reproduction is modeled and
investigated in the formal framework of
John von Neumann's theory of self-reproducing cellular automata.
It is argued that the transition from asexual to sexual reproduction
necessitates a change in number and structure of the genetic tapes
involved. To an asexually reproducing automaton only one genetic tape
is attached, viz. the description which enables the automaton to
construct cell for cell a replica of itself. The sexually reproducing
automaton, however, must possess two, nearly identical, genetic tapes
of a deviating structure, i.e., programs partitioned into sections
embodying the various construction and behavioral algorithms to be
executed. It is shown that the recombination of the parents'
characteristics in the offspring closely conforms to recombination in
nature. Similarities and differences with biological systems are
discussed.
The model accounts for many biological phenomena that are known and
predicts phenomena that are not yet known, e.g., genetics-linked
sterility or transsexuality. This may be of interest to biologists.
Title: Self-replicating molecular machines.
Author(s): Richard Laing.
Year(s): 1975-1977.
Model: Artificial molecular machines. Replication is attained
by self-inspection.
Implementation: Theoretical work.
Reference(s):
1. R. Laing.
``Some alternative reproductive strategies in artificial molecular
machines.''
Journal of Theoretical Biology, Vol. 54, pages 63-84, 1975.
2. R. Laing. ``Automaton introspection.''
Journal of Computer and System Sciences, Vol. 13, pages 172-183,
1976.
3. R. Laing. ``Automaton models of reproduction by self-inspection.''
Journal of Theoretical Biology, Vol. 66, pages 437-456, 1977.
Description: The artificial molecular machines
introduced by Laing are chains (possibly folded and interconnected) of
basic molecule-like constituents. As put by Laing (1977): ``The basic
components of our system consist of strands or strings of
primitive constituent finite state automata, these component strings
being in sliding contact... A primitive constituent of a string can be
in an activated or passive state. An active primitive constituent in
contact with a passive constituent of another string will interact
with the passive constituent in precisely defined ways only. These
ways include changing the state of the contacted passive
primitive, reacting to the state of the contacted passive
primitive, sliding to the next neighbor of the contacted
passive primitive. Since one string (an active string) can be designed
to play the part of any Turing machine finite-state read-head, and
another string (a passive string) can be designed to play the part of
a Turing machine tape, we can carry out any Turing computation in this
kinematic machine system.''
Related work:
Morris.
Title: Self-replicating interstellar probes.
Author(s): R. A. Freitas, Jr.
Year(s): 1980-83.
Model: Von Neumann kinematic model assumed (a model
that preceded that of the cellular automaton).
Implementation: Exploratory engineering design.
Reference(s):
1. R. A. Freitas, Jr., ``A self-reproducing interstellar probe,''
Journal of the British Interplanetary Society, Vol. 33,
July 1980, pages 251-264.
2. R. A. Freitas, Jr. and F. Valdes, ``Comparison of
reproducing and non-reproducing starprobe strategies for galactic
exploration,'' Journal of the British Interplanetary Society,
Vol. 33, November 1980, pages 402-408.
3. R. A. Freitas, Jr., ``Terraforming Mars and Venus using machine
self-replicating systems,''
Journal of the British Interplanetary Society, Vol. 36,
March 1983, pages 139-142.
Description: Paper (1) was the first quantitative
engineering analysis of a complete self-replicating interstellar
probe, with special attention to materials, structural, and functional
closure
issues.
The other papers examined two specific far-future
space applications of machine replication technology.
Title: Self-replicating lunar factory.
Author(s): R. A. Freitas, Jr. and W. P. Gilbreath.
Year(s): 1980.
Model: Von Neumann kinematic model assumed (a model
that preceded that of the cellular automaton).
Implementation: Exploratory engineering design.
Reference(s):
1. R. A. Freitas, Jr. and W. P. Gilbreath, editors.
Advanced automation for space missions: Proceedings of the 1980
NASA/ASEE summer study, chapter 5: Replicating Systems Concepts:
Self-replicating Lunar Factory and Demonstration.
NASA, Scientific and Technical Information Branch (available from
U.S. G.P.O., Conference Publication 2255), Washington, D.C., 1982.
2. R. A. Freitas, Jr. and W. Zachary, ``A self-replicating,
growing lunar factory,'' In J. Grey and L. A. Hamdan, Eds., Space
Manufacturing - Proceedings of the Fifth Princeton/AIAA/SSI Conference
on Space Manufacturing, 18-21 May 1981, Princeton University, AIAA,
New York, 1981, pages 109-119.
3. R. A. Freitas, Jr., T. J. Healy, and J. E. Long, ``Advanced
automation for space missions,'' Proceedings of 7th International Joint
Conference on Artificial Intelligence (IJCAI-81), 24-28 August 1981,
Vancouver, Canada, pages 803-808.
4. R. A. Freitas, Jr., ``Report on the NASA/ASEE summer study on
advanced automation for space missions,'' Journal of the British
Interplanetary Society, Vol. 34, September 1981, pages 407-408.
5. R. A. Freitas Jr., T. J. Healy, and J. E. Long, ``Advanced
automation for space missions,''
Journal of the Astronautical Sciences,
Vol. 30, January-March 1982, pages 1-11.
See the following references for popular discussions of the NASA study:
1. R. A. Freitas, Jr., ``Roboclone: Self-replicating robots,'' Omni,
Vol. 5, July 1983, pages 44-47.
2. R. A. Freitas, Jr., ``Building Athens without the slaves,''
Technology Illustrated, Vol. 3, August 1983, pages 16-20.
3. Steven Levy,
Artificial Life, Vintage Books/Random House, NY,
1992, pages 34-42.
Description: In 1980 NASA convened a committee of
experts to conduct an in-depth study of various issues related to
space exploration. Among these studies was one that raised the
possibility of planting a ``seed'' factory on the moon that would then
self-replicate to populate a large surface, using local lunar
material. The study introduced the concept of closure engineering,
studying qualitative closure (can all parts be made?), quantitative closure
(can enough parts be made?), and throughput closure (can parts be made
fast enough?).
Further information is available
here
and also
here.
Title: Self-replicating programs.
Author(s): John Burger, David Brill, and Filip Machi.
Year(s): 1980.
Model: Computer program.
Implementation: Computer simulation.
Reference(s):
J. Burger, D. Brill, and F. Machi. ``Self-reproducing programs.''
Byte, Vol. 5, pages 72-74, 1980.
See
The Quine Page for several examples of self-replicating programs.
Title: Self-replicating loop.
Author(s):
Christopher G. Langton.
Year(s): 1984.
Model: Two-dimensional, 5-neighbor cellular automaton with 8
states per cell.
Implementation: Computer simulation.
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.,
and
Morita and Imai
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.
Figure(s): 2.
Title: Core war.
Author(s): A. K. Dewdney.
Year(s): 1984-89.
Model: An assembly language.
Implementation: Computer simulation.
Reference(s):
1. A. K. Dewdney. ``Core war.''
Scientific American, Vol. 250, No. 5, pages 15-19, May 1984.
2. A. K. Dewdney. ``Core war.''
Scientific American, Vol. 252, No. 3, pages 14-19, March 1985.
3. A. K. Dewdney. ``Core war tournament.''
Scientific American, Vol. 256, No. 1, pages 8-11, January 1987.
4. A. K. Dewdney. ``Of worms, viruses and core war.''
Scientific American, Vol. 260, No. 3, pages 90-93, March 1989.
Description: Core war is a virtual computer
environment in which computer programs ``do battle'' with each other.
Some of these programs have self-replicating features.
Related work:
Ray.
Title: Self-replicating loop.
Author(s): John Byl.
Year(s): 1989.
Model: Two-dimensional, 5-neighbor cellular automaton with 6
states per cell.
Implementation: Computer simulation.
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).
Title: Implementation of
von Neumann's universal constructor on a SIMD machine.
Author(s): Jacqueline Signorini.
Year(s): 1989.
Model: Two-dimensional, 5-neighbor cellular automaton with 29
states per cell.
Implementation: SIMD (single-instruction multiple-data)
machine.
Reference(s):
J. Signorini.
``How a SIMD machine can implement a complex cellular automaton?
A case study: von Neumann's 29-state cellular automaton.''
In Supercomputing '89: Proceedings of the ACM/IEEE Conference, pages
175-186, 1989.
Description:
This study was part of an effort to simulate
von Neumann's model. Signorini concentrated on the 29-state transition
rule, discussing its implementation on a SIMD computer.
Von Neumann's constructor
is divided into many
functional blocks known as organs. In addition to implementation of
the transition rule, Signorini also presented the implementation
of three such organs: a pulser, a decoder, and a periodic pulser.
Related work:
Pesavento,
Beuchat and Haenni.
Title: Self-replication in typogenetics.
Author(s): Harold C. Morris.
Year(s): 1989.
Model: Typogenetics.
Implementation: Computer simulation.
Reference(s):
H. C. Morris.
``Typogenetics: A logic for artificial life.''
In C. G. Langton, editor, Artificial Life,
vol. VI of SFI Studies in the Sciences of Complexity,
pages 369-395. Addison-Wesley, 1989.
Description: Typogenetics was first introduced by
Douglas Hofstadter in his book Godel, Escher, Bach (1979) as a
formal system for describing operations on DNA strands. A
typogenetics string, or strand, has a double aspect: it is a
coded message prescribing operations, and it is the very operand or
data those operations will work on. Self-replication in typogenetics
can be achieved in two ways (Morris, 1989): (1) a string can extend
itself horizontally along one level and then cut itself into two
pieces which are either already replicas of their parent or will beget
such replicas, or (2) use a copy operation to create a double strand
that will separate into two daughters that are either already copies
of their parent or will grow into such copies.
Related work:
Varetto,
Laing.
Title: Tierra.
Author(s):
Tom Ray.
Year(s): 1992-present.
Model: An assembly language.
Implementation: Computer simulation.
Reference(s):
T. S. Ray.
``An approach to the synthesis of life.''
In C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, editors,
Artificial Life II, volume X of SFI Studies in the Sciences
of Complexity, pages 371-408, Redwood City, CA, 1992. Addison-Wesley.
Further references:
Tierra home page.
Description:
``Tierra'' is a virtual world, consisting of computer programs that can
undergo evolution. In contrast to
evolutionary algorithms where fitness is defined by the user, the
Tierra ``creatures'' (programs) receive no such direction. Rather,
they compete for the natural resources of their computerized
environment, namely, CPU time and memory. Since only a finite amount
of these are available, the virtual world's natural resources are
limited, as in nature, giving rise to competition between
creatures. Ray (1992) observed the formation of an ``ecosystem''
within the Tierra world, including organisms of various sizes,
parasites, and hyper-parasites. To get the system going, Ray
inoculated it with an 80-line self-replicating computer program
written in the Tierran assembly language.
Related work:
Dewdney.
Title: Self-replicating loops.
Author(s):
James A. Reggia,
Steven L. Armentrout,
Hui-Hsien Chou,
and Yun Peng.
Year(s): 1993.
Model: Two-dimensional cellular automaton with either
6 or 8 states per cell and a neighborhood of either 5 or 9 cells.
Implementation: Computer simulation.
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).
Title: Self-replication in typogenetics.
Author(s): Louis Varetto.
Year(s): 1993.
Model: Typogenetics.
Implementation: Computer simulation.
Reference(s):
L. Varetto.
``Typogenetics: An artificial genetic system.''
Journal of Theoretical Biology, Vol. 160, pages 185-205, 1993.
Description:
See Morris.
Title: Embryonics (Embryonic Electronics).
Author(s):
Daniel Mange,
Eduardo Sanchez,
André Stauffer,
Gianluca Tempesti,
Dominik Madon,
Moshe Sipper,
Pierre Marchal, Serge Durand, and Christian Piguet.
Year(s): 1993-present.
Model: Multicellular automaton.
Implementation: Hardware (reconfigurable processors known
as field-programmable gate arrays, or FPGAs).
Reference(s):
1. D. Mange and A. Stauffer.
``Introduction to embryonics: Towards new self-repairing and
self-reproducing hardware based on biological-like properties.''
In N. M. Thalmann and D. Thalmann, editors, Artificial Life and
Virtual Reality, pages 61-72. John Wiley, England, 1994.
2. P. Marchal, C. Piguet, D. Mange, A. Stauffer, and S. Durand.
``Embryological development on silicon.''
In R. A. Brooks and P. Maes, editors, Artificial Life IV,
pages 365-370, Cambridge, Massachusetts, 1994. The MIT Press.
3. D. Mange, M. Goeke, D. Madon, A. Stauffer, G. Tempesti, and S. Durand.
``Embryonics: A new family of coarse-grained field-programmable
gate array with self-repair and self-reproducing properties.''
In E. Sanchez and M. Tomassini, editors, Towards Evolvable
Hardware, volume 1062 of Lecture Notes in Computer Science, pages
197-220. Springer-Verlag, Heidelberg, 1996.
4. P. Marchal, P. Nussbaum, C. Piguet, S. Durand, D. Mange, E. Sanchez,
A. Stauffer, and G. Tempesti.
``Embryonics: The birth of synthetic life.''
In E. Sanchez and M. Tomassini, editors, Towards Evolvable
Hardware, volume 1062 of Lecture Notes in Computer Science, pages
166-196. Springer-Verlag, Heidelberg, 1996.
5. M. Sipper, D. Mange, and A. Stauffer.
``Ontogenetic hardware.''
BioSystems, Vol. 44, No. 3, pages 193-207, 1997.
6. D. Mange, D. Madon, A. Stauffer, and G. Tempesti.
``Von Neumann revisited: A Turing machine with self-repair and
self-reproduction properties.''
Robotics and Autonomous Systems, Vol. 22, No. 1, pages 35-58, 1997.
7. D. Mange, E. Sanchez, A. Stauffer, G. Tempesti, P. Marchal, and C. Piguet,
``Embryonics: A new methodology for designing field-programmable gate
arrays with self-repair and self-replicating properties,''
IEEE Transactions on VLSI Systems, vol. 6, no. 3, pp. 387-399,
September 1998.
Other references are available by contacting the authors.
See also
Embryonics page and
POE page.
Description:
The embryonics (embryonic electronics) project is a joint collaboration
between the
Logic Systems Laboratory
and the
Centre Suisse d'Electronique et de Microtechnique SA. The ultimate
objective is the construction of large-scale integrated circuits,
exhibiting properties such as self-repair (healing), self-replication,
and evolution, found up until now only in living beings. Such systems
will be more robust than current-day ones, able to function within
complex dynamic environments which not only cannot be fully specified
in advance, but furthermore may change in time. Essentially,
embryonics is a CA-based approach in which three biologically inspired
principles are employed: multicellular organization, cellular
differentiation, and cellular division.
Figure(s): 3 and 4.
Title: Self-replicating loop.
Author(s):
Moshe Sipper.
Year(s): 1994.
Model: Two-dimensional, 9-neighbor,
non-uniform cellular automaton with 3
states per cell.
(The basic cell is somewhat
more complex as compared to the original CA).
Implementation: Computer simulation.
Reference(s):
1. M. Sipper.
``
Studying artificial life using a simple, general cellular model.''
Artificial Life Journal, Vol. 2, No. 1, pages 1-35, 1995.
The MIT Press, Cambridge, MA.
2. M. Sipper.
``
Non-uniform cellular automata: Evolution in rule space and formation
of complex structures.''
In R. A. Brooks and P. Maes, editors, Artificial Life IV,
pages 394-399, Cambridge, Massachusetts, 1994. The MIT Press.
3. M. Sipper.
Evolution of Parallel Cellular Machines: The Cellular
Programming Approach.
Springer-Verlag, Heidelberg, 1997.
Description:
A small 5-cell self-replicating loop. The underlying model is that
of a
non-uniform cellular automaton in which the local update rule need
not be identical for all grid cells (as is the case with the
original CA).
Furthermore, the cells are somewhat more complex than those of
the original CA: whereas a cell in the original model accesses the
states of its neighbors but may only change its own state, Sipper's
model allows state changes of neighboring cells and rule copying into
them (this latter characteristic can be considered a form of cellular
movement).
Figure(s): 5.
Related work:
Arbib,
Lohn and Reggia.
Title: Synthetic self-replicating molecules.
Author(s): Julius Rebek, Jr.
Year(s): 1994.
Model: Organic chemistry.
Implementation: Bioware.
Reference(s):
J. Rebek, Jr.
``Synthetic self-replicating molecules.''
Scientific American, Vol. 271, No. 1, pages 48-55, July 1994.
Description: From Rebek, Jr. (1994): ``Imagine a
molecule that likes its own shape: finding a copy of itself, it will
fit neatly with its twin, forming for a while a complete entity. If
the original molecule is presented with the component parts of
itself, it will assemble these into additional replicas. The process
will continue as long as the supply of components lasts. My colleagues
and I... have designed such self-assembling molecules and crafted them
in the laboratory... Our organic molecules, although they operate
outside of living systems, help to elucidate some of the essential
principles of self-replication.''
Title: Spontaneous emergence of self-replicating programs.
Author(s):
John R. Koza.
Year(s): 1994.
Model: LISP programs.
Implementation: Computer simulation.
Reference(s):
J. R. Koza,
``Artificial life: Spontaneous emergence of self-replicating and
evolutionary self-improving computer programs,''
Artificial Life III, C. G. Langton, editor, Reading, MA,
1994, vol. XVII of SFI Studies in the Sciences of Complexity, pages
225-262, Addison-Wesley.
Description: While most of the systems described
herein were designed by hand, Koza showed that self-replicating LISP
programs can spontaneously emerge. In his experiment, programs were
randomly created from a number of (hand-designed) basic components, or
functions.
Related work:
Lohn and Reggia.
Title: A self-replicating loop with finite computational
capabilities.
Author(s):
Gianluca Tempesti.
Year(s): 1995.
Model: Two-dimensional, 9-neighbor cellular automaton with 10
states per cell.
Implementation: Computer simulation.
Reference(s):
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, Heidelberg, 1995.
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.
Figure(s): 6.
Related work:
Perrier et al.
Title: Evolution of self-replicating structures.
Author(s):
Jason D. Lohn and
James A. Reggia.
Year(s): 1995.
Model: Two-dimensional cellular automaton.
Implementation: Computer simulation.
Reference(s):
1. J. D. Lohn and J. A. Reggia.
``Discovery of self-replicating structures using a genetic algorithm.''
Proceedings of 1995 IEEE International Conference
on Evolutionary Computation (ICEC'95), pages 678-683, 1995.
2. J. D. Lohn. ``Automated discovery of self-replicating structures in
cellular space automata models.'' Dept. of Computer Science Tech.
Report CS-TR-3677, Univ. of Maryland at College Park, August 1996.
3. J. D. Lohn and J. A. Reggia.
``Automatic discovery of self-replicating structures in cellular automata.''
IEEE Transactions on Evolutionary Computation, vol. 1,
no. 3, pp 165-178, September 1997.
Description: Most of the models of
self-replication in cellular spaces, described herein,
were manually designed, a
difficult and time-consuming process.
Genetic algorithms were introduced by Lohn and Reggia to
discover automata rules that govern emergent self-replicating
processes. Given dynamically evolving automata, identification of
effective fitness functions for self-replicating structures is a
difficult task, and they gave one solution to this problem. A model
consisting of movable automata, called effector automata, embedded in
a cellular space was introduced and discussed in this context. For
cellular automata models, a new method of automata input, called
orientation insensitive input, was introduced and shown to increase the
yield of self-replicating structures found.
Related work:
Sipper,
Koza,
Chou and Reggia.
Title: Self-inspection based replication in cellular automata.
Author(s): Jesùs Ibáñez,
Daniel Anabitarte, Iker Azpeitia,
Oscar Barrera, Arkaitz Barrutieta, Haritz Blanco, and Francisco Echarte.
Year(s): 1995.
Model: Two-dimensional cellular automaton with 16
states per cell.
Implementation: Computer simulation.
Reference(s):
J. Ibáñez, D. Anabitarte, I. Azpeitia,
O. Barrera, A. Barrutieta, H. Blanco, and F. Echarte.
``Self-inspection based reproduction in cellular automata.''
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 564-576.
Springer-Verlag, Heidelberg, 1995.
Description:
The self-replicating process demonstrated by Ibáñez et al.
is based on
self-inspection. One of the interesting properties of their systems
concerns the fact that the loops are not necessarily square ones as with
Langton-like loops.
Title: Simulation of
von Neumann's universal constructor.
Author(s): Umberto Pesavento.
Year(s): 1995.
Model: Two-dimensional, 5-neighbor cellular automaton with 32
states per cell.
Implementation: Computer simulation.
Reference(s):
U. Pesavento.
``An implementation of von Neumann's self-reproducing
machine.''
Artificial Life Journal, Vol. 2, No. 4, pages 337-354, 1995.
The MIT Press, Cambridge, MA.
Description:
A computer simulation of
von Neumann's universal constructor.
Self-replication is not demonstrated since the tape required to describe
the constructor is too large to simulate.
Pesavento used three more states per cell as compared with von
Neumann (32 vs. 29) which resulted in a substantially smaller constructor.
Title: COSMOS.
Author(s):
Tim Taylor.
Year(s): 1995-2001.
Model: An assembly language.
Implementation: Computer simulation.
Reference(s):
1. Tim Taylor.
``Creativity in Evolution: Individuals, Interactions and
Environments.''
Chapter 1 in Peter J Bentley and David W Corne (eds.),
Creative Evolutionary Systems, Morgan Kaufman, 2001.
2. T. J. Taylor.
``From Artificial Evolution to Artificial Life.''
PhD thesis, School of Informatics, University of Edinburgh, 1999
(online version available here).
3. Tim Taylor.
``On Self-Reproduction and Evolvability''.
In D. Floreano, J.-D. Nicoud, F. Mondada (eds.),
Proceedings of the Fifth European Conference on Artificial Life
(ECAL99), Springer-Verlag, 1999.
4. Tim Taylor and John Hallam.
``Replaying the Tape: An Investigation into the Role of Contingency
in Evolution''.
In C. Adami, R. Belew, H. Kitano, and C. Taylor (eds.),
Proceedings of the Sixth International Conference on Artificial
Life (Artificial Life VI), MIT Press, 1998.
5. Tim Taylor and John Hallam.
``Studying Evolution with Self-Replicating Computer Programs''.
In P. Husbands and I. Harvey (eds.),
Proceedings of the Fourth European Conference on Artificial Life
(ECAL97), MIT Press/Bradford Books, 1997.
Description:
COSMOS is a derivative of Tierra and was originally designed to
investigate the evolution of differentiated, parallel
(``multicellular'') programs. A program in COSMOS has a more
complex, cellular-inspired structure than its Tierran
counterpart; the genetic information is represented as a binary
string which is decoded to active instructions using a
genotype-to-phenotype mapping. This mapping could itself be
allowed to evolve, although such experiments have not yet been
conducted. Transcription is controlled by promoters and
repressors (which are produced by the cell itself), allowing for
complex genetic regulatory networks, shifts of reading frame
etc. Programs must collect ``energy tokens'' from the
environment in order to run their code, so programs in COSMOS
are therefore in competition for energy as well as
space. Programs can also compose and transmit arbititrary binary
messages into the environment, which may be received by other
programs. Some experiments were also conducted with
sexually-reproducing programs. For further information, look at reference 2
above. The work was not particularly successful in achieving the
evolution of complex programs (in fact it did not even produce
the parasitic programs observed in Tierra). A major contribution of the
thesis was to analyse the reasons for failure, to identify
weaknesses (both methodological and theoretical) of this kind of
study of self-replicating programs in general, and to suggest ways for
improving evolvability in future systems (see refs 1 and 2). The
PhD thesis also contains an extensive survey of previous
work on self-replication and open-ended evolution (ref 2, Chapter
3).
Related work:
Ray.
Title: A self-replicating loop with universal
computational capabilities.
Author(s):
Jean-Yves Perrier,
Moshe Sipper, and
Jacques Zahnd.
Year(s): 1996.
Model: Two-dimensional, 5-neighbor cellular automaton with 63
states per cell.
Implementation: Computer simulation.
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.
Figure(s): 7.
Related work:
Tempesti.
Title: Self-replication in reversible cellular automata.
Author(s): Kenichi Morita and Katsunobu Imai.
Year(s): 1996-1997.
Model: Two-dimensional, 5-neighbor
reversible cellular automaton.
Implementation: Computer simulation.
Reference(s):
1. K. Morita and K. Imai.
``Self-reproduction in a reversible cellular space.''
Theoretical Computer Science, Vol. 168, pages 337-366, 1996.
2. K. Morita and K. Imai.
``A simple self-reproducing cellular automaton with shape-encoding
mechanism.'' In C. Langton and T. Shimohara, editors,
Artificial Life V: Proceedings of the Fifth
International Workshop on the Synthesis and
Simulation of Living Systems. The MIT Press, Cambridge, MA, 1997.
3. K. Morita and K. Imai.
``Logical universality and self-reproduction in reversible
cellular automata.''
In T. Higuchi, M. Iwata, and W. Liu, editors, Proceedings of The
First International Conference on Evolvable Systems: From Biology to Hardware
(ICES96), volume 1259 of Lecture Notes in Computer Science, pages
152-166. Springer-Verlag, Heidelberg, 1997.
Description:
A reversible cellular automaton is a special type of CA in which every
grid configuration of states has at most one predecessor. Roughly speaking,
it is a ``backward-deterministic'' CA.
Morita and Imai showed that self-replication can be attained in
reversible cellular spaces.
Recent studies suggest that computers based on
reversible logic will be more efficient.
Title: Hardware implementation of one of the ``organs'' of
von Neumann's universal constructor.
Author(s):
Jean-Luc Beuchat and
Jacques-Olivier Haenni.
Year(s): 1997.
Model: Two-dimensional, 5-neighbor cellular automaton with 29
states per cell.
Implementation: Hardware (reconfigurable processors known
as field-programmable gate arrays, or FPGAs).
Reference(s):
1. J.-L. Beuchat and J.-O. Haenni.
``Von Neumann's 29-state cellular automaton: A hardware
implementation.''
Logic Systems Laboratory,
1997. (submitted for publication).
2. M. Sipper, D. Mange, and A. Stauffer.
``Ontogenetic hardware.''
BioSystems, Vol. 44, No. 3, pages 193-207, 1997.
Description:
Beuchat and Haenni constructed a hardware module that
implements a single 29-state cell
of
von Neumann's model. Each module is embedded in a plastic box
whose top face contains a number of connection points and a LED
display showing the current state of the cell. Several such modules
can be fitted together to produce a small cellular array. The sides
of the modules contain electrical contacts, which allow adjacent cells
to transmit information to each other without additional wiring.
Figure(s): 8 and 9.
Title: Spontaneous emergence of self-replicating loops.
Author(s):
Hui-Hsien Chou and
James A. Reggia.
Year(s): 1997.
Model: Two-dimensional, 5-neighbor cellular automaton with 256
states per cell (8 bits, arranged into four distinct bit fields).
Implementation: Computer simulation.
Reference(s):
H.-H. Chou and J. A. Reggia.
``Emergence of self-replicating structures in a cellular automata space.''
Physica D, vol. 110, no. 3-4, pp. 252-276, 1997.
Description: While most of the systems described
herein support the replication of a specific, given structure, Chou
and Reggia explored the possibility of creating a CA universe, a
``primordial soup,'' in which self-replicating structures are not
inoculated ab initio, but rather emerge in a spontaneous manner.
Toward this end, they introduced a CA model in which the cellular state
is divided into four distinct bit fields, thus facilitating the emergence of
self-replication.
Related work:
Lohn and Reggia.
Title: Problem solving during artificial selection of
self-replicating loops.
Author(s):
Hui-Hsien Chou and
James A. Reggia.
Year(s): 1998.
Model: Two-dimensional, 5-neighbor cellular automaton.
Cellular state is divided into a number of distinct bit fields.
Implementation: Computer simulation.
Reference(s):
H.-H. Chou and J. A. Reggia.
``Problem solving during artificial selection of
self-replicating loops.''
Physica D, vol. 115, no. 3-4, pp. 293-312, 1998.
Description: This work suggests a novel approach by
which self-replicating loops can be used as a computational means to
solve a difficult NP-complete problem, known as satisfiability, or SAT
(finding an assignment of variables that satisfies a boolean
predicate). Chou and Reggia show here how a cellular automaton (CA) can
be used as a truly massively parallel machine to solve a hard problem.
This is in contrast to many works (including von
Neumann's seminal one) where the highly parallel CA is used in a
completely serial manner (e.g., by embedding a sequential Turing
machine). As Chou and Reggia note, their model bears interesting
similarities to DNA computing, an emerging and exciting field.
As in their earlier work, the authors used a
CA model in which the cellular state is divided into fields, each of
which can be dealt with independently. This greatly facilitates the
CA's programming. The initial set-up consists of a single
self-replicating loop, containing a generic solution to the
problem. This loop then replicates, each daughter structure being
different than the mother one, thus enumerating all possible solutions
to the problem (the enumeration process). There is then a selection
process that culls unfit solutions by eliminating the loops that
represent them (each loop represents one possible SAT solution). Chou
and Reggia introduced innovative ways to handle these parallel
enumeration and selection processes.
Related work:
Lohn and Reggia.
Title: On the relationship between cellular automata and L-systems:
The self-replication case.
Author(s):
André Stauffer and
Moshe Sipper.
Year(s): 1998.
Model: L-systems and two-dimensional cellular automata.
Implementation: Computer simulation.
Reference(s):
A. Stauffer and M. Sipper.
``On the relationship between cellular automata and L-systems:
The self-replication case.''
Physica D, vol. 116, no. 1-2, pp. 71-80, 1998.
Description: Cellular automata (CA) have been
ubiquitously used over the years to study the issue of
self-replication. The L-systems model, on the other hand, is
naturally suited for modeling growth processes, of which replication
is a special case. The goals of this work are: (1) to show how
L-systems can be used to specify self-replicating structures, and (2)
to explore the relationship between L-systems and CAs. Stauffer and
Sipper conclude that the bridge between CAs and L-systems seems to
offer a promising approach in the study of self-replication, and, more
generally, of growth processes in CAs.
Title: A structurally dissolvable self-reproducing loop.
Author(s):
Hiroki Sayama.
Year(s): 1998.
Model: Two-dimensional, 9-state, 5-neighbor
cellular automaton, similar to Langton's.
Implementation: Computer simulation.
Reference(s):
H. 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.
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.
Related work:
Langton.
Title: Evoloop: An evolving SDSR loop.
Author(s):
Hiroki Sayama.
Year(s): 1998-1999.
Model: Two-dimensional, 9-state, 5-neighbor
cellular automaton which is similar to
Langton's CA.
Implementation: Computer simulation.
Reference(s):
1. H. 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.
2. H. 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.
3. H. Sayama: ``Constructing Evolutionary Systems on a Simple
Deterministic Cellular Automata Space'', Ph.D. Dissertation,
Department of Information Science, Graduate School of Science, University
of Tokyo, 1998.
Description:
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 self-reproductive mechanism of the SDSR loop and modifying its initial
configuration slightly.
Related work:
Langton, Sayama.
Title: JohnnyVon: Self-replicating automata in continuous
two-dimensional space.
Author(s): Arnold Smith,
Peter Turney,
Robert Ewaschuk.
Year(s): 2002.
Model: mobile automata, two-dimensional continuous space,
virtual physics.
Implementation: Computer simulation.
Reference(s):
Smith, A., Turney, P., and Ewaschuk, R. (2002).
JohnnyVon: Self-replicating automata in continuous
two-dimensional space. NRC Technical Report ERB-1099.
National Research Council Canada.
Description:
JohnnyVon is an implementation of self-replicating automata in continuous
two-dimensional space. Two types of particles drift about in a virtual
liquid. The particles are automata with discrete internal states but
continuous external relationships. Their internal states are governed by
finite state machines but their external relationships are governed by a
simulated physics that includes brownian motion, viscosity, and spring-like
attractive and repulsive forces. The particles can be assembled into
patterns that can encode arbitrary strings of bits. If an arbitrary seed
pattern is put in a soup of separate individual particles, the pattern will
replicate by assembling the individual particles into copies of
itself. Also, given sufficient time, a soup of separate individual
particles will eventually spontaneously form self-replicating patterns.
Title: Squirm3 - Self-replicating molecules in an artificial chemistry.
Author(s):
Tim J. Hutton.
Year(s): 2002-present.
Model: mobile automata, concrete artificial chemistry.
Implementation: CA, computer simulation.
Reference(s):
1. T.J.Hutton "Evolvable Self-Replicating Molecules in an Artificial Chemistry" Artificial Life 8(4): 341-356, 2002.
2. T.J.Hutton "Simulating Evolution's First Steps" 7th European Conference on Artificial Life (poster), Dortmund, Germany, 14-17th September 2003.
3. T.J.Hutton "Information-Replicating Molecules with Programmable Enzymes" Invited talk at Sixth International Conference on Humans and Computers, Session 1: Artificial Life and Artificial Chemistry. Aizu-Wakamatsu, Japan, 28-30th August 2003.
Description:
Simple rules determine what happens when 'atoms' (eg. e8, a1, f3) bump into each other. Eight rules (reactions) are sufficient to cause a chain of linked atoms (eg. e8-a1-b1-c1-d1-f1) to replicate itself when there are sufficient atoms in state 0 around (eg. e0, a0, f0). Catalytic properties can be added to the rules, making the system a simple model of early RNA replicators or similar. Research investigates whether open-ended evolution can be achieved in such a system.