Complex Systems: Cellular Automata

A cellular automaton is an abstract net of spatially discrete elements (called cells or atoms) that undergoes changes in a series of discrete intervals of time. At any particular time the set of cells together with their mutual relations configure one particular global state of the automaton. One state follows a previous one through a set of rules, known as dynamical transitions. The dynamical transitions determine the next individual state (e.g., on or off) of each cell, as a function of its previous individual state and of those of its immediate, locally adjacent cells. As the automaton jumps from one global state to the next it implements successive steps of an algorithm, i.e., performs a computation. Given an appropriate set of dynamical transitions cellular automata can compute any function or solve any problem within the powers of any digital computer.

The main interest of cellular automata for complexity studies is that they epitomize some basic characteristics of self-organized systems; in particular they proceed from a set of simple elements, evolving according to simple and usually deterministic rules, to finally become complex structures that exhibit emergent or previously unforeseen patterns of behavior.

Outside the world of specialists the best-known cellular automaton is Conway’s Game of Life, frequently used to illustrate and simulate such phenomena as emergence and self-organization. Conway’s automaton is a simplification and refinement of John von Newman’s scheme for a self-replicating machine or universal constructor, a seminal development in the theory of self-reproducing automata.