"a seething information matrix" "If AI is the surfer, CA is the sea." (Rudy Rucker)
Cellular Automata were invented by Stanislaw Ulam in the late 1940's and used by John von Neumann in his theoretical investigations of self- replication in machines. A cellular automaton is a lattice of finite automata that all obey transition functions defined by the local context of each cell at any given time.
The cellular grid is usually a rectangular partitioning of one- or two-dimensional space, but higher dimensional CA's are equally possible, just more difficult to visualize. Each cell can assume only a finite number k of values, so if we have a finite grid of N cells, the total number of possible states is also finite, equalling k to the Nth .
The rule fixing the value of each cell at a given moment is a deterministic function of the current value of that cell and the values of the cells in a neighborhood of that cell, (stochastic transitions are sometimes added) and each cell is the same as any other. The state of all the cells is transformed at time=0,1,2, etc. Thus the state is determined at one instant by its state at the previous instant and by the operation of the transition rules operating at every cell simultaneously. It should be noted that while the transition functions are local, the behaviour is global, as are both the lattice structure and the timing regime.(usually some form of "clock" pulse) (although the timing is local in that there are no time-lag effects)
While the system does not change, its states change and reveal unexpectedly dynamic change, including, most importantly Self-Replication
The local rules of CA's are "neighborhood rules." and in 2D automata there are two kinds of neighborhoods, von Neumann neighborhoods, and Moore neighborhoods, the former being restricted to vertical and horizontal, the latter including diagonals. The most famous cellular automaton is the "game of life" invented by John Conway and popularized through Scientific American in 1970. The game of life is described in Poundstone's Recursive Universe. Its neighborhood rules, using the Moore neighborhood, reflect ideas about dying of "isolation" or of "overcrowding." Conway was ablo to prove that the game of life could function as a universal Turing machine and compute any quantity that can be computed. This was by creating "Not", "or", and "if" gates, which are, according to Boole's binary logic, all that is required to derive all logic and to carry out any algorithmically specifiable computation.
The primary features of CA's are: parallelism (each individual cell updates independently), locality (updating by neighborhood rules), and homogeneity (same rules apply at all cell locations) According to Christopher Langton, CA's are good examples of the kind of computational paradigm sought after by Artificial Life: bottom up, parallel, local-determination of behavior. (p.13) Christopher Langton has tried to parametricize the space of transition rules -- to correlate them to different kinds of dynamic behaviour by the CA.
The main applications of CA's are in computer graphics (image cleanup), simulation of biological systems (artificial life), simulation of physical phenomena (heat-flow, turbulence) and the design of massively parallel computers.
A more "real life" version, studied by Thomas Schelling and described by John Casti in Complexification, described racial"tipping" of neighborhoods based on local preferences for racially similar neighbors.