Biomedical Engineering Reference
In-Depth Information
automaton
—and so the whole board is called a
cellular automaton
, or CA. To
run it, you color the cells in your favorite pattern, start the clock, and stand back.
Let us follow this concrete picture with one more technical and abstract.
The cells do not have to be colored, of course; all that's important is that each
cell is in one of a finite number of states at any given time. By custom they're
written as the integers, starting from 0, but any "finite alphabet" will do. Usually
the number of states is small, under ten, but in principle any finite number is
allowed. What counts as the "nearby cells," the
neighborhood
, varies from
automaton to automaton; sometimes just the four cells on the principal direc-
tions, sometimes the corner cells, sometimes a block or diamond of larger size;
in principle any arbitrary shape. You do not need to stick to a chessboard; you
can use any regular pattern of cells that will fill the plane (or "tessellate" it; an
old name for cellular automata is
tessellation structures
). And you do not have
to stick to the plane; any number of dimensions is allowed. There are various
tricks for handling the edges of the space; the one which has "all the advantages
of theft over honest toil" is to assume an infinite board.
Cellular Automata as Parallel Computers
. CA are synchronous massive-
ly parallel computers, with each cell being a finite state transducer, taking input
from its neighbors and making its own state available as output. From this per-
spective, the remarkable thing about CA is that they are computationally univer-
sal, able to calculate any (classically) computable function; one can use finite-
state machines, the least powerful kind of computer, to build devices equivalent
to Turing machines, the most powerful kind of computer. The computational
power of different physically motivated CA is an important topic in complex
systems (120,121), though it must be confessed that CA with very different
computational powers can have very similar behavior in most other respects.
Cellular Automata as Discrete Field Theories
. From the perspective
of physics, a CA is a "digitized" classical field theory, in which space, time,
and the field (state) are all discrete. Thus fluid mechanics, continuum mechan-
ics, and electromagnetism can all be simulated by CA
14
; typically, however,
the physical relevance of a CA comes not from accurately simulating some
field theory at the microscopic level, but from the large-scale phenomena they
generate.
Take, for example, simulating fluid mechanics, where CA are also called
lattice gases
or
lattice fluids
. In the "HPP" (122) rule, a typical lattice gas with
a square grid, there are four species of "fluid particle," which travel along the
four principal directions. If two cells moving in opposite directions try to occupy
the same location at the same time, they collide, and move off at right angles to
their original axis Figure 4). Each cell thus contains only an integer number of
particles, and only a discrete number of values of momentum are possible. If
one takes averages over reasonably large regions, however, then density and
