Cellular automaton

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.

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.

Relation to esoteric programming

Any cellular automaton can be considered a programming language, at least in the general sense that we use for esoteric programming languages, and most constructions described as cellular automata are esoteric as well. This makes Von Neumann's 29-state cellular automaton and Game of Life among the earliest perhistoric esoteric programming languages.

Of the esoteric programming languages invented by the esoteric language community, few seem to be strictly defined as cellular automaton (possibly because CA's are well-studied and thus less interesting than more exotic models such as bully automata.) There are, however, a few:

• RedGreen
• Braktif
• Circute
• LLLL
• Black

ALPACA is not a cellular automaton, but it produces implementations of cellular automata as its output.

History

Von Neumann's 29-state cellular automaton is generally credited as the first deliberate cellular automata. The concept of a cellular automaton is so broad though that there are probably earlier examples of mathematical concepts that can be considered a cellular automata if you squint hard enough. Game of Life, the most famous cellular automaton, was first published by John Horton Conway in 1970, and there has been active research done about it ever since.

See also

• Particle automaton
• Bully automaton
• Category:Cellular automata
• User_talk:ColorfulGalaxy's CA discoveries, the official place for discussion about CA on this wiki, although it sounds weird

External resources

• Nyles Heise's WireWorld Pages (from the Wayback Machine; retrieved on 13 March 2008)