Worlds of David Darling
Encyclopedia of Science
Home > Encyclopedia of Science

cellular automaton

cellular automaton
A cellular automaton is an array of cells that evolves according to a set of rules based on the states of surrounding cells; for example, a cell might be "on" if its four neighbor cells (east, west, north, and south) are also on. The entire array can self-organize into global patterns that may move around the screen. These patterns can be quite complex even though they emerge from just a few very simple rules governing the connections among the cells. Cellular automata are the simplest models of spatially distributed processes. They were first investigated by John von Neumann in about 1952. Von Neumann incorporated a cellular model into his "universal constructor" and also proved that an automaton consisting of cells with four orthogonal neighbors and 29 possible states would be capable of simulating a Turing machine for some configuration of about 200,000 cells. The best-known cellular automaton is Conway's game of Life. Another example is Langton's Ant. The study of cellular automata and their patterns has led to insights into the way structure is built-up in biological and other complex systems, and for this reason forms part of the subject of artificial life.

Related categories