cellular automaton

A d-dimensional cellular automaton is a triple 𝒜=Q,𝒩,f where:

  1. 1.

    Q is a nonempty set, called alphabet or set of states.

  2. 2.

    𝒩={ν1,,ν|𝒩|} is a finite, nonempty subset of d, called neighborhoodMathworldPlanetmathPlanetmath index.

  3. 3.

    f:Q𝒩Q is the local function.

The local function of the cellular automaton 𝒜 induces, by synchronous application at all points, a global function F𝒜 on d-dimensional configurationsMathworldPlanetmathPlanetmath c:dQ:

F𝒜(c)(z)=f(c(z+ν1),,c(z+ν|𝒩|))=f(c|z+𝒩). (1)

Observe that the global function is continuousMathworldPlanetmathPlanetmath in the product topology.

Cellular automata are a Turing-complete model of computation. In fact, given a Turing machineMathworldPlanetmath, it is straightforward to construct a cellular automaton that emulates it in real time. On the other hand, given a one-dimensional cellular automaton, there exists a Turing machine that emulates it in linear time with respect to the size of the input.

Cellular automata make good tools for qualitative analysisMathworldPlanetmath. In fact, given the description of a cellular automaton, it is straightforward to write a computer program that implements its features. Also, several phenomena in different fields of sciences — from physics to biology to sociology — can be described in terms of finite-range interactions between discrete agents.

On the other hand, retrieving the properties of the global dynamics from the local description is usually a very difficult task, and may depend on the dimensionMathworldPlanetmath. As an example, reversibility of the global function is decidable in dimension 1 but not in dimension 2 (or higher).

The definition above can be generalized to the case of a genericPlanetmathPlanetmathPlanetmath group G acting by translations on the space QG of configurations. If

Lg(x)=gxxG, (2)

then the local function f:Q𝒩Q (𝒩 being a finite nonempty subset of G) induces F𝒜:QGQG via the relationMathworldPlanetmath

F𝒜(c)(g)=f((cLg)|𝒩)=f(c|g𝒩)c:GQ. (3)

Observe that L={Lg}gG is a left action, while (c,g)cLg is a right action. It is of course possible to only use left action by defining F𝒜(c)(g) as f((cLg-1)|𝒩) instead: since this is just a reparametrization of the family L, the bulk of the theory does not change.

More to come …

Title cellular automaton
Canonical name CellularAutomaton
Date of creation 2013-03-22 19:21:58
Last modified on 2013-03-22 19:21:58
Owner Ziosilvio (18733)
Last modified by Ziosilvio (18733)
Numerical id 5
Author Ziosilvio (18733)
Entry type Definition
Classification msc 37B15
Classification msc 68Q80
Defines neighborhood (cellular automaton)
Defines neighborhood index (cellular automaton)
Defines local function (cellular automaton)
Defines global function (cellular automaton)