Self-replication, Evolvability and Asynchronicity in Stochastic Worlds

  • Chrystopher L. Nehaniv
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


We consider temporal aspects of self-replication and evolvability – in particular, the massively asynchronous parallel and distributed nature of living systems. Formal views of self-reproduction and time are surveyed, and a general asynchronization construction for automata networks is presented. Evolution and evolvability are distinguished, and the evolvability characteristics of natural and artificial examples are overviewed. Minimal implemented evolvable systems achieving (1) asynchronous self-replication and evolution, as well as (2) proto-cultural transmission and evolution, are presented and analyzed for evolvability. Developmental genetic regulatory networks (DGRNs) are suggested as a novel paradigm for massive asynchronous computation and evolvability. An appendix classifies modes of life (with different degrees of aliveness) for natural and artificial living systems and possible transitions between them.


Cellular Automaton Logical Description Temporal Wave Genetic Regulatory Network Universal Computation 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Nehaniv, C.L. (ed.): BioSystems, vol. 69, pp. 2–3 (2003), Special issue on EvolvabilityGoogle Scholar
  2. 2.
    Adami, C., Ofria, C., Collier, T.C.: Evolution of biological complexity. Proc. Natl. Acad. Sci. U.S.A. 97, 4463–4468 (2000)CrossRefGoogle Scholar
  3. 3.
    Alissandrakis, A., Nehaniv, C.L., Dautenhahn, K.: Synchrony and perception in robotic imitation across embodiments. In: Proc. IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA 2003), pp. 923–930 (2003)Google Scholar
  4. 4.
    Alissandrakis, A., Nehaniv, C.L., Dautenhahn, K.: Towards robot cultures? - learning to imitate in a robotic arm test-bed with dissimilarly embodied agents. Interaction Studies 5(1), 3–44 (2004)CrossRefGoogle Scholar
  5. 5.
    Altenberg, L.: The evolution of evolvability in genetic programming. In: Kinnear, K.E. (ed.) Advances in Genetic Programming, pp. 47–74. MIT Press, Cambridge (1994)Google Scholar
  6. 6.
    Arthur, W.: The Origin of Animal Body Plans: A Study in Evolutionary Developmental Biology, 1st paperback edn. Cambridge (2000)Google Scholar
  7. 7.
    Banzhaf, W.: Artificial regulatory networks and genetic programming. In: Genetic Programming - Theory and Applications, pp. 43–61. Kluwer, Dordrecht (2003)Google Scholar
  8. 8.
    Berners-Lee, T.: Evolvability. In: 7th International WWW Conference, Brisbane, Australia (April 15 1998), keynote address: slides on-line at,
  9. 9.
    Bonner, J.T.: The Evolution of Complexity, by Means of Natural Selection. Princeton University Press, Princeton (1988)Google Scholar
  10. 10.
    Burks, A.W.: Essays on Cellular Automata. University of Illinois Press, Urbana (1970)zbMATHGoogle Scholar
  11. 11.
    Buss, L.W.: The Evolution of Individuality. Princeton University Press, Princeton (1987)Google Scholar
  12. 12.
    Byl, J.: Self-reproduction in small cellular automata. Physica D 34, 295–299 (1989)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Codd, E.F.: Cellular Automata. Academic Press, New York (1968)zbMATHGoogle Scholar
  14. 14.
    Conrad, M.: The geometry of evolution. BioSystems 24(2), 61–81 (1990)CrossRefGoogle Scholar
  15. 15.
    Crutchfield, J.P.: Observing complexity and the complexity of observation. In: Atmanspacher, H. (ed.) Inside versus Outside, pp. 235–272. Springer, Berlin (1993)Google Scholar
  16. 16.
    Darwin, C.: The Origin of Species by Means of Natural Selection, 1st edn. John Murray, London (1859)Google Scholar
  17. 17.
    Darwin, C., Wallace, A.: On the tendency of species to form varieties; and on the perpetuation of varieties and species by natural means of selection. Journal of the Proceedings of the Linnean Society, Zoology 3, 45–62 (1858)Google Scholar
  18. 18.
    Davidson, E.H.: Genomic Regulatory Systems: Development and Evolution. Academic Press, London (2001)Google Scholar
  19. 19.
    Dawkins, R.: The Selfish Gene, Oxford (1976)Google Scholar
  20. 20.
    Dawkins, R.: The evolution of evolvability. In: Langton, C. (ed.) Artificial Life. Addison Wesley, Reading (1989)Google Scholar
  21. 21.
    Dömösi, P., Nehaniv, C.L.: Algebraic Theory of Finite Automata Networks: An Introduction (SIAM Monographs on Discrete Mathematics and Applications), vol. 11. Society for Industrial and Applied Mathematics, Philadelphia (2005)Google Scholar
  22. 22.
    Edmundson, A.C.: A Fuller Explanation: The Synergistic Geometry of R. Buckminster Fuller, Birkhäuser (1987)Google Scholar
  23. 23.
    Egri-Nagy, A., Nehaniv, C.L.: Evolvability of the genotype-phenotype relation in populations of self-replicating digital organisms in a tierra-like system. In: Banzhaf, W., Ziegler, J., Christaller, T., Dittrich, P., Kim, J.T. (eds.) ECAL 2003. LNCS (LNAI), vol. 2801, pp. 238–247. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  24. 24.
    Fogel, L.J., Owen, A.J., Walsh, M.J.: Artificial Intelligence Through Simulated Evolution. John Wiley, Chichester (1966)zbMATHGoogle Scholar
  25. 25.
    Goguen, J.: Requirements engineering as the reconciliation of technical and social issues. In: Jirotka, M., Goguen, J. (eds.) Requirements Engineering: Social and Technical Issues, pp. 165–199. Academic Press, London (1994)Google Scholar
  26. 26.
    Goguen, J.: Formality and informality in requirements engineering. In: Proceedings, Fourth International Conference on Requirements Engineering, pp. 102–108. IEEE Computer Society, Los Alamitos (1996)Google Scholar
  27. 27.
    Holland, J.: Adaptation in Natural and Artificial Systems. MIT Press, Cambridge (1975)Google Scholar
  28. 28.
    Kimura, M.: The neutral theory of molecular evolution. Cambridge Univ. Press, Cambridge (1983)CrossRefGoogle Scholar
  29. 29.
    Kirschner, M., Gerhart, J.: Evolvability. Proc. Natl. Acad. Sci. USA 95, 8420–8427 (1998)CrossRefGoogle Scholar
  30. 30.
    Koza, J.R.: Evolution of subsumption. In: Genetic Programming: On the Programming of Computers by Means of Natural Selection, ch. 13. MIT Press, Cambridge (1992)Google Scholar
  31. 31.
    Koza, J.R.: Genetic Programming II: The Next Generation. MIT Press, Cambridge (1994)Google Scholar
  32. 32.
    Laing, R.: Automaton models of reproduction by self-inspection. Journal of Theoretical Biology 66, 437–456 (1977)CrossRefMathSciNetGoogle Scholar
  33. 33.
    Langton, C.G.: Self-reproduction in cellular automata. Physica D 10, 135–144 (1984)CrossRefGoogle Scholar
  34. 34.
    Langton, C.G.: Studying artificial life with cellular automata. Physica D 22, 120–149 (1986)CrossRefMathSciNetGoogle Scholar
  35. 35.
    Lehman, M.M.: The role and impact of assumptions in software development, maintenance and evolution. In: IEEE International Workshop on Software Evolvability. IEEE Computer Society Press, Los Alamitos (2005), (in press)Google Scholar
  36. 36.
    Leyser, O., Day, S.: Mechanisms in Plant Development. Blackwell, Malden (2003)Google Scholar
  37. 37.
    Lohn, J.D.: Self-replicating systems in cellular space models. In: Nehaniv, C.L. (ed.) Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution. Lectures on Mathematics in the Life Sciences, vol. 26, pp. 11–30. American Mathematical Society, Providence (1999)Google Scholar
  38. 38.
    Lohn, J.D., Reggia, J.A.: Automatic discovery of self replicating structures in cellular automata. IEEE Transactions on Evolutionary Computation 1(3), 165–178 (1997)CrossRefGoogle Scholar
  39. 39.
    Lynch, M., Katju, V.: The altered evolutionary trajectories of gene duplicates. Trends in Genetics 11, 544–549 (2004)CrossRefGoogle Scholar
  40. 40.
    Macias, N.J., Durbeck, L.J.K.: Adaptive methods for growing electronic circuits on an imperfect synthetic matrix. BioSystems 73, 173–204 (2004)CrossRefGoogle Scholar
  41. 41.
    Mange, D., Sanchez, E., Stauffer, A., Tempesti, G., Marchal, P., Piguet, C.: Embryonics: A new methodology for designing field-programmable gate arrays with self-repair and self-replicating properties. In: Micheli, G.D., Ernst, R., Wolf, W. (eds.) Readings in Hardware/Software Co-Design, pp. 643–655. Morgan Kaufmann, San Francisco (2002)CrossRefGoogle Scholar
  42. 42.
    Margulis, L.: Symbiosis in Cell Evolution. W. H. Freeman & Co., New York (1981)Google Scholar
  43. 43.
    Margulis, L., Sagan, D.: Acquiring Genomes: A Theory of the Origins of Species. Basic Books (2002); Foreword by Ernst Mayr Google Scholar
  44. 44.
    Maynard Smith, J.: A darwinian view of symbiosis. In: Margulis, L., Fester, R. (eds.) Symbiosis as a Source of Evolutionary Innovation, pp. 26–39. MIT Press, Cambridge (1991)Google Scholar
  45. 45.
    Maynard Smith, J., Szathmáry, E.: The Major Transitions in Evolution. W. H. Freeman, New York (1995)Google Scholar
  46. 46.
    Michod, R.E.: Eros and Evolution: A Natural Philosophy of Sex. Addison-Wesley, Reading (1995)Google Scholar
  47. 47.
    Michod, R.E.: Darwinian Dynamics: Evolutionary Transitions in Fitness and Individuality, Princeton (1999)Google Scholar
  48. 48.
    Michod, R.E., Roze, D.: Cooperation and conflict in the evolution of individuality. III. transitions in the unit of fitness. In: Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution. Lectures on Mathematics in the Life Sciences, vol. 26, pp. 47–91. American Mathematical Society, Providence (1999)Google Scholar
  49. 49.
    Moore, E.F.: Machine models of self-reproduction. In: Proceedings of the Fourteenth Symposium on Applied Mathematics, pp. 17–33. American Mathematical Society, Providence (1962) (Reprinted in A.W. Burks (ed.) (1968)Google Scholar
  50. 50.
    Morita, K., Imai, K.: A simple self-reproducing cellular automaton with shape-encoding mechanism. In: Langton, C.G., Shimohara, K. (eds.) Artificial Life V, pp. 489–496. MIT Press, Cambridge (1997)Google Scholar
  51. 51.
    Nakamura, K.: Asynchronous cellular automata and their computational ability. Systems, Computers, Controls 5(5), 58–66 (1974); Translated from Japanese, Tsushin, D., Ronbunshi, G.: vol. 57-D(10), pp. 573–580 (October 1974)Google Scholar
  52. 52.
    Nehaniv, C.L.: Evolvability in biology, artifacts, and software systems. In: Proceedings of the Evolvability Workshop at the the Seventh International Conference on the Simulation and Synthesis of Living Systems (Artificial Life 7), Reed College, Portland, Oregon, USA, August 1-2 (2000), On-line at:
  53. 53.
    Nehaniv, C.L.: Evolution in asynchronous cellular automata. In: Standish, R.K., Bedau, M.A., Abbass, H.A. (eds.) Artificial Life VIII: Proc. 8th Intl. Conf. on Artificial Life, pp. 65–73. MIT Press, Cambridge (2002)Google Scholar
  54. 54.
    Nehaniv, C.L.: Internal constraints and ecology in evolution: A case study in tierra. In: Proceedings of the Fifth German Workshop on Artificial Life (GWAL V), pp. 243–252 (2002)Google Scholar
  55. 55.
    Nehaniv, C.L.: Self-reproduction in asynchronous cellular automata. In: Proc. 2002 NASA/DoD Conference on Evolvable Hardware, Alexandria, Virginia, July 15-18, pp. 201–209. IEEE Computer Society Press, Los Alamitos (2002)CrossRefGoogle Scholar
  56. 56.
    Nehaniv, C.L.: Asynchronous automata networks can emulate any synchronous automata network. International Journal of Algebra & Computation 14(5,6), 719–739 (2004); Presented at International Workshop on Semigroups, Automata, and Formal Languages, Crema, Italy (June 2002)Google Scholar
  57. 57.
    Nehaniv, C.L.: The algebra of time. In: Proc. National Conf. of the Japan Society for Industrial and Applied Mathematics, pp. 127–128 (September 1993)Google Scholar
  58. 58.
    Nehaniv, C.L., Dautenhahn, K.: Self-replication and reproduction: Considerations and obstacles for rigorous definitions. In: Proceedings of the Third German Workshop on Artificial Life (GWAL III), pp. 283–290 (1998)Google Scholar
  59. 59.
    Nehaniv, C.L., Dautenhahn, K.: Artificial Life Fundamentals: The Simulation and Synthesis of Living Systems. Springer, Heidelberg (in prep.)Google Scholar
  60. 60.
    Nehaniv, C.L., Rhodes, J.L.: On the manner in which biological complexity may grow. Lectures on Mathematics in the Life Sciences, vol. 26, pp. 93–102 (1999)Google Scholar
  61. 61.
    Nehaniv, C.L., Rhodes, J.L.: Axioms for biological complexity and mathematically rigorous measures of computational capacity: Applications to evolution of computation in cells. In: Bolouri, H., Paton, R. (eds.) Proc. Computation in Cells: An EPSRC Emergent Computing Workshop, April 17-18, pp. 71–76. University of Hertfordshire, U.K. (2000)Google Scholar
  62. 62.
    Nehaniv, C.L., Rhodes, J.L.: The evolution and understanding of biological complexity from an algebraic perspective. Artificial Life 6(1), 45–67 (2000)CrossRefGoogle Scholar
  63. 63.
    Ohno, S.: Evolution by Gene Duplication. Springer, Heidelberg (1970)Google Scholar
  64. 64.
    Orgel, L.E.: Molecular replication. Nature 358, 203–209 (1992)CrossRefGoogle Scholar
  65. 65.
    Parnas, D.: On the criteria to be used in decomposing systems into modules. Communications of the Association for Computing Machinery 15(2), 1052–1058 (1972)Google Scholar
  66. 66.
    Pepper, J.W.: The evolution of evolvability in genetic linkage patterns. In: Nehaniv, C.L. (ed.) Special issue on Evolvability, vol. 69(2-3), pp. 115–126 (2003)Google Scholar
  67. 67.
    Quick, T., Nehaniv, C.L., Dautenhahn, K., Roberts, G.: Evolving embodied genetic regulatory network-driven control systems. In: Banzhaf, W., Ziegler, J., Christaller, T., Dittrich, P., Kim, J.T. (eds.) ECAL 2003. LNCS (LNAI), vol. 2801, pp. 266–277. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  68. 68.
    Rasmussen, S., Chen, L., Deamer, D., Krakauer, D., Packard, N., Stadler, P., Bedau, M.: Transitions from nonliving to living matter. Science 303, 963–965 (2004)CrossRefGoogle Scholar
  69. 69.
    Ray, T.S.: An approach to the synthesis of life. In: Jones, F. (ed.) Artificial Life II, pp. 371–408. Addison-Wesley, Reading (1991)Google Scholar
  70. 70.
    Rechenberg, I.: Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Frommann-Holzboog (1973)Google Scholar
  71. 71.
    Reggia, J.A., Armentrout, S., Chou, H.H., Peng, Y.: Simple systems that exhibit self-directed replication. Science 259, 1282–1288 (1993)CrossRefMathSciNetGoogle Scholar
  72. 72.
    Rendell, L., Whitehead, H.: Culture in whales and dolphins. Behavioral and Brain Sciences 24(2), 309–382 (2001)Google Scholar
  73. 73.
    Ridley, M.: Evolution, 2nd edn. Blackwell Science, Malden (1996)Google Scholar
  74. 74.
    Sapp, J.: Evolution by Association, Oxford (1994)Google Scholar
  75. 75.
    Sayama, H. Constructing Evolutionary Systems on a Simple Deterministic Cellular Automata Space. PhD thesis, Department of Information Science, Graduate School of Science, University of Tokyo (December 1998)Google Scholar
  76. 76.
    Sayama, H.: Introduction of structural dissolution into langton’s self-reproducing loop. In: Adami, C., Belew, R.K., Kitano, H., Taylor, C.E. (eds.) Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life, pp. 114–122. MIT Press, Cambridge (1998), On-line material at,
  77. 77.
    Sayama, H.: A new structurally dissolvable self-reproducing loop evolving in a simple cellular automata space. Artificial Life 5(4), 343–365 (1999)CrossRefGoogle Scholar
  78. 78.
    Schilstra, M., Bolouri, H.: Logical modelling of developmental genetic regulatory networks with netbuilder. In: 2nd Int. Conf. Systems Biology (ICSB 2001). Omnipress (2001)Google Scholar
  79. 79.
    Schilstra, M., Nehaniv, C.L.: The logic of genetic regulation. (submitted)Google Scholar
  80. 80.
    Schwefel, H.-P.: Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie, Birkhäuser (1977)Google Scholar
  81. 81.
    Sigmund, K.: Games of Life, Penguin (1995)Google Scholar
  82. 82.
    Sipper, M.: The artificial self-replication page,
  83. 83.
    Sommerville, I.: Software Engineering, 5th edn. Addison-Wesley, Reading (1996)Google Scholar
  84. 84.
    Szathmáry, E.: Chemes, genes, memes: A classification of replicators. In: Nehaniv, C.L. (ed.) Mathematical and Computational Biology: Computational Morphogenesis, Hierarchical Complexity, and Digital Evolution. Lectures on Mathematics in the Life Sciences, vol. 26, pp. 1–10. American Mathematical Society, Providence (1999)Google Scholar
  85. 85.
    Szostak, J., Bartel, D., Luisi, P.: Synthesizing life. Nature 409, 383–390 (2001)CrossRefGoogle Scholar
  86. 86.
    Tempesti, G.: A new self-reproducing cellular automaton capable of construction and computation. In: Morán, F., Merelo, J.J., Moreno, A., Chacon, P. (eds.) ECAL 1995. LNCS, vol. 929, pp. 555–563. Springer, Heidelberg (1995)Google Scholar
  87. 87.
    Toffoli, T.: Integration of phase-difference relations in asynchronous sequential networks. In: Ausiello, G., Bohm, C. (eds.) Automata, Languages, and Programming (Fifth Colloquium, Udine). LNCS, vol. 62, pp. 457–463. Springer, Heidelberg (1978)Google Scholar
  88. 88.
    Toffoli, T., Margolus, N.: Cellular Automata Machines. MIT Press, Cambridge (1987)Google Scholar
  89. 89.
    Tyrrell, A.M., Sanchez, E., Floreano, D., Tempesti, G., Mange, D., Moreno, J.M., Rosenberg, J., Villa, A.E.P.: Poetic tissue: An integrated architecture for bio-inspired hardware. In: Tyrrell, A.M., Haddow, P.C., Torresen, J. (eds.) ICES 2003. LNCS, vol. 2606, pp. 129–140. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  90. 90.
    Van Belle, T., Ackley, D.H.: Code factoring and the evolution of evolvability. In: GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1383–1390. Morgan Kaufmann, San Francisco (2002)Google Scholar
  91. 91.
    Van Belle, T., Ackley, D.H.: Uniform subtree mutation. In: Foster, J.A., Lutton, E., Miller, J., Ryan, C., Tettamanzi, A.G.B. (eds.) EuroGP 2002. LNCS, vol. 2278, pp. 152–161. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  92. 92.
    van Nimwegen, E., Crutchfield, J.P., Huynen, M.: Neutral evolution of mutational robustness. Proc. Natl. Acad. Sci. U.S.A. 96, 9716–9720 (1999)CrossRefGoogle Scholar
  93. 93.
    van Nimwegen, E., Crutchfield, J.P., Mitchell, M.: Statistical dynamics of the royal road genetic algorithm. In: Eiben, A.E., Rudolph, G. (eds.) Special Issue on Evolutionary Computation. Theoretical Computer Science, vol. 229 (1999)Google Scholar
  94. 94.
    Varela, F.J.: Principles of biological autonomy. North Holland, Amsterdam (1979)Google Scholar
  95. 95.
    Varela, F.J., Maturana, H.R., Uribe, R.: Autopoiesis: The organization of living systems. BioSystems 5(4), 187–196 (1974)CrossRefGoogle Scholar
  96. 96.
    Varshavsky, V.: System time and system timing. In: Nehaniv, C.L., Ito, M. (eds.) Algebraic Engineering, pp. 38–57. World Scientific Press, Singapore (1999)Google Scholar
  97. 97.
    Vitányi, P.M.B.: Sexually reproducing cellular automata. Mathematical Biosciences 18, 23–54 (1973)zbMATHCrossRefMathSciNetGoogle Scholar
  98. 98.
    von Neumann, J.: Probabilistic logics and the synthesis of reliable organisms from unreliable components. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, Princeton, (Annals of Mathematics Studies), vol. 34, pp. 43–98 (1956)Google Scholar
  99. 99.
    von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press, Urbana (1966) (Edited and completed by A. W. Burks)Google Scholar
  100. 100.
    Wagner, G.P. (ed.): The Character Concept in Evolutionary Biology. Academic Press, London (2001)Google Scholar
  101. 101.
    Wagner, G.P., Altenberg, L.: Complex adaptations and the evolution of evolvability. Evolution 50(3), 967–976 (1996)CrossRefGoogle Scholar
  102. 102.
    Watson, J.D., Crick, F.H.C.: Molecular structure of nucleic acids. Nature 171, 737–738 (1953)CrossRefGoogle Scholar
  103. 103.
    Wernick, P., Lehman, M.M.: Software process white box modelling for feast/1. Journal of Systems and Software 46(2-3), 193–201 (1999)CrossRefGoogle Scholar
  104. 104.
    West-Eberhard, M.: Developmental Plasticity and Evolution. Oxford University Press, Oxford (2003)Google Scholar
  105. 105.
    Whiten, A., Goodall, J., McGrew, W.C., Nishida, T., Reynolds, V., Sugiyama, Y., Tutin, C.E.G., Wrangham, R.W., Boesch, C.: Culture in chimpanzees. Nature 399, 682–685 (1999)CrossRefGoogle Scholar
  106. 106.
    Wolpert, L.: The Triumph of the Embryo. Oxford University Press, Oxford (1991)Google Scholar
  107. 107.
    Wright, S.: The role of mutation, inbreeding, crossbreeding, and selection in evolution. In: Proceedings of the Sixth International Congress on Genetics, vol. 1, pp. 356–366 (1932)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Chrystopher L. Nehaniv
    • 1
  1. 1.Adaptive Systems, Algorithms, and BioComputation Research Groups, School of Computer Science & Science and Technology Research InstituteUniversity of Hertfordshire, HatfieldHertfordshireUnited Kingdom

Personalised recommendations