As a first example, consider various idealizations of the system
discussed above consisting of a ball rolling with friction on a
landscape, now assumed one dimensional. In the approximation of a
point ball, this is equivalent to a particle moving with damping in
a one-dimensional potential. But the basins of attraction depend
substantially on thee exact dynamics assumed. In the case of very
large friction, the particle satisfies a differential equation in
which velocity is proportional to force, and force is given by the
gradient of the potential. In a more realistic model, with finite
friction and the inertia of the ball included, the system becomes
similiar to a Roulette wheel. And in this case it is known that
the outcome is a sensitive function of the precise initial conditions.
As a consequence, the basins of attraction corresponding for example
to different holes around the wheel must have a complicated,
interdigitated, form (cf. [5]).
Complicated basin boundaries can also be obtained with simpler
equations of motion. As one example, one can take time to be
discrete, and assume that the potential has the form of a polynomial,
so that the differential equation is approximated by an iterated
polynomial mapping. The sequence of positions found from this
mapping may overshoot the minimum, and for some values of parameters
may in fact never converge to it. The region of initial conditions
which evolves to a particular attractor may therefore be complicated.
In the case of the complex iterated mapping z->z^2+c, the boundary
of the basin of attraction (say for the attractor z=\infty) is a
Julia set, and has a very complicated fractal form (e.g. [6]).
The essentials of the problem of finding basins of attraction already
arise in the problem of determining what set of inputs to a function of
discrete variables yields a particular output. This problem is known in
general to be computationally very difficult. In fact, the satisfiability
problem of determining which if any assignments of truth values to n
variables in a Boolean expression make the whole expression true is
NP-complete, and can presumably be solved in general essentially only
by explicitly testing all 2^n possible assignments (e.g. [7]). For some
functions with a simple, perhaps algebraic, structure an efficient
inversion procedure to find appropriate inputs may exist. But in general
no simple mathematical formula can describe the pattern of inputs:
they will simply seem random (cf. [8]).
Many realistic examples of this problem are found in cellular automata.
Cellular automata consist of a lattice of sites with discrete values
updated in discrete steps according to a fixed local rule. The image
processing operation mentioned above can be considered a single step
in the evolution of a simple two-dimensional cellular automaton (cf.
[9]). Other cellular automata show much more complicated behaviour,
and it seems in fact that with appropriate rules they capture the
essential features of many complex systems in nature (e.g. [1]). The
basic problems of complexity engineering thus presumably already
arise in cellular automata.
Most cellular automata are dissipative, or irreversible so that after
many steps, they evolve to attractors which contain only a subset
of their states. In some cellular automata (usually identified with
the classes 1 and 2), these attractors are fixed points (or limit
cycles), and small changes in initial conditions are usually dampened
out [10]. Other cellular automata (classes 3 and 4), however, never
settle down to a fixed state with time, but instead continue to show
complicated, chaotic, behaviour. Such cellular automata are unstable,
so that most initial perturbations grow with time to affect the detailed
configurations of an ever-increasing number of sites. The statistical
properties of the behaviour produced are nevertheless robust, and are
unaffected by such perturbations.
It can be shown that the set of fixed points of a one-dimensional
cellular automaton consists simply of all those configurations in
which particular blocks of site values do no appear [11]. This set
forms a (finite complement) regular language, and can be represented
by the set of possible paths through a certain labeled directed
graph [11]. Even when they are not fixed points, the set of all states
that can occur after say t time steps in the evolution of a
one-dimensional cellular automaton in fact also forms a regular
language (though not necessarily a finite complement one). In addition,
the basin of attraction, or in general the set of all states which
evolve after t steps to a given one, can be represented as a regular
language. For class 1 and 2 cellular automata, the siz of the minimal
graph for this language stays bounded, or at most increases like a
polynomial with t. For class 3 and 4 cellular automata, however, the
the size of the graph often increases apparently exponentially with
t, so that it becomes increasingly difficult to describe the basin
of attraction. The general problem of determining which states evolve
to a particular one after t steps is in fact a generalization of the
satisfiability problem for logical functions mentioned above, and is
thus NP complete. The basin of attraction in the worst case can thus
presumably be found only by explicit testing of essentially all O(2^t)
possible initial configurations (cf. [12]). Its form will again often
be so complicated as to seem random. For two-dimensional cellular
automata, it is already an NP-complete problem just to find fixed
points (say to determine which n x n blocks of sites with specified
boundaries are invariant under the cellular automaton rule) [13].
It is typical of complex systems that to reproduce their behaviour
requires extensive computation. This is a consequence of the fact that the
evolution of the systems themselves typically corresponds to a
sophisticated computation. In fact, the evolution of many complex systems
is probably computationally irreducible: it can be found essentally only
by direct simulation, and cannot be predicted by any short-cut procedure
[12, 14]. Such computational irreducibility is a necessary consequence of
the efficient use of computational resources in a system. Any
computational reducibility is a sign of inefficiency, since it implies
that some other system can determine the outcome more efficiently.
Many systems in nature may well be computationally irreducible, so that no
general predictions can be made about their behaviour. But if a system is
to be used in engineering, it must be possible to determine in advance at
least some aspects of its behaviour. Conventional engineering requires
detailed specifications of the precise behaviour of each component in a
system. To make use of complex systems in engineering, one must relax this
constraint, and instead require only some general or approximate
specification of overall behaviour.
One goal is to design systems which have particular attractors. For the
example of an inertialess ball rolling with friction on a landscape, this
is quite straightforward (cf. [15]). In one dimension, the height of the
landscape at position x could be given by the polynomial \Pi_i(x-x_i)^2,
where the x_i are the desired minima, or, attractors. The polynomial is
explicitly constructed to yield certain attractors in the dynamics.
However, it implies a particular structure for the basins of attraction.
If the attractors are close to equally spaced, or are sufficiently far
apart, then the boundaries of the basins of attraction for successive
attractors will be roughly half way between them. Notice, however, that as
the parameters of the landscape polynomial are changed, the structure of
the attractors and basins of attraction obtained can change
discontinuously, as described by catastrophe theory.
For a more complex system, such as a cellular automaton, it is more
difficult to obtain a particular set of attractors. One approach is to
construct cellular automaton rules which leave particular sequences
invariant [16]. If these sequences are say of length L, and are
arbitrarily chosen, then it may be necessary to use a cellular automaton
rule which involves a neighbourhood of up to L-1 sites. The necessary rule
is straightforward to construct, but takes up to 2^{L-1} bits to specify.
Many kinds of complex systems can be considered as bases for engineering.
Conventional engineering suggests some principles to follow. The most
important is the principle of modularity. The components of a system
should be arranged in some form of hierarchy. Components higher on the
hierarchy should provide overall control for sets of components lower on
the hierarchy, which can be treated as single units or modules. This
principle is crucial for software engineering, where the modules are
typically subroutines. It is also manifest in biology in the existance of
organs and definite body parts, apparently mirrored by subroutine-like
constructs in the genetic code [ check out Kauffman's "The Origins of
Order", Chapter 14 (Morphology, Maps and the Spatial Ordering of
Integrated Tissues) for more info on morphogenetic gadgetry -- 'gene ]
An important aspect of modularity is the abstraction it makes possible.
Once the construction of a particular module has been completed, the
module can be treated as a single object, and only its overall behaviour
need be considered, wherever the module appears. Modularity thus divides
the problem of constructing or analysing a system into many levels,
potentially making each level manageable.
Modularity is used in essentially all of the systems to be discussed
below. In most cases, there are just two levels: controlling (master) and
controlled (slave) components. The components on these two levels usually
change on different time scales. The controlling components change at most
slowly, and are often fixed once a system say with a particular sets of
attractors has been obtained. The controlled components change rapidly,
processing input data according to dynamical rules determined by the
controlling components. Such separation of time scales is common in many
natural and artificial systems. In biology, for example, phenotypes of
organisms grow by fast process, but are determined by genotypes which seem
to change only slowly with time. In software engineering, computer memory
is divided into a part for "programs", which ar supposed to remain fixed
or change only slowly, and another part for intermediate data, which
changes rapidly.
[ to be continued... 'gene ]