CELLULAR AUTOMATA & SELF-REPRODUCTION
Celluar Automata were invented by the mathematician Stanislaw
Ulam and were used by J. von Neumann, followed by A.W. Burks and
E.F. Codd, to solve problem of the
non-trivial self-reproduction
in a logical system. They are of interest to physicists as
a models of simple local physics, to biologists as settings
for models in theoretical biology, and to computer scientists
as a setting for massive parallel processing in future
computers and for other applications.
Definition of Cellular Automata
On a regular lattice (repeated structure of points have
the same kind of neighborhood) one puts a finite-state
machine at each point. The input to the machine is
the states of all machines in its neighborhood.
The behaviour is to change its state based
in a determined way, as a function of the states of
its neighbors and its own state. The states of all
machines in the lattice are updated synchronously
(simultaneously).
Example: John Conway's LIFE
For this cellular automaton, one takes a neighborhood consisting
of the nearest 8 cells to a cell on a two-dimensional grid of
cells. The transition function for the local automaton is as
follows:
- There are two states: alive , not alive
- If 2 or 3 neighbors of a cell are alive and
its is currently alive, its next state is alive
- If 3 neighbors of a cell are alive and
its currently not alive, its next state is alive
- Otherwise the next state is not alive.
With these simple rules on an infinite 2D grid, it is
possible to construct a machine capable of universal
computation, that is, of emulating the computing power
of any Turing machine or existing digital computer.
Before biologists determined the nature of inheritence via DNA
encoding of protein synthesis (and more), John von Neumann showed how
automata can be constructed that can self-reproduce using
the the notion of a universal constructor and cellular automata.
The mechanism he used distinguished data as having two aspects:
- material that can be copied, and
- material that can be used as instructions.
This insight is perhaps due originally to mathematical logician K. Gödel.
The von Neumann self-reproducing automata is actually
a ``universal constructor'' that constructs ``any machine'' in
its 29-state cellular space. In particular, it is capable of
Turing universal computation. It solves the self-reproduction problem
by reading a tape containing instructions on how to build a copy
of itself, provides the copy with a copy of its own input tape, and then
presses the ON button starting the copy in operation.
In the 1980s, C. Langton and then J. Byl
showed that in fact much smaller automata
can in fact self-reproduce.
We shall study new implementations and applications of self-reproducing systems.
Although these cellular automata self-reproduce in a non-trivial manner
using the two-fold nature of data, the generated copies
are exactly the same as the parent, the growth is like that of a
crystal rather than of biological life
involving
heredity, variability
and differing fitness, which are necessary
for real
evolution by
means of natural selection.
Copyright (c) by C. Nehaniv, University of Aizu, 1995-96
e-mail: nehaniv@u-aizu.ac.jp