Automata, Cellular

A cellular automata (CA) is a network of connected, identical, finite state automata, which are typically arranged in a one-, two-, or three-dimensional grid, where each grid cell corresponds to one automaton. A finite state automaton is a simple mathematical model for processes that can be described by a table of state transitions and limited memory, which only allows immediate calculations without delays. Each automaton has a state and a set of program rules defined in the state transition table. The state transitions are defined as a function of the current state and the state of its neighbors according to the program rules. Time and space in CAs are discrete—that is, they are represented as discrete time steps and a finite number of cells respectively. During runtime, the state of all automata is updated between time step t and t + 1 based on the states of all automata at time t, resulting in synchronized state transitions.

The neighbors of each automaton are defined by a neighborhood topology, typically (but not necessarily) specified as the immediate neighboring cells. In the case of the most common twodimensional grids with square cells, these are often five (center, right, left, above, below) and nine (the five neighborhood and all diagonals) cell neighborhoods. Often CAs are also defined as discrete dynamic systems in contrast to differential equations that describe continuous dynamic systems.

CAs were introduced by computer pioneers John von Neumann (1903–1957) and Stanislaw Ulam (1909–1984) in the 1940s. The original work was published in the 1966 by A.W. Burks. The motivation for this approach was to propose a formal framework to model the dynamics of complex systems by means of repeated local interactions between simple components. In this context, von Neumann wanted to investigate what kind of logical organization of an automaton is sufficiently powerful to produce the self-organization principles found in nature. For this purpose he proposed a CA model with twenty-nine states and a five neighborhood, which has universal computation capabilities—it is powerful enough to calculate any computable task equivalent to a Turing machine.

An important instance of CA is the "game of life," which was introduced by mathematician John H. Conway in 1970. The game of life is a CA that consists of a two-dimensional grid of square cells with a nine neighborhood where each cell (automaton) has just the two states "alive" and "dead." Cells die if they have less than two or more than three live neighbors and become alive if they have exactly three live neighbors. It has been shown that Conway's very simple CA resembles a universal computer. The game of life is capable of producing complex organizational patterns, which, depending on the initial states of the cells, can be static, periodically changing, or moving. Interestingly, the size versus the frequency of state transitions in the game of life follows a power law relationship, which is a typical phenomenon found among a great variety of complex systems, which are in a state between stability and chaos called self-organized criticality. So far no other instance of cellular automata has been found that expresses the same property.

Cellular automata have been mainly investigated in artificial life and complexity science, but have also gained importance in other fields. In biology, CAs serve as simple frameworks for modeling the spatial effects of the interactions between neighbored individuals. In particular, CAs have been used to model space in game theory for various research issues, including the evolution of cooperation.

See also Complexity; Evolutionary Algorithms; Self-organization

Bibliography

gardner, martin. "mathematical games: the fantastic combinations of john conway's new solitaire game 'life'." scientific american 223, no. 4 (1970):120–123.

von neumann, john. the theory of self-reproducing automata, edited and completed by arthur w. burks. urbana: university of illinois press, 1966.

thiemo krink