Cellular automaton
- This page is about the general concept of cellular automaton. For a list of automata studied on-wiki, see Category:Cellular automata.
A cellular automaton (CA) is an automaton which consists, essentially, of a tiling of interdependent finite-state automata (FSAs) on a discrete topology - most often an infinite grid, but other structures, such as hex-nets, are certainly possible.
The individual FSAs, called cells, are interdependent in the sense that the next state of each relies not only on its current state, but also the state of a set of other cells called its neighbours. These neighbours can be found in a consistent set of locations relative to the cell, called its neighbourhood.
The tiling is generally considered homogenous (i.e. all FSAs are identical) and unbounded (i.e. extending without limit in all directions,) although these requirements are not hard and fast.
All cells in the tiling advance synchronously during an atomic time period called a tick. The state of all the cells at some given time is called the configuration of the CA at that point.
Any cellular automaton can be considered as a Zero Instruction Set Computer (ZISC) machine. In this sense, cellular automata are esoteric programming languages.
Cellular automata of note
The most famous CA is undoubtedly John Conway's Game of Life, also known as just Life. Another CA of considerable popularity is WireWorld. Both of these CAs use an unbounded, two-dimensional grid as their underlying topology.
Computational class
Cellular automata are of varying computational classes; some are Turing-complete, while others are not. Both Life and WireWorld have been shown to be so. The original proof of Life's Turing-completeness was done by Conway; a particularly readable and conscientious (but occasionally sketchy) proof using a "digital circuit" model is found in The Game of Life: Universality Revisited (Durand and Róka, 1999).
There are two major points which make a reduction to a CA from a Turing machine (or similar system) troublesome, as discussed in that paper:
- Background pattern: while programs, by assumed equivalence with algorithms, are generally considered finite, CA configurations have the same extent as their underlying topology, and as such, may well be infinite. In this case, the initial configuration is considered to be surrounded by a background pattern. Although "empty space" is perhaps the most intuitive background pattern, there is nothing that puts it in a privileged position; any quiescent (or possibly periodic) configuration should be equally valid.
- Halting configuration: CAs never come to a halt, as such - the closest thing is a quiescent configuration. It may be inconvenient for a system to come to such a configuration. In this case, a halting configuration may be defined, such that when some part of the CA assumes this configuration, it is considered to have halted.
History
Cellular automata were studied by wikipedia:Stanislav Ulam and wikipedia:John von Neumann in the 1940s in the context of physics. In a series of papers starting with their 1969 PhD dissertation, wikipedia:Alvy Ray Smith formalized the concept of cellular automaton and established basic results for working with them. Early examples of cellular automata in computer science include Von Neumann's 29-state cellular automaton and Conway's Game of Life.
Examples
Related
ALPACA is not a cellular automaton, but it produces implementations of cellular automata as its output.
See also
External resources
- Nyles Heise's WireWorld Pages (from the Wayback Machine; retrieved on 13 March 2008)