Dissertation abstract

Dynamics, Emergent Computation, and Evolution in Cellular Automata

Wim Hordijk

PhD dissertation, University of New Mexico, 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. Examples of emergent pattern formation in such systems include the foraging and nest-building behavior of social insects, spiral waves in cultures of amoebae, synchronized oscillations in the brain, etc.

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. For example, by means of emergent patterns, 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. These pattern forming behaviors, and the resulting emergent computations, have evolved over time. In other words, many decentralized spatially extended systems have adapted, under the force of natural selection, to use their tendency to produce patterns to perform certain kinds of global information processing that benefit the system as a whole. 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.

My dissertation investigates these relations among dynamics, emergent computation, and evolution in decentralized spatially extended systems. This investigation is done in the context of using genetic algorithms to evolve cellular automata. Cellular automata (CAs) are one of the simplest models of decentralized spatially extended systems in which emergent patterns are observed, and in which emergent computation can take place. Genetic algorithms (GAs) are a simple model of an evolutionary process, and can be used to evolve CAs to perform certain tasks that require global information processing. A new class of models is then 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. These modeling results provide a better understanding of how emergent patterns can give rise to global information processing, and how evolution can produce systems that use their pattern forming behavior to perform emergent computation. The development and subsequent use of this new class of models thus provides a means to study formally the relation among dynamics, emergent computation, and evolution in cellular automata.