Cellular automaton

From Esolang
Jump to: navigation, search

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

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

External resources