Paper abstract

An Overview of Computation in Cellular Automata

Wim Hordijk

In K. Krithivasan and R. Rama (eds.), Formal Language Aspects of Natural Computing, 7-16, 2005.

Cellular Automata (CA) are mathematical models of decentralized spatially extended systems. They consist of a large number of relatively simple individual units, or “cells”, which are connected only locally, without the existence of a central control in the system. Each cell is a simple finite automaton that repeatedly updates its own state, where the new cell state depends on the cell’s current state and those of its immediate (local) neighbors. However, despite the limited functionality of each individual cell, and the interactions being restricted to local neighbors only, the system as a whole is capable of producing intricate patterns, and even of performing complicated computations. In that sense, they form an alternative model of computation, one in which information processing is done in a distributed and highly parallel manner. Because of these properties, CA have been used extensively to study complex systems in nature, such as fluid flow in physics or pattern formation in biology, but also to study information processing (computation) in decentralized spatially extended systems (natural or artificial). Here, we will give a brief overview of the different ways in which computations can be done with cellular automata.