
John von Neumann, Theory of SelfReproducing Automata.
In the late 1940's eminent mathematician and physicist John von Neumann had become interested in the question of whether a machine can selfreplicate, 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 biochemical or genetic level. Remember that at the time DNA had not yet been discovered as the genetic material in nature.
The study of artificial selfreplicating 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 informationprocessing principles and algorithms involved in selfreplication, 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 selfreplicating system must satisfy and by providing alternative explanations for empirically observed phenomena. The fabrication of artificial selfreplicating machines can also have diverse applications, ranging from nanotechnology to space exploration.
One of the central models used to study selfreplication 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 ndimensional, 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 selfreplication 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 selfreplication, 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 selfreplicating 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 selfreplication.
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: October 16, 2005.
Translation of this page to Belarusian
Events related to selfreplication
Further information (events, journals, and more) can be found
here.
Research on selfreplicating systems
Title: Universal constructorcomputer.
Author(s): John von Neumann (this work was completed
posthumously by Arthur Burks).
Year(s): Late 1940's.
Model: Twodimensional, 5neighbor, cellular automaton with 29
states per cell.
Implementation: Theoretical work (cf.
Signorini,
Pesavento,
Beuchat and Haenni).
Reference(s): J. von Neumann.
Theory of SelfReproducing 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 selfreplication by machines. In particular he asked
whether we can use purely mathematicallogical considerations to
discover the specific features of biological automata that make them
selfreplicating. To conduct a formal investigation of this issue,
von Neumann used the cellular automaton model, conceived by Stanislaw
Ulam.
Von Neumann used twodimensional 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
selfreplicating. 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 selfreplication in
cellular automata bear strong resemblance to those employed by
biological life, discovered during the following decade.
Figure(s): 1.
Title: Mechanical selfreplication.
Author(s): Lionel S. Penrose and Roger Penrose.
Year(s): 1959.
Model: Simple mechanical units.
Implementation: Plywood.
Reference(s):
L. S. Penrose.
``Selfreproducing machines.''
Scientific American, Vol. 200, No. 6., pages 105114, 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 selfreplication 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 5867.
(Described, among others, von Neumann's work.)
2. E. F. Moore, ``Artificial living plants,'' Scientific American,
Vol. 195, October 1956, pages 118126.
(Speculations on applications for machines that can reproduce.)
3. H. Jacobson, ``On models of reproduction,'' American Scientist,
Vol. 46, 1958, pages 255284.
(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 261263.
(Another construction of a simple physical replicator.)
Barricelli ran computer simulations between 19531956 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.''
Title: Selfreplicating 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 selfreproducing universal automata.''
Information and Control, Vol. 9, pages 177189, 1966.
Description:
Arbib presented a universal array in which the selfreplicating 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 selfreproducing
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 selfreproducing automaton; but rather that, given components of one level
of complexity, we may use them to obtain selfreproducing aggregates
of an arbitrarily higher level of complexity...''
Related work:
Sipper,
Lohn and Reggia.
Title: Universal constructorcomputer.
Author(s): E. F. Codd.
Year(s): 1968.
Model: Twodimensional, 5neighbor 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 constructorcomputer
was simplified by Codd who used an 8state,
5neighbor cellular space. Selfreplication is obtained as a special
case of universal construction, just as with von Neumann's work.
Title: Simple nontrivial selfreplicating machines.
Author(s): Alvy Ray Smith.
Year(s): 196869.
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 selfreproducing 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 709725, Redwood City, CA, 1992. AddisonWesley.
Description:
Von Neumann's proof of the possibility of machine selfreplication
is achieved via a booklength constructive proof. Smith provided a
twopage proof of the possibility of machine selfreplication (thus
his proof is existence rather than constructive). Whereas von Neumann
required both computation universality and construction universality
of his selfreplicating machines, Smith showed that computational
universality alone suffices. Smith (1992) noted that ``the proof here
reduces the problem of selfconstruction to a computation problem,
which means that no machinery beyond ordinary computation theory is
required for selfreproduction.''
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 selfreplication:
Chapter 1: ``Von Neumann's selfreproducing automata,`` Arthur W. Burks,
pages 364.
Chapter 4: ``Selfdescribing Turing machines and selfreproducing cellular
automata,`` J. W. Thatcher, pages 103131.
Chapter 6: ``Machine models of selfreproduction,`` Edward F. Moore,
pages 187203.
Chapter 8: ``The abstract theory of selfreproduction,'' John Myhill,
pages 206218.
Title: Periodicity in generations of automata.
Author(s):
John Case.
Year(s): 197174.
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 selfdescribing Turing machines.''
Journal of the Association for Computing Machinery, Vol. 18,
pages 329338, 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 1532, 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: Selfreplicating 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: Selfreproducing
programs.'' Software Practice and Experience, Vol. 2, pages
397400, 1972.
See
The Quine Page for several examples of selfreplicating programs.
Title: Selfreplicating computer.
Author(s): John Devore.
Year(s): Early 1970's.
Model: Twodimensional, 5neighbor 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 selfreplicating
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): 197374.
Model: Twodimensional, 5neighbor, cellular
automaton with 29 states per cell (like
von Neumann) or
twodimensional, 5neighbor 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 2354, 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 166171.
(Related paper: P. M. B. Vitanyi. ``On a problem in the collective behavior
of automata.'' Discrete Mathematics, Vol. 14, pages 99101 (1976). )
Description: Sexual reproduction is modeled and
investigated in the formal framework of
John von Neumann's theory of selfreproducing 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., geneticslinked
sterility or transsexuality. This may be of interest to biologists.
(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 steadystate population of reproducing automata as a function of a given start population. That is the relevance to selfreplicating 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 selfinspection,
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.''
Related work:
Morris.
Title: Selfreplicating interstellar probes.
Author(s): R. A. Freitas, Jr.
Year(s): 198083.
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 selfreproducing interstellar probe,''
Journal of the British Interplanetary Society, Vol. 33,
July 1980, pages 251264.
2. R. A. Freitas, Jr. and F. Valdes, ``Comparison of
reproducing and nonreproducing starprobe strategies for galactic
exploration,'' Journal of the British Interplanetary Society,
Vol. 33, November 1980, pages 402408.
3. R. A. Freitas, Jr., ``Terraforming Mars and Venus using machine
selfreplicating systems,''
Journal of the British Interplanetary Society, Vol. 36,
March 1983, pages 139142.
Description: Paper (1) was the first quantitative
engineering analysis of a complete selfreplicating interstellar
probe, with special attention to materials, structural, and functional
closure
issues.
The other papers examined two specific farfuture
space applications of machine replication technology.
Title: Selfreplicating 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:
Selfreplicating 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 selfreplicating,
growing lunar factory,'' In J. Grey and L. A. Hamdan, Eds., Space
Manufacturing  Proceedings of the Fifth Princeton/AIAA/SSI Conference
on Space Manufacturing, 1821 May 1981, Princeton University, AIAA,
New York, 1981, pages 109119.
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 (IJCAI81), 2428 August 1981,
Vancouver, Canada, pages 803808.
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 407408.
5. R. A. Freitas Jr., T. J. Healy, and J. E. Long, ``Advanced
automation for space missions,''
Journal of the Astronautical Sciences,
Vol. 30, JanuaryMarch 1982, pages 111.
See the following references for popular discussions of the NASA study:
1. R. A. Freitas, Jr., ``Roboclone: Selfreplicating robots,'' Omni,
Vol. 5, July 1983, pages 4447.
2. R. A. Freitas, Jr., ``Building Athens without the slaves,''
Technology Illustrated, Vol. 3, August 1983, pages 1620.
3. Steven Levy,
Artificial Life, Vintage Books/Random House, NY,
1992, pages 3442.
Description: In 1980 NASA convened a committee of
experts to conduct an indepth 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
selfreplicate 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: Selfreplicating 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. ``Selfreproducing programs.''
Byte, Vol. 5, pages 7274, 1980.
See
The Quine Page for several examples of selfreplicating programs.
Title: Selfreplicating loop.
Author(s):
Christopher G. Langton.
Year(s): 1984.
Model: Twodimensional, 5neighbor cellular automaton with 8
states per cell.
Implementation: Computer simulation.
Reference(s):
1. C. G. Langton.
``Selfreproduction in cellular automata.''
Physica D, Vol. 10, pages 135144, 1984.
2. C. G. Langton.
``Studying artificial life with cellular automata.''
Physica D, Vol. 22, pages 120149, 1986.
Description: Langton observed that although the
capacity for
universal construction, as studied by
von Neumann
and
Codd,
is a sufficient condition
for selfreplication, 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 selfreplicating automata which are
much simpler than the universal constructor. These machines, however,
lack any computing and constructing capabilities, their sole
functionality being that of selfreplication.
Langton's selfreplicating structure is a loop constructed in twodimensional, 8state, 5neighbor cellular space, based on one of Codd's elements, known as a periodic emitter. The 86cell 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 cotraveling 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.
Figure(s): 2.
An online demo is available here.
Title: Core war.
Author(s): A. K. Dewdney.
Year(s): 198489.
Model: An assembly language.
Implementation: Computer simulation.
Reference(s):
1. A. K. Dewdney. ``Core war.''
Scientific American, Vol. 250, No. 5, pages 1519, May 1984.
2. A. K. Dewdney. ``Core war.''
Scientific American, Vol. 252, No. 3, pages 1419, March 1985.
3. A. K. Dewdney. ``Core war tournament.''
Scientific American, Vol. 256, No. 1, pages 811, January 1987.
4. A. K. Dewdney. ``Of worms, viruses and core war.''
Scientific American, Vol. 260, No. 3, pages 9093, March 1989.
Description: Core war is a virtual computer
environment in which computer programs ``do battle'' with each other.
Some of these programs have selfreplicating features.
Related work:
Ray.
Title: Selfreplicating loop.
Author(s): John Byl.
Year(s): 1989.
Model: Twodimensional, 5neighbor cellular automaton with 6
states per cell.
Implementation: Computer simulation.
Reference(s):
J. Byl.
``SelfReproduction in small cellular automata.''
Physica D, Vol. 34, pages 295299, 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).
An online demo is available here.
Title: Implementation of
von Neumann's universal constructor on a SIMD machine.
Author(s): Jacqueline Signorini.
Year(s): 1989.
Model: Twodimensional, 5neighbor cellular automaton with 29
states per cell.
Implementation: SIMD (singleinstruction multipledata)
machine.
Reference(s):
J. Signorini.
``How a SIMD machine can implement a complex cellular automaton?
A case study: von Neumann's 29state cellular automaton.''
In Supercomputing '89: Proceedings of the ACM/IEEE Conference, pages
175186, 1989.
Description:
This study was part of an effort to simulate
von Neumann's model. Signorini concentrated on the 29state 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: Selfreplication 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 369395. AddisonWesley, 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. Selfreplication 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): 1992present.
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 371408, Redwood City, CA, 1992. AddisonWesley.
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 hyperparasites. To get the system going, Ray
inoculated it with an 80line selfreplicating computer program
written in the Tierran assembly language.
Related work:
Dewdney.
Title: Selfreplicating loops.
Author(s):
James A. Reggia,
Steven L. Armentrout,
HuiHsien Chou,
and Yun Peng.
Year(s): 1993.
Model: Twodimensional 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 selfdirected replication.''
Science, Vol. 259, pages 12821287, February 1993.
Description:
Reggia et al. presented several small selfreplicating loops, essentially based
on
Langton's work. Their smallest demonstrated loop
consists of 5 cells, embedded in 6state 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).
An online demo is available here.
Title: Selfreplication 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 185205, 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): 1993present.
Model: Multicellular automaton.
Implementation: Hardware (reconfigurable processors known
as fieldprogrammable gate arrays, or FPGAs).
Reference(s):
1. D. Mange and A. Stauffer.
``Introduction to embryonics: Towards new selfrepairing and
selfreproducing hardware based on biologicallike properties.''
In N. M. Thalmann and D. Thalmann, editors, Artificial Life and
Virtual Reality, pages 6172. 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 365370, 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 coarsegrained fieldprogrammable
gate array with selfrepair and selfreproducing properties.''
In E. Sanchez and M. Tomassini, editors, Towards Evolvable
Hardware, volume 1062 of Lecture Notes in Computer Science, pages
197220. SpringerVerlag, 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
166196. SpringerVerlag, Heidelberg, 1996.
5. M. Sipper, D. Mange, and A. Stauffer.
``Ontogenetic hardware.''
BioSystems, Vol. 44, No. 3, pages 193207, 1997.
6. D. Mange, D. Madon, A. Stauffer, and G. Tempesti.
``Von Neumann revisited: A Turing machine with selfrepair and
selfreproduction properties.''
Robotics and Autonomous Systems, Vol. 22, No. 1, pages 3558, 1997.
7. D. Mange, E. Sanchez, A. Stauffer, G. Tempesti, P. Marchal, and C. Piguet,
``Embryonics: A new methodology for designing fieldprogrammable gate
arrays with selfrepair and selfreplicating properties,''
IEEE Transactions on VLSI Systems, vol. 6, no. 3, pp. 387399,
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 largescale integrated circuits,
exhibiting properties such as selfrepair (healing), selfreplication,
and evolution, found up until now only in living beings. Such systems
will be more robust than currentday 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 CAbased approach in which three biologically inspired
principles are employed: multicellular organization, cellular
differentiation, and cellular division.
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 twodimensional 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 selfreplication,
this artificial organism also exhibits selfrepair capabilities,
another biologically inspired phenomenon,
lacking in the other systems presented herein. Such selfreplicating
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
selfreplicating 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).
Figure(s): 3 and 4.
Title: Selfreplicating loop.
Author(s):
Moshe Sipper.
Year(s): 1994.
Model: Twodimensional, 9neighbor,
nonuniform 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 135, 1995.
The MIT Press, Cambridge, MA.
2. M. Sipper.
``
Nonuniform cellular automata: Evolution in rule space and formation
of complex structures.''
In R. A. Brooks and P. Maes, editors, Artificial Life IV,
pages 394399, Cambridge, Massachusetts, 1994. The MIT Press.
3. M. Sipper.
Evolution of Parallel Cellular Machines: The Cellular
Programming Approach.
SpringerVerlag, Heidelberg, 1997.
Description:
A small 5cell selfreplicating loop. The underlying model is that
of a
nonuniform 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 selfreplicating molecules.
Author(s): Julius Rebek, Jr.
Year(s): 1994.
Model: Organic chemistry.
Implementation: Bioware.
Reference(s):
J. Rebek, Jr.
``Synthetic selfreplicating molecules.''
Scientific American, Vol. 271, No. 1, pages 4855, 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 selfassembling 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 selfreplication.''
Title: Spontaneous emergence of selfreplicating 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 selfreplicating and
evolutionary selfimproving computer programs,''
Artificial Life III, C. G. Langton, editor, Reading, MA,
1994, vol. XVII of SFI Studies in the Sciences of Complexity, pages
225262, AddisonWesley.
Description: While most of the systems described
herein were designed by hand, Koza showed that selfreplicating LISP
programs can spontaneously emerge. In his experiment, programs were
randomly created from a number of (handdesigned) basic components, or
functions.
Related work:
Lohn and Reggia.
Title: A selfreplicating loop with finite computational
capabilities.
Author(s):
Gianluca Tempesti.
Year(s): 1995.
Model: Twodimensional, 9neighbor cellular automaton with 10
states per cell.
Implementation: Computer simulation.
Reference(s):
G. Tempesti
``A new selfreproducing 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 555563.
SpringerVerlag, 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 selfreplication.
Tempesti developed a selfreplicating 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 selfreplicating structures.
Author(s):
Jason D. Lohn and
James A. Reggia.
Year(s): 1995.
Model: Twodimensional cellular automaton.
Implementation: Computer simulation.
Reference(s):
1. J. D. Lohn and J. A. Reggia.
``Discovery of selfreplicating structures using a genetic algorithm.''
Proceedings of 1995 IEEE International Conference
on Evolutionary Computation (ICEC'95), pages 678683, 1995.
2. J. D. Lohn. ``Automated discovery of selfreplicating structures in
cellular space automata models.'' Dept. of Computer Science Tech.
Report CSTR3677, Univ. of Maryland at College Park, August 1996.
3. J. D. Lohn and J. A. Reggia.
``Automatic discovery of selfreplicating structures in cellular automata.''
IEEE Transactions on Evolutionary Computation, vol. 1,
no. 3, pp 165178, September 1997.
Description: Most of the models of
selfreplication in cellular spaces, described herein,
were manually designed, a
difficult and timeconsuming process.
Genetic algorithms were introduced by Lohn and Reggia to
discover automata rules that govern emergent selfreplicating
processes. Given dynamically evolving automata, identification of
effective fitness functions for selfreplicating 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 selfreplicating structures found.
Related work:
Sipper,
Koza,
Chou and Reggia.
Title: Selfinspection 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: Twodimensional 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.
``Selfinspection 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 564576.
SpringerVerlag, Heidelberg, 1995.
Description:
The selfreplicating process demonstrated by Ibáñez et al.
is based on
selfinspection. One of the interesting properties of their systems
concerns the fact that the loops are not necessarily square ones as with
Langtonlike loops.
Title: Simulation of
von Neumann's universal constructor.
Author(s): Umberto Pesavento.
Year(s): 1995.
Model: Twodimensional, 5neighbor cellular automaton with 32
states per cell.
Implementation: Computer simulation.
Reference(s):
U. Pesavento.
``An implementation of von Neumann's selfreproducing
machine.''
Artificial Life Journal, Vol. 2, No. 4, pages 337354, 1995.
The MIT Press, Cambridge, MA.
Description:
A computer simulation of
von Neumann's universal constructor.
Selfreplication 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.
An online demo is available here.
Title: COSMOS.
Author(s):
Tim Taylor.
Year(s): 19952001.
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 SelfReproduction and Evolvability''.
In D. Floreano, J.D. Nicoud, F. Mondada (eds.),
Proceedings of the Fifth European Conference on Artificial Life
(ECAL99), SpringerVerlag, 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 SelfReplicating 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, cellularinspired structure than its Tierran
counterpart; the genetic information is represented as a binary
string which is decoded to active instructions using a
genotypetophenotype 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
sexuallyreproducing 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 selfreplicating 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 selfreplication and openended evolution (ref 2, Chapter
3).
Related work:
Ray.
Title: A selfreplicating loop with universal
computational capabilities.
Author(s):
JeanYves Perrier,
Moshe Sipper, and
Jacques Zahnd.
Year(s): 1996.
Model: Twodimensional, 5neighbor cellular automaton with 63
states per cell.
Implementation: Computer simulation.
Reference(s):
J.Y. Perrier, M. Sipper, and J. Zahnd.
``
Toward a viable, selfreproducing universal computer.''
Physica D, Vol. 97, pages 335352, 1996.
Description:
While
Tempesti's loop has finite computational capabilities,
Perrier et al. demonstrated a
selfreplicating 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, selfreplicating
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: Selfreplication in reversible cellular automata.
Author(s): Kenichi Morita and Katsunobu Imai.
Year(s): 19961997.
Model: Twodimensional, 5neighbor
reversible cellular automaton.
Implementation: Computer simulation.
Reference(s):
1. K. Morita and K. Imai.
``Selfreproduction in a reversible cellular space.''
Theoretical Computer Science, Vol. 168, pages 337366, 1996.
2. K. Morita and K. Imai.
``A simple selfreproducing cellular automaton with shapeencoding
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 selfreproduction 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
152166. SpringerVerlag, 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 ``backwarddeterministic'' CA.
Morita and Imai showed that selfreplication can be attained in
reversible cellular spaces.
Recent studies suggest that computers based on
reversible logic will be more efficient.
Some online documents and demos are available here.
Title: Hardware implementation of one of the ``organs'' of
von Neumann's universal constructor.
Author(s):
JeanLuc Beuchat and
JacquesOlivier Haenni.
Year(s): 1997.
Model: Twodimensional, 5neighbor cellular automaton with 29
states per cell.
Implementation: Hardware (reconfigurable processors known
as fieldprogrammable gate arrays, or FPGAs).
Reference(s):
1. J.L. Beuchat and J.O. Haenni.
``Von Neumann's 29state 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 193207, 1997.
Description:
Beuchat and Haenni constructed a hardware module that
implements a single 29state 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.
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 fieldprogrammable 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 dotmatrix 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
25cell ``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.
Figure(s): 8 and 9.
Title: Spontaneous emergence of selfreplicating loops.
Author(s):
HuiHsien Chou and
James A. Reggia.
Year(s): 1997.
Model: Twodimensional, 5neighbor 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 selfreplicating structures in a cellular automata space.''
Physica D, vol. 110, no. 34, pp. 252276, 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 selfreplicating 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
selfreplication.
Related work:
Lohn and Reggia.
Title: Problem solving during artificial selection of
selfreplicating loops.
Author(s):
HuiHsien Chou and
James A. Reggia.
Year(s): 1998.
Model: Twodimensional, 5neighbor 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
selfreplicating loops.''
Physica D, vol. 115, no. 34, pp. 293312, 1998.
Description: This work suggests a novel approach by
which selfreplicating loops can be used as a computational means to
solve a difficult NPcomplete 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 setup consists of a single
selfreplicating 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.
A downloadable demo is available here.
Title: On the relationship between cellular automata and Lsystems:
The selfreplication case.
Author(s):
André Stauffer and
Moshe Sipper.
Year(s): 1998.
Model: Lsystems and twodimensional cellular automata.
Implementation: Computer simulation.
Reference(s):
A. Stauffer and M. Sipper.
``On the relationship between cellular automata and Lsystems:
The selfreplication case.''
Physica D, vol. 116, no. 12, pp. 7180, 1998.
Description: Cellular automata (CA) have been
ubiquitously used over the years to study the issue of
selfreplication. The Lsystems 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
Lsystems can be used to specify selfreplicating structures, and (2)
to explore the relationship between Lsystems and CAs. Stauffer and
Sipper conclude that the bridge between CAs and Lsystems seems to
offer a promising approach in the study of selfreplication, and, more
generally, of growth processes in CAs.
Title: A structurally dissolvable selfreproducing loop.
Author(s):
Hiroki Sayama.
Year(s): 1998.
Model: Twodimensional, 9state, 5neighbor
cellular automaton, similar to Langton's.
Implementation: Computer simulation.
Reference(s):
H. Sayama.
``Introduction of Structural Dissolution into Langton's
SelfReproducing 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.114122,
Los Angeles, California, 1998, MIT Press.
Description:
The ``structurally dissolvable selfreproducing (SDSR) loop'' is a
kind of revision of Langton's selfreproducing (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 selfreproduction. 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.
More information about the SDSR loop is available here.
Title: Evoloop: An evolving SDSR loop.
Author(s):
Hiroki Sayama.
Year(s): 19981999.
Model: Twodimensional, 9state, 5neighbor
cellular automaton which is similar to
Langton's CA.
Implementation: Computer simulation.
Reference(s):
1. H. Sayama: ``Spontaneous Evolution of SelfReproducing Loops
Implemented on Cellular Automata: A Preliminary Report'',
Proceedings of the Second International Conference on Complex
Systems, Y. BarYam, 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.254257, 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 9state, 5neighbor cellular automata
space. It has been realized by enhancing the "adaptability" of
the selfreproductive mechanism of the SDSR loop and modifying its initial
configuration slightly.
Related work:
Langton, Sayama.
More information about the evoloop is available here.
More information plus simulation is available
here.
Title: Squirm3  Selfreplicating molecules in an artificial chemistry.
Author(s):
Tim J. Hutton.
Year(s): 2002present.
Model: mobile automata, concrete artificial chemistry.
Implementation: CA, computer simulation.
Reference(s):
1. T.J.Hutton "Evolvable SelfReplicating Molecules in an Artificial Chemistry" Artificial Life 8(4): 341356, 2002.
2. T.J.Hutton "Simulating Evolution's First Steps" 7th European Conference on Artificial Life (poster), Dortmund, Germany, 1417th September 2003.
3. T.J.Hutton "InformationReplicating Molecules with Programmable Enzymes" Invited talk at Sixth International Conference on Humans and Computers, Session 1: Artificial Life and Artificial Chemistry. AizuWakamatsu, Japan, 2830th 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. e8a1b1c1d1f1) 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 openended evolution can be achieved in such a system.
The papers plus simulations and experimental work are available here.
Title: Nodes  An Environment for Simulating Kinematic SelfReplicating Machines
Author(s):
Will Stevens.
Year(s): 1997present.
Model: mobile logical and mechanical components in continuous twodimensional space.
Implementation: Computer simulation.
Reference(s):
1. W.M.Stevens "NODES: An Environment for Simulating Kinematic SelfReplicating Machines" Proc. of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9) 3944, 2004.
Description:
Particles moving in continuous space with Newtonian laws of motion carrying out logical and mechanical functions (Boolean and arithmetic operations, exerting forces, connecting particles together). These particles are put together to make a selfreplicating system. The system is made from several disconnected components which cooperate together to replicate the entire system.
Further information, animations and simulation software are available here.