UNIVERSITY OF HERTFORDSHIRE COMPUTER SCIENCE RESEARCH COLLOQUIUM presents "Asynchronous Cellular Automata, Self-Replication and Evolvability" speaker: Chrystopher L. Nehaniv Adaptive Systems Research Group & Algorithms Research Group University of Hertfordshire 23 October 2002 (Wednesday) Lecture Theatre E351 Hatfield Campus 3 - 4 pm Coffee/tea and biscuits will be available. Everyone is Welcome to Attend [Space Permitting] Abstract: Evolvability can be defined as the capacity of a population to generate heritable phenotypic and genotypic variability (cf. [4,5]). To fully explain this wonderfully versatile and open-ended capacity as observed in the case of the evolution of organic life on earth, a Darwinian evolutionary dynamic characterized by heredity, variation, and (natural) selection is, by itself, insufficient. All constructed or artificial evolutionary systems fail so far to display this type of capacity [5,9,12] that opens the "floodgates of evolution" [3]. This represents a current challenge for the scientific understanding of evolution, although progress is being made in identifying properties that appear to play key roles in evolvability (e.g., [2,4]) which we shall briefly survey. Moreover, the genesis and maintenance of individuality in differentiated multicellular organisms [1,6] or higher levels, and even the heritability of fitness itself require explanation [7,8]. Notions of individuality in constructive systems are still in their infancy [13]. Since they were introduced by John Von Neuman and Stanislaw Ulam in the late 1940's (syncrhonous) cellular automata have served as conceptual tools for studying the possiblity of self-replication in constructed systems. The first simple asynchronous cellular automata systems exhibiting limited self-reproductive capacity and heritable variability will be surveyed [10,11], these that force us to refine our notions in working toward a scientific understanding of biological evolvability and toward applications of its principles in constructive biology and engineering. A general technique to obtain asynchronous cellular automata (and more generally asynchronous automata networks with inputs), from whose behaviour one may recovering the behaviour of a the corresponding synchronous cellular automata will be described and illustrated. This represents a universal method and easily applicable method of freeing such automata from global clocks and synchronization. _________________________________________________________________ References 1 Buss, L. W., 1987. The Evolution of Individuality, Princeton. 2 Conrad, M. 1990, The Geometry of Evolution, BioSystems, Vol. 24, pp. 61-81. 3 Dawkins, R. 1989, The Evolution of Evolvability. In: Artificial Life, C. Langton, editor, Addison-Wesley. 4 Kirschner, M. and Gerhart, J. 1998, Evolvability, Proc. Natl. Acad. Sci. USA, Vol. 95, pp. 8420-8427. 5 Wagner, G. P. and Altenberg, L. 1996, Complex Adaptations and the Evolution of Evolvability, Evolution, Vol. 50, No. 3, pp. 967-976. 6 Maynard Smith, J. and Szathmáry, E., 1995. The Major Transitions in Evolution, Freeman. 7 Michod, R. E. and Roze, D. 1999, Cooperation and conflict in the evolution of individuality. III. Transitions in the unit of fitness. In: C. L. Nehaniv, editor, Mathematical & Computational Biology: Computational Morphogenesis, Hierarchical Complexity & Digital Evolution, Lectures on Mathematics in the Life Sciences, American Mathematical Society, Vol. 26: 47-91. 8 Michod, R. E., 1999. Darwinian Dynamics: Evolutionary Transitions in Fitness & Individuality, Princeton. 9 Nehaniv, C. L., 2002, Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network, International Workshop on Semigroups, Automata, and Formal Languages (17-21 June 2002, Crema, Italy). 10 Nehaniv, C. L., 2002. Self-Reproduction in Asynchronous Cellular Automata, Proc. 2002 NASA/DoD Conference on Evolvable Hardware, IEEE Computer Society Press, pp. 201-209, 2002. 11 Nehaniv, C. L., (in press). Evolution in Asynchronous Cellular Automata, Artificial Life VIII, MIT Press. 12 Nehaniv, C. L. guest editor, (in press). Special Issue on Evolvability, BioSystems. 13 Nehaniv, C. L. and Dautenhahn, K., 1998. Self-Replication and Reproduction: Considerations and Obstacles for Rigorous Definitions. In: C. Wilke, S. Altmeyer, and T. Martinetz, editors, Third German Workshop on Artificial Life: Abstracting and Synthesizing the Principles of Life, Verlag Harri Deutsch, pp. 283-290. -- Hertfordshire Computer Science Research Colloquium Abstracts On-line: http://homepages.feis.herts.ac.uk/~nehaniv/colloq/