We should start the study of self-organization and complex behavior with the thought that "Complexity exists,
in some murky sense, in the eye of the beholder" [Horgan, page 106]. George Klir [1991], in line with Ashby
[1962] thinks of self-organizing systems as a case of goal-oriented systems "that are capable, with no explicit
outside help, of improving their performance while pursuing their goals" [Klir, 1991, page 165] and which
must be evaluated with some performance function. However, this goal (e.g. order, complex behavior) is
established in relation to some observer interested in a particular behavior. This is the reason why the study
of emergent, interesting, complex behavior is a tricky affair. We can all agree on the simple local rules causing
the emergent global behavior, but the latter is a more subjective affair since it is not explicitly programmed or
described in physical terms. It is instead an observed behavior, relevant for some observer with some goal like
understanding life or building some sort of computational engine [see Forrest, 1991]. Kauffman[1993] calls
for a new statistical mechanics to understand the behavior of self-organizing computational structures, in other
words, new higher-level parameters (with physical analogues such as temperature) must be developed to
understand self-organizing, emergent, behavior regarding some observer's interest.
"Complexologists often employ 'interesting' as a synonym for 'complex'. But what government agency would
supply funds for research on a 'unified theory of interesting things'?" [Horgan, 1995, page 106]
What is usually referred to as self-organizing behavior is the spontaneous formation of well organized
structures, patterns, or behaviors, from random initial conditions. The systems used to study this behavior are
referred to as dynamical systems: state-determined systems. They possess a large number of elements or
variables, and thus very large state spaces. However, when started with some initial conditions they tend to
converge to small areas of this space (attractor basins) which can be interpreted as a form of self-organization.
The existence of attractors is identified with the dissipation of some form of energy (friction), therefore, like
living systems, dissipative structures can only be maintained by a constant flux of energy through them, and
are therefore not in equilibrium. These attractors may be chaotic in which case the emergent behavior becomes
too disorganized to grasp (disorganized complexity), though still self-organizing since chaotic attractors tend
to be restricted to small volumes of their state-space (e.g. chaotic in a small subset of dimensions of the stat-space). The behavior of interest is often found in the transition between order and chaos -- edge of chaos--
and classified as a kind of organized complexity [Weaver, 1948]. Another parallel to living systems here is that
such dynamical structures are not devised to exhibit this behavior, they develop spontaneously from random
initial conditions (note: not from special initial conditions). This behavior -- many parts working together to
achieve a higher order -- is also known as synergetics [Haken, 1977].
Since such formal dynamical systems are usually used to model real dynamical systems such as chemical networks of reactions, non-equilibrium thermodynamic behavior [Nicolis and Prigogine, 1977], or even mineral osmotic growths [Leduc, 1911; Zeleny, Klir, and Hufford, 1989], the conclusion is that in nature, there is a tendency for spontaneous self-organization which is therefore universal [Kauffman, 1993]. Further, only matter out of equilibrium (with dissipation) can achieve self-organization, which may be quite complex (strange attractors, etc.) [Prigogine, 1985]. This undeniable tendency for the spontaneous formation of complex physical patterns, is also frequently used to propose that life (an autonomous dissipative organization maintained through metabolism) is more general than usually accepted and that even mineral structures can be in this sense alive [Zeleny, Klir, and Hufford, 1989]. This process of self-organization is also often interpreted as the evolution of order from chaos. However, notice that this evolution is limited in its complexity level to the attractors dynamic systems converge to. A given dynamic system, unless its parameters are changed (structural perturbation), cannot escape its own attractor landscape and it is therefore constrained in its evolutionary potential. This limitation will become more apparent when we approach the problem of self-replication.
However, if the parameter space is divided by many bifurcations, the system becomes increasingly sensitive
to initial conditions and small parameter changes; in this sense its behavior becomes chaotic. It is usually
argued that the most useful behavior lies instead in between full order and chaos. Langton [1990, 1992] has
shown (for two-dimensional cellular automata) that it is in this range of behavior that dynamical systems can
carry the most complicated computations. Computation here is used an a loose sense, and means that
information exchange between elements of these systems is maximized in this range, or in other words, Langton
showed that the highest degrees of correlation between the states of his cellular automata occur at this stage.
The same idea has been proposed by others, including Prigogine who "speaking anthropomorphically [proposed
that], matter at equilibrium is 'blind,' it only 'sees' at very short distances, while matter out of equilibrium
develops a sensitivity to the outside world that is a sensitivity to distant events." [Prigogine, 1985, page 484].
Kauffman [1993, page 232] further hypothesizes that "living systems exist in the [ordered] regime near the
edge of chaos, and natural selection achieves and sustains such a poised state". This hypothesis is based on
Packard's [1988] work showing that when natural selection algorithms are applied to dynamic systems, with
the goal of achieving higher discriminative power, the parameters are changed generally to lead these systems
into this transitional area between order and chaos. This idea is very intuitive, since chaotic dynamical systems
are too sensitive to parameter changes (structural perturbation), that is, a single mutation leads the system into
another completely different behavior (sensitive to damage). By contrast, ordered systems are more resilient
to damage, and a small parameter change will usually result in a small behavior change which is ideal for
smooth adaptation (hill-climbing) in correlated fitness landscapes. However, even though very ordered systems
can adapt by accumulation of useful successful variations (because damage does not propagate widely), they
may not be able 'step out' of certain areas of their fitness landscapes. It is here that systems at the edge of
chaos enter the scene; they are not as sensitive to damage as chaotic systems, but still they are more sensitive
than fully ordered systems, and thus, some mutations will accumulate (by causing minor structural changes)
and some others will cause major changes in the dynamics allowing more distant searches in fitness spaces.
These characteristics of simultaneous mutation buffering (to small changes) and dramatic alteration of behavior
(in response to larger changes) is ideal for evolvability [Conrad, 1983, 1990].
Perhaps these concepts can be better grasped in the context of classifier networks. As stressed in the first
lecture, the ability to discriminate (categorize) relevant events in an environment is an important characteristic
of life. Dynamic systems such as boolean networks have the ability to discriminate inputs. Generally, the
attractors of their dynamics are used to represent events in their environments: depending on inputs, the network
will converge to different attractors. However, for any classification to have survival value, it must relate its
own constructed states (attractors) to relevant events in its environment, thus, similar events in the world should
correspond to the same attractor basin. Chaotic systems clearly do not have this property due to their sensitivity
to initial conditions. Ordered systems follow this basic heuristic. If on the edge of chaos, ordered systems may
in addition allow for higher information exchange and perhaps more 'clever' (evolvable) categorization mechanisms.
"Organisms and other entities which interact with their worlds are likely to couple to those worlds in such a way that smooth classification occurs, and the world is seen as relatively stable. Then the 'knower' should not be chaotic, nor should its classification, the 'known', be. It is a reasonable guess that both the knowing system and the known world are in the [ordered] regime, perhaps near the edge of chaos." [Kauffman, 1993, page 234]
Langton's definition of GTYPE and PTYPE is not so much a generalization of the genotype/phenotype
distinction in biology, as it is a framework to conceptualize emergent behavior in Artificial Life. It states the
requirement of a minimum of two levels of description for models of emergence. The first specifically describes
the level of the rules of dynamics (e.g. laws of physics or cellular automata rules). The second is the description
of whatever global behavior one decides to observe (e.g. self-organization, function, patterns, etc.). However,
this distinction fails to generalize the biological genotype/phenotype distinction, since the genotype does not
define the laws that allow the phenotype to self-organize (protein folding), those are simply the chemical laws
of the constituents of proteins (aminoacid chains). The genotype merely offers the initial conditions for such
a process of self-organization, in this sense it can be seen more as data than as a program for a phenotype
[Atlan and Koppel, 1990]. This problem can be easily recognized when we realize that the biological genotype,
depending on the level of description chosen, can be seen both as a GTYPE and as a PTYPE. The GTYPE of
the genotype being the chemical rules of interaction between the components of nucleic acids, and the PTYPE
being its self-organization into DNA strands and its subsequent utilization as a genetic information carrier.
Likewise, the biological phenotype may also be granted a GTYPE and PTYPE description. The former being
the rules of interaction of protein constituents, and the latter being the functions associated with the specific
phenotype (e.g. catalytic behavior).
Historical papers and books in self-organization include: Farley and Clark [1954], Yovits and Cameron [1960], von Foerster and Zopf [1962], Yovits, Jacobi, and Goldstein [1962], Ashby [1962], Nicolis and Prigogine [1977], and more recently Kauffman [1993].
Further Readings and References:
Ashby, W.R. [1960], Design for a Brain. Wiley.
Ashby, W.R. [1962]."Principles of the self-organizing system." In: Principles of Self-Organization. H. von Foerster and G.W. Zopf (Eds.). Pergamon Press. Reprinted in Klir [1991 pp. 521-536.
Atlan, H. And M. Koppel [1990]. "The cellular computer DNA: program or data". In: Bulletin of Mathematical Biology, Vol. 52, No. 3, pp.335-348.
Conrad. M. [1983], Adpatability. Plenum Press.
Conrad, M. [1990], "The geometry of evolutions". In BioSystems Vol. 24, pp. 61-81.
Farley, B.G. and W.A. Clark [1954], "Simulations of self-organizing systems by digital computer. IRE Transactions, IT-Vol 4 No. 3, pp 76-84.
Forrest, S. (Ed.) [1990]. Emergent Computation. MIT Press/ North-Holland. Special Issue of Physica D. Vol. 42.
Haken, H. [1977], Synergetics. Springer-Verlag.
Horgan J. [1995], Scientific American, June 1995 issue, "From Complexity to Perplexity"
Kauffman, Stuart A. [1993]. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press.
Klir, George J. [1991]. Facets of Systems Science. Plenum Press.
Langton, C. [1989], "Artificial Life" In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 1-47.
Langton, C. [1990]. "Computation at the edge of chaos: phase transitions and emergent computation". In Forrest [1990] pp12-37.
Langton, C. [1992], "Life at the edge of chaos". In Artificial Life II. C. Langton (Ed.) Pp 41-91. Addison-Wesley
Leduc, S. [1911], The Mechanisms of Life. Rebman.
Nicolis, G. and I. Prigogine [1977]. Self-Organization in Nonequilibrium Systems: From Dissipative Structures to Order through Fluctuations. Wiley-Interscience.
Packard, N. [1988] "Adaptation toward the edge of chaos". In. Complexity in Biologic Modelling. S. Kelso and M. Shlesinger.
Prigogine, I. [1985]. "New Perspectives on Complexity". In the Sciences and Praxis of Complexity. The United Nations University pp.107-118. Reprinted in Klir [1991] pp.484-492
von Foerster, H. and G.W. Zopf (Eds.) [1962], Principles of Self-Organization. Pergamon Press.
Weaver,W. [1948], "Science and Complexity", In American Scientist, Vol. 36. Reprinted in Klir [1991] pp. 449-456.
Yovits, M.C. and S. Cameron (Eds.) [1960], Self-Organizing Systems. Pergamon Press.
Yovits, M.C., G.T. Jacobi, and G.D. Goldstein (Eds.) [1962], Self-Organizing Systems _ 1962. Spartan Books.
Zeleny, M., G. Klir, and K. Hufford [1989], "Precipitation Membranes, Osmotic Growths and Sythetic Biology". In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 125-139.
For Next Lecture Read:
Chapter II of Emmeche's [1991], The Garden in the Machine: The Emerging Science of Artificial Life. Princeton University Press.
So far, we have seen two different types of computational systems said to be self-organizing in this sense: the
discrete logistic equation and Kauffman's NK-Boolean nets. We have seen that the former observes several
ranges of ordered behavior according to its parameter a. For a 3, the system will converge to a single point
steady state (independently of its initial value). For 3 a 4 the system enters a series of bifurcations, meaning
that it starts converging to a two-state limit cycle which progressively doubles the number of states in its cycle
as a increases. Close to a = 4, the cycles become chaotic. That is, in the chaotic range, the slightest change in
the initial value, will lead to a completely different trajectory (though similarly chaotic). The system goes from
being independent to strongly dependent of initial conditions, though, in each range, the attractor behavior of
the equation is the same for random initial conditions. Thus, we can see the logistic equation as self-organizing.
But there is another aspect of the logistic equation that should be understood. In all of its ranges of behavior,
from full order to full chaos, the system is (fairly) reversible. That is, I can always obtain a specific initial
condition which caused some behavior, by formally running the system backwards. This means the system is
deterministic in both temporal directions. Formally, this means the state transition function is invertible. (This
is actually only true, if we decide to work on the lower half of its state space, since the logistic equation is a
quadratic function, it has always two possible solutions for the previous value of the current state, these values
are symmetric about the middle point of its state space). Some, Howard Pattee for instance, resist calling this
kind of reversible systems self-organizing. They reason that if a system is self-organizing, when ran backwards
it should be self-disorganizing, that is, it should lead to random initial conditions, or to an incomplete
knowledge of possible initial states. Pattee reserves the term self-organization to those irreversible systems
whose behaviors must be evaluated statistically. The logistic map shows "hints" of this backwards self-disorganization, but we can still work out effectively its backwards trajectory to an initial condition by
restricting the quadratic solutions to half of its state space.
Random Boolean Networks are much more complicated than this. They are completely deterministic since a
certain state will always lead to the same next state (state-determinacy), however, we cannot usually know
exactly what the predecessor of a current state was. Systems like this are usually studied with statistical tools.
Even though the rules that dictate the next state of its components are simple and deterministic, the overall
behavior of the system is generally too complicated to predict and statistical analysis has to be performed. For
instance, Kauffman has shown that when K=2 (number of inputs to each node), his networks will have on
average SQRT(N) basins of attraction with a length of SQRT(N) states; if the output of one node is switched to the other
boolean value (perturbation), the trajectory returns to that cycle 85% of the time, while on the remaining 15%
of the time it will "jump" into a different basin of attraction.
Cellular automata (CA) fall into this same category of deterministic, irreversible, self-organization. We will
discuss Wolfram's four statistical classes reached by all one-dimensional CA from random initial conditions,
Langton's further refinement of these classes, and Conway's game of Life. Like the NK-networks, CA self-organize exclusively in accordance to their local rules. This is usually interpreted in boolean networks as the
simulation of some closed abstract dynamics (e.g. chemical reactions, genomic networks with epistasis, etc),
but in CA the local rules are often viewed as the simulation of some artificial physics in an artificial topological
space, while the patterns of cellular activation (state cycles) are seen as emergent phenomena. In particular,
when coherent patterns are observed which behave like life in some way (motion, self-reproduction, etc), it is
often argued that it represents the emergence of artificial life from artificial matter. The simple local rules stand
for an artificial physics with micro-causality (a cell's state is solely dependent on its spatial neighbors and on
their previous value), and the emergent patterns for artificial life. One obvious problem with this interpretation
is that in the real world the local rules leading to some physical causality generate all that we see around us,
living and non-living. In the CA world, arguments are often made for the emergence of artificial life, but not
for an explicit criteria to distinguish artificial life from artificial non-life also generated by the artificial physics.
CA further observe the three ranges of behavior exhibited by boolean networks: ordered, chaotic, and intermediate. We will discuss Langton's results indicating that CA will perform computations more effectively in the edge of chaos, which is based on the definition of his parameter. Later on, once evolutionary algorithms are introduced, the evolution of CA rules for the solution of non-trivial tasks is discussed.
Further Readings and References:
Forrest, S. (Ed.) [1990]. Emergent Computation. MIT Press/ North-Holland. Special Issue of Physica D. Vol. 42.
Kauffman, Stuart A. [1993]. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press.
Langton, C. [1990]. "Computation at the edge of chaos: phase transitions and emergent computation". In Forrest [1990] pp12-37.
Packard, N. [1988]. "Adaptation to the edge of chaos". In Complexity in Biological Modeling, S.Kelso and M. Shlesinger (eds.).
Rucker R. And J. Walker [1989]. CA Lab: Rudy Rucker's Cellular Automata Laboratory. Autodesk, 1989 (book and software)
Sigmund, K. [1993], Games of Life: Explorations in Ecology, Evolution, and Behavior. Oxford University Press
Toffoli T. and N. Margolus [1987]. Cellular Automata Machines. MIT Press
Wolfram, S. (Ed.) [1986], Theory and Applications of Cellular Automata, World Scientific Press.
For Next Lecture Read:
Chapter III of Emmeche's [1991], The Garden in the Machine: The Emerging Science of Artificial Life. Princeton University Press.