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
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.
More From encyclopedia.com
Artificial Life , Artificial life (also known as "ALife") is an interdisciplinary study of life and lifelike processes by means of computer simulation and other method… Atm , ATM Abbrev. for asynchronous transfer mode. 1. A form of switching system designed to minimize the magnitude of switching times. In most switching sy… Plasma Membrane , Plasma membranes envelop all plant and animal cells and all single-celled eukaryotes and prokaryotes , separating them from their environments. Struc… Cell Theory , Cell theory states that the cell is the basic building block of all life forms and that all living things, whether plants or animals, consist of one… Endoplasmic Reticulum , The endoplasmic reticulum (ER) is a series of interconnected membranes or flattened sacs adjacent and connected to the nuclear membrane. The ER comes… Cerebellum , The cerebellum is located at the rear of the brain above the brain stem. It is connected to the spinal cord, brain stem, and cerebral cortex. The fun…
About this article
Updated About encyclopedia.com content Print Article
You Might Also Like