For more information contact Luis Rocha at rocha@lanl.gov
Last Modified: December 13, 1999
Many systems in nature produce complicated patterns, which emerge from the local interactions of relatively simple individual components that live in some spatially extended world. Notably, this type of emergent pattern formation often occurs without the existence of a central control. Such systems, consisting of (many) components in a spatially extended world, with local interactions only and no central control, are generally referred to as decentralized spatially extended systems.
Emergent pattern formation in decentralized spatially extended systems often entails an important functionality for the system as a whole. In other words, the emergent patterns give rise to some form of globally coordinated behavior, or global information processing, which is used by the system to sustain itself or make certain decisions. This global information processing in decentralized spatially extended systems, mediated by emergent pattern formation, is known as emergent computation. These pattern forming behaviors, and the resulting emergent computations, have evolved over time. However, there is little understanding of how the dynamics (i.e., the spatio-temporal behavior) of decentralized spatially extended systems gives rise to emergent computation, or even how such systems and their behaviors are produced by an evolutionary process.
I will present an investigation of these relations among dynamics, emergent computation, and evolution in decentralized spatially extended systems. This investigation is done in the context of using a genetic algorithm (GA) to evolve cellular automata (CAs). A new class of models is developed and used to analyze the relation between dynamics and emergent computation in GA-evolved CAs. These models are used to make quantitative predictions about the evolved CAs' computational performances, based on the CAs' emergent dynamics. The development and subsequent use of this new class of models provides a means to study formally the relation among dynamics, emergent computation, and evolution in cellular automata.