Skip to main content

Automata, Cellular

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 discretethat 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 (19031957) and Stanislaw Ulam (19091984) 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 capabilitiesit 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):120123.

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

thiemo krink

Cite this article
Pick a style below, and copy the text for your bibliography.

  • MLA
  • Chicago
  • APA

"Automata, Cellular." Encyclopedia of Science and Religion. . Encyclopedia.com. 21 Oct. 2018 <http://www.encyclopedia.com>.

"Automata, Cellular." Encyclopedia of Science and Religion. . Encyclopedia.com. (October 21, 2018). http://www.encyclopedia.com/education/encyclopedias-almanacs-transcripts-and-maps/automata-cellular

"Automata, Cellular." Encyclopedia of Science and Religion. . Retrieved October 21, 2018 from Encyclopedia.com: http://www.encyclopedia.com/education/encyclopedias-almanacs-transcripts-and-maps/automata-cellular

Learn more about citation styles

Citation styles

Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).

Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.

Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the most-recent information available at these sites:

Modern Language Association

http://www.mla.org/style

The Chicago Manual of Style

http://www.chicagomanualofstyle.org/tools_citationguide.html

American Psychological Association

http://apastyle.apa.org/

Notes:
  • Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
  • In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.