Dynamics, Emergent Computation, and Evolution in Cellular Automata

Wim Hordijk, LIRMM, Montpellier

March 21, 2005, 10 AM

INRIA Rhône-Alpes 655 avenue de l'Europe Montbonnot (Grenoble)

Abstract

Many systems in nature produce complicated patterns that emerge from local interactions of simple individual components that live in some spatially extended world, without the existence of a central control. Examples of emergent pattern formation in such decentralized spatially extended systems include the foraging paths of social insects, spiral waves in aggregating amoebae, and synchronized oscillations in the brain. Often, these emergent patterns give rise to some form of globally coordinated behavior, or global information processing. For example, an ant colony decides what the shortest path is to some food source, amoebae decide when and where to aggregate to reproduce or find the highest concentrations of food, and the brain classifies sensory inputs.

This global information processing in decentralized spatially extended systems, mediated by emergent pattern formation, is known as emergent computation. However, there is still little understanding of how the dynamics (i.e., the pattern forming behavior) of these systems gives rise to emergent computation, or how such systems and their behaviors and (emergent) computational abilities have evolved.

In this talk, I will give an overview of the Evolving Cellular Automata (EvCA) project, which provides a framework for studying the relations among dynamics, emergent computation, and evolution in decentralized spatially extended systems. In the EvCA project, a genetic algorithm (a simple model of an evolutionary process) is used to evolve cellular automata (simple models of decentralized spatially extended systems) to perform certain computational tasks that require global information processing. The results of this project provide significant insights into emergent computation and its evolution.

Contact: Hidde de Jong