Contents /
Previous /
Next
Cellular Automata (CA)
Cellular automata are arrays of elements, or cells, all behaving
identically, depending on the element's state. At regular, discrete
intervals (iterations), the state of all elements is updated,
depending on the current state of the element itself and that of its
neighbors, according to a set of transition rules.
A (discrte time and space)
cellular automaton is defined by the following parameters:
- A number of dimensions
- A set of states (two in the case of Life below)
- A neighborhood,
which specifies which neighbors will have
an effect on an element's next state
(Life uses a neighborhood of 9)
- A collection of transition rules,
used to compute an element's
next state depending on the neighborhood. The rules can be expressed
either as an algorithm (as for Life above) or exhaustively as a lookup
table.
In the
latter case, the total number of rules necessarily to exhaustively
define a cellular automaton is SN,
where S is the number of states and N the neighborhood (thus, to
completely define Life, a lookup table of 29=512 rules would be required). In practice, the
number of required rules can, in many cases, be considerably
reduced.
CA Example : "Life"
A popular, well studied, cellular automata is is "Life".Life is a
uniform two-dimensional cellular automaton where each element can be
in one of only two states (aliveordead). The next state
of an element depends on its current state and that of its eight
closest neighbors (to the north, south, east, west, northeast,
southeast, southwest, and northwest), and is calculated from a set of
simple rules:
- if fewer than two elements in the neighborhood are alive,
the next state is dead (death by starvation);
- if more than three elements in the neighborhood are alive,
the next state is dead (death by overcrowding);
- if exactly three elements in the neighborhood are alive, then
the next state is alive (birth);
- otherwise (i.e., if exactly two of the elements in the neighborhood
are alive) the next state is equal to the current state (survival).
This very simple automaton
leads either to an empty space or to a
collection of small, isolated cyclic patterns. One of the best-known
of these patterns is the glider,
a small structure capable of
moving diagonally across the space.
Von Neumann's Self-Replicating Machines
Von Neumann, confronted with the lack of reliability of computing
systems, turned
to nature to find inspiration in the design of fault-tolerant
computing machines. Natural systems are among the most reliable
complex systems known to man, and their reliability is a consequence
not of any particular robustness of the individual cells (or
organisms), but rather of their extreme redundancy. The basic natural
mechanism which provides such reliability is
self-reproduction, both at the cellular level (where the
survival of a single organism is concerned) and at the organism level
(where the survival of the species is concerned).
Thus von Neumann, drawing inspiration from natural systems, attempted
to develop an approach to the realization of self-replicating
computing machines (which he called artificialautomata, as
opposed to naturalautomata, that is, biological organisms). In
order to achieve his goal, he imagined a series of five distinct
models for self-reproduction,
p. 91-99]: the kinematic model, the cellular model, the
excitation-threshold-fatigue
model, the continuous model, and the probabilistic model.
-
The kinematic model
involves structural elements
such as sensors, muscle-like components, joining and cutting tools,
along with logic (switch) and memory elements.
- The cellular model, based on the use of cellular automata was
the closest to an actual realization. Even if it was never completed,
it was further refined by von Neumann's successors and was the basis
for further research on self-replication.
-
The excitation-threshold-fatigue model was based on the
a neuron-like element.
-
For the continuous model, von Neumann planned to use differential
equations to describe the process of self-reproduction.
- The probabilistic model is
a kind of automaton where the transitions
between states were probabilistic rather than deterministic. Such an
approach would allow the introduction of mechanisms such as mutation
and thus of the phenomenon of evolution in artificial automata.
Von Neumann's Cellular Model
In von Neumann's work, self-reproduction is always presented as a
special case of universal construction, that is, the capability
of building any machine given its description, based on three separate
components:
- A memory tape, containing the description of the machine to
be built, in the form of a uni-dimensional string of elements.
- The constructor itself, a very complex machine capable of
reading the memory tape and interpreting its contents.
- A constructing arm, directed by the constructor, used to build
the offspring (i.e., the machine described in the memory tape).
If we consider the universal constructor from a biological viewpoint,
we can associate the memory tape with the genome, and thus the entire
constructor with a single cell (which would imply a parallel between
the automaton's elements and molecules).
Orignial Sources and Links:
Intro, Game of Life, von Neumann, Langton
CA
CA examples
Von Neumann CA
Some very colorful examples for CAs