Biomedical Engineering Reference
In-Depth Information
completely different symbolic dynamics (113-115). How then might we choose
a
good
partition?
Nonlinear dynamics provides an answer, at least for deterministic systems,
in the idea of a
generating partition
(10,116). Suppose we have a continuous
state
x
and a deterministic map on the state
F
, as in §3.1. Under a partitioning G,
each point
x
in the state space will generate an infinite sequence of symbols,
'(
x
), as follows: G(
x
), G(
F
(
x
)), G(
F
2
(
x
)), .... The partition G is generating if each
point
x
corresponds to a
unique
symbol sequence, i.e., if ' is invertible. Thus,
no information is lost in going from the continuous state to the discrete symbol
sequence.
13
While one must know the continuous map
F
to determine exact gen-
erating partitions, there are reasonable algorithms for approximating them from
data, particularly in combination with embedding methods (75,117,118). When
the underlying dynamics are stochastic, however, the situation is much more
complicated (119).
4.
CELLULAR AUTOMATA
Cellular automata
are one of the more popular and distinctive classes of
models of complex systems. Originally introduced by von Neumann as a way of
studying the possibility of mechanical self-reproduction, they have established
niches for themselves in foundational questions relating physics to computation
in statistical mechanics, fluid dynamics, and pattern formation. Within that last,
perhaps the most relevant to the present purpose, they have been extensively and
successfully applied to physical and chemical pattern formation, and, somewhat
more speculatively, to biological development and to ecological dynamics. In-
teresting attempts to apply them to questions like the development of cities and
regional economies lie outside the scope of this chapter.
4.1. A Basic Explanation of CA
Take a board, and divide it up into squares, like a chess- or checkerboard.
These are the cells. Each cell has one of a finite number of distinct colors—red
and black, say, or (to be patriotic) red, white, and blue. (We do not allow con-
tinuous shading, and every cell has just one color.) Now we come to the
"automaton" part. Sitting somewhere to one side of the board is a clock, and
every time the clock ticks the colors of the cells change. Each cell looks at the
colors of the nearby cells, and its own color, and then applies a definite rule, the
transition rule
, specified in advance, to decide its color in the next clock-tick;
and all the cells change at the same time. (The rule can say "stay the same.")
Each cell is a sort of very stupid computer—in the jargon, a
finite-state
