Artificial Self-Replication
(an old page that might still be of value, but I can’t guarantee all links work… 😏)
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.
General references
Robert A. Freitas Jr., Ralph C. Merkle, Kinematic Self-Replicating Machines, Landes Bioscience, Georgetown, TX, 2004.M. Sipper, Machine Nature: The Coming Age of Bio-Inspired Computing, McGraw-Hill, New York, 2002.
M. Sipper and J. A. Reggia, Go forth and replicate, Scientific American, vol. 285, no. 2, pp. 26-35, August 2001.Special issue of Artificial Life Journal on Self-Replication, Summer 1998.J. A. Reggia, H.-H. Chou, and J. D. Lohn. “Cellular automata models of self-replicating systems,” Advances in Computers, M. Zelkowitz, Ed., vol. 47, pp. 141-183. Academic Press, New York, 1998.M. Sipper. “ If the milieu is reasonable: Lessons from nature on creating life.” Journal of Transfigural Mathematics, Vol. 3, No. 1., pages 7-22, 1997.
M. Sipper. “ An introduction to artificial life.” Explorations in Artificial Life (special issue of AI Expert), pages 4-8, September 1995. Miller Freeman, San Francisco, CA.
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.
(includes a short review section).
Events related to self-replication
ECAL99 – Fifth European Conference on Artificial Life (Sep. 13-17, 1999).Second International Conference on Evolvable Systems: From Biology to Hardware (ICES98) (Sep. 23-26,1998).Artificial Life VI (Jun. 26-29, 1998).ECAL97 – Fourth European Conference on Artificial Life (Jul. 28-31, 1997).The von Neumann Day: Biological inspiration in computer science 40 years from the death of John von Neumann (Jul. 25, 1997).
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.
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.
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.”
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.”
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.
(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.)
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.”
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.”
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.
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.
Figure(s): 2.
An online demo is available here.
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).
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: 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).
An online demo is available here.
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.
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).
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.
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.
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.
More information about the SDSR loop is available here.
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.
More information about the evoloop is available here.
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.
More information plus simulation is available here.
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.
Title: Nodes – An Environment for Simulating Kinematic Self-Replicating Machines
Author(s): Will Stevens
Year(s): 1997-present.
Model: mobile logical and mechanical components in continuous two-dimensional space.
Implementation: Computer simulation.
Reference(s):
1. W.M.Stevens “NODES: An Environment for Simulating Kinematic Self-Replicating Machines” Proc. of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9) 39-44, 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 self-replicating system. The system is made from several disconnected components which cooperate together to replicate the entire system.