cellular automaton
A -dimensional cellular automaton is a triple where:
-
1.
is a nonempty set, called alphabet or set of states.
-
2.
is a finite, nonempty subset of , called neighborhood
index.
-
3.
is the local function.
The local function of the cellular automaton
induces, by synchronous application at all points,
a global function
on -dimensional configurations :
(1) |
Observe that the global function is continuous in the product topology.
Cellular automata are a Turing-complete model of computation.
In fact, given a Turing machine,
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 analysis.
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 dimension.
As an example,
reversibility of the global function
is decidable in dimension but not in dimension (or higher).
The definition above can be generalized to the case
of a generic group acting by translations
on the space of configurations.
If
(2) |
then the local function
( being a finite nonempty subset of )
induces
via the relation
(3) |
Observe that is a left action, while is a right action. It is of course possible to only use left action by defining as instead: since this is just a reparametrization of the family , 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) |