Any change in the structure or function of an entity (say, a
biological organism) that allows it to survive and reproduce more effectively in its
environment.
Algorithmic Complexity
A measure of the complexity of a problem. Typically defined as the
size of the smallest program that computes the given problem or that generates a complete
description of it.
Animats
Artificial animals consisting of both software and hardware.
Typically designed to be able to adapt to their environment over time.
Artificial Life
This is not a concept that is yet ready to be rigorously defined. The
most concise, but still far from rigorous definition, is simply: life as synthesized by
man rather than by nature. One of the basic tenets of this still-infant field is the
belief that life is not unique to its biological (and, as yet, only known) form, but is a
more general property of the organization of matter. Artificial life explores life as it
could be as opposed to life as we know it to be.
Attractor
Dissipative dynamical systems are
characterized by the presence of some sort of internal "friction" that tends to
contract phase-space volume elements. Contraction in phase space
allows such systems to approach a subset of the phase-space called an attractor as the
elapsed time grows large. Attractors therefore describe the long-term behavior of a
dynamical system. Steady state (or equilibrium) behavior corresponds to fixed-point
attractors, in which all trajectories starting from the appropriate basin-of-attraction
eventually converge onto a single point. For linear dissipative dynamical systems, fixed
point attractors are the only possible type of attractor. Nonlinear systems, on the other
hand, harbor a much richer spectrum of attractor types. For example, in addition to
fixed-points, there may exist periodic attractors such as limit cycles. There is also an
intriguing class of chaotic attractors called strange attractors that have a complicated
geometric structure (see Chaos and Fractals).
Autonomous (or Adaptive-) Agent
An entity that, by sensing and acting upon its environment, tries to
fulfill a set of goals in a complex, dynamic environment. Properties: (1) it can sense the
environment through its sensors and act on the environment through its actuators; (2) it
has an internal information processing and decision making capability; (3) it can
anticipate future states and possibilities, based on internal models (which are often
incomplete and/or incorrect); (4) this anticipatory ability often significantly alters the
aggregate behavior of the system of which an agent is part. An agent's goals can take on
diverse forms: (i) desired local states;(ii) desired end goals;(iii) selective rewards to
be maximized; (iv) internal needs (or motivations) that need to be kept within desired
bounds. Since a major component of an agent's environment consists of other agents, agents
spend a great deal of their time adapting to the adaptation patterns of other agents.
Autoplectic Systems
Consider a dynamical system whose behavior appears random or chaotic.
There are two ways in which an apparent randomness can occur: (1) external noise, so that
if the evolution of the system is unstable, external perturbations amplify exponentially
with time -such systems are called homoplectic; (2) internal mechanisms, so that the
randomness is generated purely by the dynamics itself and does not depend on any external
sources or require that randomness be present in the initial conditions -such systems are
called autoplectic systems. An example of an autoplectic system is the one-dimensional,
two-state, two neighbor Cellular Automaton rule-30, starting from
a single non-zero site. The temporal sequence of binary values starting from that single
non-zero initial seed are completely random, despite the fact that the evolution is
strictly deterministic and the initial state is ordered.
Autopoiesis
Autopoiesis literally means "self-reproduction," and
expresses a fundamental complementarity between structure and function. More precisely,
the term refers to the dynamics of non-equilibrium structures; that is, organized states
(sometimes also called dissipative structures) that remain stable for long periods of time
despite matter and energy continually flowing through them. A vivid example of a
nonequilibrium structure is the Great Red Spot on Jupiter, which is essentially a gigantic
whirlpool of gases in Jupiter's upper atmosphere. This vortex has persisted for a much
longer time (on the order of centuries) than the average amount of time any one gas
molecule has spent within it.
Backpropagation Algorithm
The backpropagation algorithm is a learning rule for multi-layered Neural Networks, credited to Rumelhart and McClelland. The algorithm
gives a prescription for adjusting the initially randomized set of synaptic weights
(existing between all pairs of neurons in each successive layer of the network) so as to
maximize the difference between the network's output of each input fact and the output
with which the given input is known (or desired) to be associated. The backpropagation
rule takes its name from the way in which the calculated error at the output layer is
propagated backwards from the output layer to the Nth hidden layer to the (N1)th hidden
layer, and so on. Because this learning process requires us to to "know" the
correct pairing of input-output facts beforehand, this type of weight adjustment is called
supervised learning.
Basin of Attraction
The basin of attraction is the ensemble of points P such that if the
trajectory starts from P it approaches the Attractor.
Bifurcation
The splitting into two modes of behavior of a system that previously
displayed only one mode. This splitting occurs as a control parameter is continuously
varied. In the Logistic Equation, for example, a period-doubling
bifurcation occurs whenever all the points of period-2n cycle simultaneously become
unstable and the system becomes attracted to a new period-2n+1 cycle.
Boolean Function
A function that maps an n-tuple of binary values -(x1, x2, ..., xn),
where xi = 0 or 1 for all i -to another binary value (either 0 or 1). There are clearly
2^(2n) possible Boolean functions that can defined for a given n-tuple.
Cantor Set
A simple example of a Fractal set of points
having noninteger Hausdorff Dimension. For example, the triadic
Cantor set is constructed as follows: take the unit interval (= [0,1]) and generate a new
set by deleting the open interval (1/2, 2/3); that is, by deleting the middle third.
Generate a new set by deleting the middle thirds (1/9, 2/9) and (7/9, 8/9) from the
previous set with the middle third removed. The Cantor set is essentially what remains of
the unit interval in the limit of generating successive "middle third" deleted
sets from the original set. It can be shown that the Fractal Dimension of this set is
approximately equal to 0.6309.
Catastrophe Theory
Catastrophe theory, introduced by Thom in the 1960s, is a
mathematical formalism for modeling nonlinear systems whose behavior is determined by the
actions of a small number of driving parameters. In particular, it applies to systems that
undergo either gradual or sudden changes in behavior due to gradually changing forces. It
has been applied to many problems in mathematics, physics and the social sciences. Thom
called the sudden changes that take place in a system "catastrophes" and
developed a theory as a method of analyzing and classifying these changes. Thom's theorem
asserts that the stationary state behavior of all systems that have up to four control
parameters (or input variables) and two behavior (or output) variables, and which also
have an associated potential function, can be described using one of seven elementary
catastrophes.
Cellular Automata
Cellular automata (CA) are a class of spatially and temporally
discrete, deterministic mathematical systems characterized by local interaction and an
inherently parallel form of evolution. First introduced by von Neumann in the early 1950s
to act as simple models of biological selfreproduction, CA are prototypical models for
complex systems and processes consisting of a large number of identical, simple, locally
interacting components. The study of these systems has generated great interest over the
years because of their ability to generate a rich spectrum of very complex patterns of
behavior out of sets of relatively simple underlying rules. Moreover, they appear to
capture many essential features of complex self-organizing cooperative
behavior observed in real systems. Although much of the theoretical work with CA has been
confined to mathematics and computer science, there have been numerous applications to
physics, biology, chemistry, biochemistry, and geology, among other disciplines. Some
specific examples of phenomena that have been modeled by CA include fluid and chemical
turbulence, plant growth and the dendritic growth of crystals, ecological theory, DNA
evolution, the propagation of infectious diseases, urban social dynamics, forest fires,
and patterns of electrical activity in neural networks. CA have also been used as discrete
versions of partial differential equations in one or more spatial variables.
Cellular Games
A cellular game is a dynamical system in which sites of a discrete
lattice play a "game" with neighboring sites. Strategies may be deterministic or
stochastic. Success is usually judged according to a universal and fixed criterion.
Successful strategies persist and spread throughout the lattice; unsuccessful strategies
disappear.
Chaos
Deterministic chaos refers to irregular or chaotic motion that is
generated by nonlinear systems evolving according to dynamical laws that uniquely
determine the state of the system at all times from a knowledge of the system's previous
history. It is important to point out that the chaotic behavior is due neither to external
sources of noise nor to an infinite number of degrees-of-freedom nor to
quantum-mechanical-like uncertainty. Instead, the source of irregularity is the
exponential divergence of initially close trajectories in a bounded region of . This
sensitivity to initial conditions is sometimes popularly referred to as the
"butterfly effect," alluding to the idea that chaotic weather patterns can be
altered by a butterfly flapping its wings. A practical implication of chaos is that its
presence makes it essentially impossible to make any longterm predictions about the
behavior of a dynamical system: while one can in practice only fix the initial conditions
of a system to a finite accuracy, their errors increase exponentially fast.
Chaotic Control
It has recently been suggested that the extreme sensitivity of
chaotic systems to small perturbations to to initial conditions (the so called
"butterfly effect") can be exploited to stabilize regular dynamic behaviors and
to effective "direct" chaotic trajectories to a desired state. This is a
capability that has no counterpart in nonchaotic systems for the ironic reason that the
trajectories in nonchaotic systems are stable and thus relatively impervious to desired
control. A recent survey article (Grebogi, Ott, et. al.) lists applications for
communications (in which chaotic fluctuations can be put to use to send controlled,
pre-planned signals), for physiology (controlling chaos in heart
rhythms), for fluid mechanics and chemical reactions. As another recent example, a few
years ago NASA used small amounts of residual hydrazine fuel to steer the ISEE3/ICE
spacecraft to its rendezvous with a comet 50 million miles away. This was possible because
of the sensitivity of the three-body problem of celestial mechanics to small
perturbations.
Classifier Systems
Classifier systems were introduced by John Holland as an attempt to
apply Genetic Algorithms to cognitive tasks. They are similar to
production systems of the "if...then" variety in artificial intelligence. A
classifier system typically consists of (1) a set of detectors (or input devices) that
provide information to the system about the state of the external environment, (2) a set
of effectors (or output devices) that transmit the classifier's conclusions to the
external environment, (3) a set of rules (or classifiers), consisting of a condition and
action, and (4) a list of messages. Learning is supervised as in multilayered Neural Networks.
Class-P Problems
The Computational Complexity of a problem is
defined as the time it takes for the fastest program running on a universal computer -as
measured in number of computing steps, say N -to compute the solution to the problem. The
complexity is then classified according to how fast N grows as a function of the problem
size, s. The first non-trivial class of problems -class-P -consists of problems for which
the computation time increases as some polynomial function of s. Problems that can be
solved with polynomial-time algorithms are called tractable; if they are solvable but are
not in the class-P, they are called intractable.
Co-Adaptation/Co-Evolution
The evolutionary process of a biological species in nature is often
described as though that species were trying to adapt to a fixed environment. However,
such a description only crudely approximates what really happens. In nature, the
"environment" consists of both a relatively (but not completely) stable physical
environment as well as other species of organisms that are simultaneously trying to adapt
to their environment. The actions of each of these other species typically affects the
actions of all other species that occupy the same physical environment. In biology (and
hence Artificial Life and studies involving Genetic
Algorithms), the terms "coadaptation" and "co-evolution" are
sometimes used to refer to the fact that all species simultaneously co-adapt and co-evolve
in a given physical environment.
Complex Adaptive Systems
Macroscopic collections of simple (and typically nonlinearly)
interacting units that are endowed with the ability to evolve and adapt to a changing
environment.
Complexity
An extremely difficult "I know it when I see it" concept to
define, largely because it requires a quantification of what is more of a qualitative
measure. Intuitively, complexity is usually greatest in systems whose components are
arranged in some intricate difficult-to-understand pattern or, in the case of a dynamical
system, when the outcome of some process is difficult to predict from its initial state.
In its lowest precisely when a system is either highly regular, with many redundant and/or
repeating patterns or when a system is completely disordered. While over 30 measures of
complexity have been proposed in the research literature, they all fall into two general
classes: (1) Static Complexity -which addresses the question of how an object or system is
put together (i.e. only purely structural informational aspects of an object), and is
independent of the processes by which information is encoded and decoded; (2) Dynamic
Complexity -which addresses the question of how much dynamical or computational effort is
required to describe the information content of an object or state of a system. Note that
while a system's static complexity certainly influences its dynamical complexity, the two
measures are not equivalent. A system may be structurally rather simple (i.e. have a low
static complexity), but have a complex dynamical behavior.
Computational Complexity
Computational complexity measures the time and memory resources that
a computer requires in order to solve a problem. A somewhat more robust measure may be
defined by invoking the Universal Turing Machine. The
Computational Complexity of a problem is then defined as the time it takes for the fastest
program running on a universal computer (as measured in number of computing steps) to
compute the solution to the problem.
Computational Irreducibility
Much of theoretical physics has traditionally been concerned with
trying to find "shortcuts" to nature. That is to say, with trying to find
methods that are able to reproduce a final state of a system by knowing the initial state
but without having to meticulously trace out each step from the initial to final states.
The fact that we can write down a simple parabola as a path a thrown object makes in a
gravitational field is an example of an instance where this might be possible. Clearly
such shortcuts ought to be possible in principle if the calculation is more sophisticated
than the computations the physical system itself is able to make. But consider a computer.
Because a computer is itself physical system, it can determine the outcome of its
evolution only by explicitly following it through. No shortcut is possible. Such
computational irreducibility occurs whenever a physical system can act as a computer. In
such cases, no general predictive ability is possible. Computational irreducibility
implies that there is a highest level at which abstract models of physical systems can be
made. Above that level, one can model only by explicit simulation.
Computational Universality
Computational universality is a property of a certain class of
computers such that changes in input alone allow any computable function to be evaluated
without any change in internal construction. Universal computers can thus simulate the
operation of any other computer, given that their input is suitably coded. Conway's Life Game, for example, has been shown to be a universal computer. This
means that with a proper selection of initial conditions (i.e. the initial distribution of
"live" and "dead" cells), Life can be turned into a general purpose
computer. This fact fundamentally limits the overall predictability of Life's behavior.
The Halting Theorem, for example, asserts that there cannot exist a general algorithm for
predicting when a computer will halt its execution of a given program. Given that Life is
a universal computer -so that the Halting theorem applies -this means that one cannot, in
general, predict whether a particular starting configuration of live and dead cells will
eventually die out. No shortcuts are possible, even in principle.
Conservative Dynamical Systems
In contrast to Dissipative Dynamical Systems,
conservative systems preserve Phase Space volumes and hence cannot display any attracting
regions in phase space; there can be no fixed points, no limit cycles and no strange
attractors. There can nonetheless be chaotic motion in the sense that points along
particular trajectories may show sensitivity to initial conditions. A familiar example of
a conservative system from classical mechanics is that of a Hamiltonian system.
Correlation Dimension
Cost Function
In optimization problems, the cost function measures how good a
particular solution to the problem is; the higher its value the better the solution. Also
called the fitness function.
Coupled-Map Lattices
Generic Cellular Automata (CA) are dynamical
systems in which space, time and the local state space are all discretized. Coupled-map
lattices are simple generalizations of CA in which space and time remain discrete, but in
which the individual site values are allowed to take on continuous values.
Criticality
"Criticality" is a concept borrowed from thermodynamics.
Thermodynamic systems generally get more ordered as the temperature is lowered, with more
and more structure emerging as cohesion wins over thermal motion. Thermodynamic systems
can exist in a variety of phases -gas, liquid, solid, crystal, plasma, etc. -and are said
to be critical if poised at a phase transition. Many phase
transitions have a critical point associated with them, that separates one or more phases.
As a thermodynamic system approaches a critical point, large structural fluctuations
appear despite the fact the system is driven only by local interactions. The disappearance
of a characteristic length scale in a system at its critical point, induced by these
structural fluctuations, is a characteristic feature of thermodynamic critical phenomena
and is universal in the sense that it is independent of the details of the system's
dynamics. (See Self-Organized Criticality)
Crossover Operator
One of three basic genetic operations used in Genetic
Algorithms. Reproduction makes a set of identical copies of a given chromosome, where
the number of copies depends on the chromosome's fitness. The crossover operator exchanges
subparts of two chromosomes, where the position of the crossover is randomly selected, and
is thus a crude facsimile of biological sexual recombination between two single-chromosome
organisms. The mutation operator randomly flips one or more bits in the chromosome, where
the bit positions are randomly chosen.
Dissipative Structure
An organized state of a physical system whose integrity is maintained
while the system is far from equilibrium. Example: the great Red-Spot on Jupiter.
Dissipative Dynamical Systems
Dissipative systems are dynamical systems that are characterized by
some sort of "internal friction" that tends to contract phase
space volume elements. Phase space contraction, in turn, allows such systems to
approach a subset of the space called an Attractor (consisting of
a fixed point, a periodic cycle, or Strange Attractor), as time
goes to infinity.
Edge-of-Chaos
The phrase "edge-of-chaos" refers to the idea that many complex adaptive systems, including life itself, seem to naturally evolve
towards a regime that is delicately poised between order and chaos.
More precisely, it has been used as a metaphor to suggest a fundamental equivalence
between the dynamics of phase transitions and the dynamics of information processing.
Water, for example, exists in three phases: solid, liquid and gas. Phase
transitions denote the boundaries between one phase and another. Universal computation
-that is, the ability to perform general purpose computations and which is arguably an
integral property of life exists between order and chaos. If the behavior of a system is
too ordered, there is not enough variability or novelty to carry on an interesting
calculation; if, on the other hand, the behavior of a system is too disordered, there is
too much noise to sustain any calculation. Similarly, in the context of evolving natural
ecologies, "edge-of-chaos" refers to how -in order to successfully adapt
-evolving species should be neither too methodical nor too whimsical or carefree in their
adaptive behaviors. The best exploratory strategy of an evolutionary "space"
appears at a phase transition between order and disorder. Despite the intuitive appeal of
the basic metaphor, note that there is currently some controversy over the veracity of
this idea.
Emergence
Emergence refers to the appearance of higher-level properties and
behaviors of a system that while obviously originating from the collective dynamics of
that system's components -are neither to be found in nor are directly deducable from the
lower-level properties of that system. Emergent properties are properties of the
"whole" that are not possessed by any of the individual parts making up that
whole. Individual line of computer code, for example, cannot calculate a spreadsheet; an
air molecule is not a tornado; and a neuron is not conscious. Emergent behaviors are
typically novel and unanticipated.
Entropy
A measure of the degree of randomness or disorder in a system.
Determines a system's capacity to evolve irreversibly in time. Specific definitions vary
depending on the type of system considered. Examples: (1) in statistical systems, the
entropy is proportional to the logarithm of the total number of possible states with the
same energy as the state under consideration.; (2) in classical thermodynamics, the
differential change in entropy of a system near equilibrium is the differential change in
absorbed heat divided by the system temperature; (3) in nonlinear deterministic dynamical
systems, the Kolmogorov-Sanai entropy is often used as a
measure. It is defined as the sum of the positive Lyapunov Exponents
of the system.
Ergodic System
An ergodic dynamical system is one whose trajectory eventually
"covers" the entire phase space. Put another way, given any point P in the phase space, the trajectory will approach P arbitrarily closely for
sufficiently large times t.
Ergodic Theory
A branch of mathematics that uses statistical concepts to describe
average properties of deterministic dynamical systems.
Evolution
A general term referring to the dynamical unfolding of behavior over
time. Darwinian evolution refers to the unfolding of higher (i.e. more complex) life forms
out of lower life forms.
Evolutionary Programming
Evolutionary programming is an early variant of genetic algorithms
and is mainly distinguished from the conventional genetic algorithm by not incorporating
crossover as an operator. Evolutionary Stable Strategy
A concept from a generalized form of Game Theory.
Animals are endowed with a finite set of possible strategies that they can use in their
interactions with other animals. Strategies may be "pure," in which the animal
acts according to a prescribed set of instructions in all contexts, or "mixed,"
in which the animal adopts different strategies with different probabilities. The
evolutionary stable strategy (ESS) is a strategy, or set of strategies such that if it is
adopted by all animals no other strategy can invade the population.
Finite Automata
Human languages can, conceptually, be regarded as a set of rules for
constructing sequences of symbols according to a fixed set of rules of composition in
order to convey meaning. One can therefore consider using a Cellular
Automaton as a formalism for studying the abstract properties of language. To be more
precise, a finite automaton M is defined to consist of a finite alphabet A, a finite set
of states X, and a state-transition function f: X x A -X that gives the next state given
the current state and the current input symbol. (There is also a set T in X, which is the
set of final or accepting states of the automaton.)
Fitness Landscape
A name for the landscape representing the fitness measure (or Cost Function) of a problem. Examples: Traveling Salesman Problem,
survivability of a real or virtual creature.
Flicker(or 1/f-) Noise
Whenever the power spectral density, S(f), scales as f^(-1), the
system is said to exhibit 1/f-noise (or flicker-noise). Despite being found almost
everywhere in nature -1/f-noise has been observed in the current fluctuations in a
resistor, in highway traffic patterns, in the price fluctuations on the stock exchange, in
fluctuations in the water level of rivers, to name just a few instances -there is
currently no fundamental theory that adequately explains why this same kind of noise
should appear in so many diverse kinds of systems. What is clear is that since the
underlying dynamical processes of these systems are so different, the common bond cannot
be dynamical in nature, but can only be a kind of "logical dynamics" describing
how a system's degrees-offreedom all interact. Self-Organized Criticality
may be a fundamental link between temporal scale invariant phenomena and phenomena
exhibiting a spatial scale invariance. Bak, et. al., argue that 1/f noise is actually not
noise at all, but is instead a manifestation of the intrinsic dynamics of Self-Organized
Critical systems.
Fractals
Fractals are geometric objects characterized by some form of
self-similarity; that is, parts of a fractal, when magnified to an appropriate scale,
appear similar to the whole. Coastlines of islands and continents and terrain features are
approximate fractals. The Strange Attractors of nonlinear dynamical
systems that exhibit deterministic Chaos typically are fractals.
Fractal Dimension
Suppose a set can be covered by a finite number N of segments of
length L. There is a simple scaling relationship between these two numbers. For a line
segment, L grows as 1/R; for a square, L grows as 1/R^2; for a cube, L grows as 1/R^3, and
so on. The fractal dimension D is defined by generalizing this intuitive scaling: D =
limR--0 ln(N)/(ln(1/R), where ln(x) is the natural logarithm. Sometimes also called the Hausdorff dimension or the Kolmogorov capacity.
Frustration
In Spin Glasses, a phenomenon in which individual
magnetic moments receive competing ordering instructions via different routes, because of
the variation of the interaction between pairs of atomic moments with separation.
Fuzzy Logic
Fuzzy set theory provides a formalism in which the conventional
binary logic based on choices "yes" and "no" is replaced with a
continuum of possibilities that effectively embody the alternative "maybe".
Formally, the characteristic function of set X defined by f(x) =1 for all x in X and
f(x)=0 for all x not in X is replaced by the membership function 0
Genetic Algorithms
Genetic algorithms are a class of heuristic search methods and
computational models of adaptation and evolution based on natural selection. In nature,
the search for beneficial adaptations to a continually changing environment (i.e.
evolution) is fostered by the cumulative evolutionary knowledge that each species
possesses of its forebears. This knowledge, which is encoded in the chromosomes of each
member of a species, is passed from one generation to the next by a mating process in
which the chromosomes of "parents" produce "offspring" chromosomes.
Genetic algorithms mimic and exploit the genetic dynamics underlying natural evolution to
search for optimal solutions of general combinatorial optimization problems. They have
been applied to the travelling salesman problem, VLSI circuit layout, gas pipeline
control, the parametric design of aircraft, neural net architecture, models of
international security, and strategy formulation.
Genetic Programming
Genetic programming is essentially an application of genetic
algorithms to computer programs. Typically the genome is represented by a LISP expression,
so that what evolves is a population of programs, rather than bit-strings as in the case
of a usual genetic algorithm. Genotype
The genetic instruction code of an individual.
Hausdorff Dimension
For an operational definition of Hausdorff dimension, proceed as
follows: Suppose a set can be covered by a finite number N of segments of length L. There
is a simple scaling relationship between these two numbers. For a line segment, L grows as
1/R; for a square, L grows as 1/R2; for a cube, L grows as 1/R3, and so on. The Hausdorff
dimension D is defined by generalizing this intuitive scaling: D = limR--0 ln(N)/(ln(1/R),
where ln(x) is the natural logarithm. Sometimes also called the fractal dimension or the
Kolmogorov capacity.
Hierarchy
Hierarchies consist of levels each of which include all lower levels;
i.e. systems within systems within systems...within the total system in question.
Evolution in complex systems leads to differentiation in multilevel hierarchic systems.
Holarchy Homoclinic Point
A point in Phase Space of a nonlinear dynamical
system that evolves to a point of unstable equilibrium in infinite time.
Homoclinic Orbit
The ensemble of points in the Phase Space of a
nonlinear dynamical system that all evolve to a point of unstable equilibrium after an
infinite time.
Hopf-Bifurcation
In the Logistic Map, a fixed point may lose
its stability by splitting (or bifurcating) into a pair of points that form a period two
orbit. Another common way in which a point may become unstable is by effectively turning
into a small circle that then increases in size, deforms and becomes unstable as the
controlling parameter is increased. This is called the Hopf Bifurcation.
Hypercycle
A scenario for the origin of self-replicating molecular systems
proposed by Manfred Eigen. The scenario involves template-instructed replicating cycles
consisting of feedback loops in which molecule A generates molecule B, molecule B
generates molecule C, and molecule C generates molecule A, and so on.
Information Dimension
Partition a d-dimensional Phase Space into boxes
of volume ed. The probability of finding a point of an Attractor
in box i is pi(e) = Ni(e)/N(e), where Ni(e) is the number of points in the ith box and
N(e) is the total number of non-empty boxes. pi(e) is the relative frequency with which
the ith box is visited. The amount of information required to specify the state of the
system to within an accuracy "e" (or, equivalently, the information gain in
making a measurement that is uncertain by an amount "e"), is given by . The
information dimension, DI, of an attractor is then defined to be DI = lim e--0
I(e)/ln(1/e).
Information Theory
Like the physically primitive notions of mass and energy of a
particle, the information content, I, of an arbitrary measurement or message composed of
particular symbol sequence, is itself a primitive concept. While the roots of information
theory extend back to the definition of the classical entropy of a physical system
introduced by Clausius in 1864 and Boltzman's probabilistic re-interpretation of classical
entropy in 1896, the mathematical formalism for measuring I is due largely to a seminal
1948 paper by Claude E. Shannon. Within the context of sending and receiving messages in a
communication system, Shannon was interested in finding a measure of the information
content of a received message. Shannon's approach was to obtain a measure of the reduction
of uncertainty given some a-priori knowledge of the symbols being sent. Suppose we are
given N different and a-priori equally likely possible outcomes. A measure of the
information gain, I, is obtained by required that I be additive for independent events.
That is to say, if there are two independent sets of outcomes N1 nd N2, so that the total
number of outcomes is N = N1 + N2, it is required that I(N1 * N2) = I(N1) + I(N2). This
requirement is uniquely satisfied by the function I= c log(N), where "c" is an
arbitrary constant.
Intermittency
A term used in the study of nonlinear dynamical systems describing
the changes between quiet, regular periods of activity (called the laminar phase) and
periods of wild, chaotic oscillation (called bursts). Intermittency is a common route to chaos in physical systems.
Kolmogorov Entropy
The Kolmogorov entropy (or K-entropy) is a useful measure by which to
characterize chaotic motion in an arbitrary-dimensional Phase Space.
Loosely speaking, the K-entropy is proportional to the rate at which information about the
state of a dynamical system is lost in the course of time. It is related to the average Lyapunov ExponentLyapunov Exponent, which measures the exponential
rate of divergence of nearby trajectories.
Lattice Gas Models
Lattice gases are micro-level rule-based simulations of macro-level
fluid behavior. The Navier-Stokes Equations, the fundamental
equations describing incompressible fluid flow, are in general analytically intractable.
Lattice-gas models provide a powerful new tool in modeling real fluid behavior. The idea
is to reproduce the desired macroscopic behavior of a fluid by modeling the underlying
microscopic dynamics. In order to achieve an Emergence of a suitable macrodynamics out of
a discrete microscopic substrate, one must have three basic ingredients: (1) local
thermodynamic equilibrium, (2) conservation laws, and (3) a "scale separation"
between the levels at which the microscopic dynamics takes place (among kinetic variables
living on a micro-lattice) and the collective motion itself appears (defined by
hydrodynamical variable on a macro-lattice). Another critical feature is the symmetry of
the underlying lattice. While there are many basic variants of the model, one can show
that there is a well-defined minimal set of rules that define a lattice-gas system whose
macroscopic behavior reproduces that predicted by the Navier-Stokes equations exactly.
Life Game
Invented by the mathematician John Conway, Life is arguably the most
widely known Cellular Automaton. It was extensively popularized by
Martin Gardner in his "Mathematical Games" department in Scientific American in
the early 1970s. Life is "played" using the eight nearest-neighbors on a
lattice, and consists of (1) seeding the lattice with some pattern of "live" and
"dead" cells, and (2) simultaneously (and repeatedly) applying the following
three rules to each cell of the lattice at discrete time steps: (i) Birth: replace a
previously dead cell with a live one if exactly 3 of its neighbors are alive; (ii) Death:
replace a previously live cell with a dead one if either (1) the living cell has no more
than one live neighbor (i.e. it dies of isolation), or
(2) the living cell has more than three neighbors (i.e. it dies of
overcrowding); (iii) Survival: retain living cells if they have either 2 or 3 neighbors
One of the most intriguing patterns in Life is an oscillatory propagating pattern known as
the "glider." It consists of 5 "live" cells and reproduces itself in a
diagonally displaced position once every four iterations. When the states of Life are
projected onto a screen in quick succession by a fast computer, the glider gives the
appearance of "walking" across the screen. The propagation of this pseudo-stable
structure can also be seen as a self-organized emergent property of the system.
Limit-Cycle
An Attractor describing regular (i.e.
periodic or quasi-periodic) temporal behavior.
Lindenmeyer (or L-) Systems
L-systems were introduced by Aristid Lindenmeyer in 1968 as a model
for the cellular development of filamentous plants. In simplest terms, L-systems consist
of production rules for rewriting abstract strings of symbols. They can be thought of as
generalized Cellular Automata in which the number of sites can
increase over time.
Logistic Equation
The logistic map is one of the simplest (continuous and
differentiable) nonlinear systems that captures most of the key mechanisms responsible for
producing deterministic chaos. It is a one-dimensional nonlinear
discrete difference equation with a single control parameter, a: xn+1 = axn(1-xn), where 0
< x0 < 1 and 0 < a < 4. The logistic equation undergoes a sequence of
period-doublingBifurcations followed by regions of deterministic chaos as a is varied
between the values 0 and 4. Some aspects of this behavior such as the ratio of bifurcation
intervals as chaos is approached are Universal; that is, are independent of the details of
the system.
Lotka-Volterra Equations
In 1926, Volterra proposed a simple model for the predation of one
species by another to explain the oscillatory level of certain fish in the Atlantic. If
N(t) is the prey population and P(t) is the predator population at time t then Volterras's
model is dN/dt = N (a -bP), dP/dt = P (cN -d), where a,b,c, and d are positive constants.
The model assumes: (1) prey in absence of predation grows linearly with N (i.e. in
Malthusian fashion); (2) predation reduces prey's growth rate by a term proportional to
the prey and predation populations; (3) the predator's death rate, in the absence of prey,
decays exponentially; (4) the prey's contribution to the predator's growth rate is
proportional to the available prey as well as to the size of the predator population. The
system of equations is known as the Lotka-Volterra equations because Lotka derived the
same equations in 1920 for a chemical reaction he believed to exhibit periodic behavior.
Lyapunov Exponent
A fundamental property of chaotic dynamics is
sensitivity to small changes to initial conditions. Initially closely separated starting
conditions evolving along regular dynamical trajectories diverge only linearly in time; a
chaotic evolution, on the other hand, leads to exponential divergence in time. Lyapunov
exponents quantify this divergence by measuring the mean rate of exponential divergence of
initially neighboring trajectories. A trajectory of a system with a negative Lyapunov
exponent is stable and will converge to an Attractor
exponentially with time. The magnitude of the Lyapunov exponent determines how fast the
attractor is approached. A trajectory of a system with a positive Lyapunov exponent is
unstable and will not converge to an attractor. The magnitude of the positive Lyapunov
exponent determines the rate of exponential divergence of the trajectory.
Markov Process
A Markov process is a process for which, if the present is given, the
future and past are independent of each other. More precisely, if t1 < ... < tn are
parameter values, and if 1 < j < n, then the sets of random variables [x(t1), ...,
x(tj-1)] and [x(tj+1), ...,x(tn)] are mutually independent for given x(tj). Equivalently,
the conditional probability distribution of x(tn) for given x(t1), ..., x(tn-1) depends
only on the specified value of x(tn-1) and is in fact the conditional probability
distribution of x(tn), given x(tn-1). An important and simple example is the Markov chain,
in which the number of states is finite or denumerably infinite.
Maximum Entropy
The principle of maximum entropy states that when one has only
partial information about the probabilities of possible outcomes of an experiment, one
should choose the probabilities so as to maximize the uncertainty about the missing
information. Put another way, since entropy is a measure of randomness, one should choose
the most random distribution subject to whatever constraints are imposed on the problem.
Mean-Field Theory
In a mean field approximation a system is assumed to be determined by
the average properties of the system as a whole. In a mean-field-theoretic description of
a thermodynamic system, for example, all particles are considered to contribute equally to
the potential at each site. Therefore, the mean field theory essentially assumes the
intermolecular interaction to be of infinite range at all temperatures. The mean field
theories are qualitatively quite successful in that they predict the existence of critical
points and power law dependence of the various thermodynamic quantities near the critical
point. They generally become more quantitatively successful as the dimensionality of the
system increases.
Multifractal
The simplest fractal sets are characterized
by some form of self-similarity, in which parts, when magnified by a constant r, appear
similar to the original whole. The more general class of fractals are really multi-scale
fractals, or multifractals, which are characterized by multiple subdivisions of the
original into N objects, each magnified by by a different factor ri, i=1,2,...,N.
Navier-Stokes Equations
These are a set of analytically intractable coupled nonlinear partial
differential equations describing fluid flow.
Neural Networks
Neural nets represent a radical new approach to computational problem
solving. The methodology they represent can be contrasted with the traditional approach to
artificial intelligence (AI). Whereas the origins of AI lay in applying conventional
serial processing techniques to high-level cognitive processing like concept-formation,
semantics, symbolic processing, etc. -or in a top-down approach -neural nets are designed
to take the opposite -or bottom-up -approach. The idea is to have a human-like reasoning
emerge on the macro-scale. The approach itself is inspired by such basic skills of the
human brain as its ability to continue functioning with noisy and/or incomplete
information, its robustness or fault tolerance, its adaptability to changing environments
by learning, etc. Neural nets attempt to mimic and exploit the parallel processing
capability of the human brain in order to deal with precisely the kinds of problems that
the human brain itself is well adapted for.
Nonlinearity
If f is a nonlinear function or an operator, and x is a system input
(either a function or variable), then the effect of adding two inputs, x1 and x2, first
and then operating on their sum is, in general, not equivalent to operating on two inputs
separately and then adding the outputs together; i.e. . Popular form: the whole is not
necessarily equal to the sum of its parts. Dissipative nonlinear dynamic systems are
capable of exhibiting self-organization and chaos.
NP-Hard Problems
A class of problems, known as nondeterministic polynomial time -or
class-NP -problems, that may not necessarily be solvable in polynomial time, but the
actual solutions to which may be tested for correctness in polynomial time.
NP-Complete
Just as there are universal computers that,
given a particular input, can simulate any other computer, there are NP-complete problems
that, with the appropriate input, are effectively equivalent to any NP-hard problem of a
given size. For example, Boolean "satisfiability" -i.e. the problem of
determining truth values of the variable's of a Boolean expression so that the expression
is true -is known to be an NP-complete problem.
Order Parameter
An order parameter is a scalar or vector parameter associated with a
continuous phase transition that determines the physical nature of
the transition. It has the value zero in the random state (typically above the transition
temperature) and takes on a nonzero value in the ordered state (typically below the
transition). In the case of a fluid, for example, the order parameter is a scalar and is
the difference in density between the liquid and vapor phases.
Percolation Theory
Percolation Theory represents one of the simplest models of a
disordered system. Consider a square lattice, where each site is occupied randomly with
probability p or empty with probability 1-p. Occupied and empty sites may stand for very
different physical properties. For simplicity, let us assume that the occupied sites are
electrical conductors, the empty sites represent insulators, and that electrical current
can flow between nearest neighbor conductor sites. At low concentration p, the conductor
sites are either isolated or form small clusters of nearest neighbor sites. Two conductor
sites belong to the same cluster if they are connected by a path of nearest neighbor
conductor sites, and a current can flow between them. At low p values, the mixture is an
insulator, since a conducting path connecting opposite edges of the lattice does not
exist. At large p values, on the other hand, many conduction paths between opposite edges
exist, where electrical current can flow, and the mixture is a conductor. At some
concentration in between, therefore, a threshold concentration pc must exist where for the
first time electrical current can percolate from one edge to the other. Below pc, we have
an insulator; above pc we have a conductor. The threshold concentration is called the
percolation threshold, or, since it separates two different phases, the critical
concentration.
Petri Nets
Petri nets are abstract models used to represent parallel systems and
processes. They are typically described using directed graphs (i.e. graphs whose edges are
depicted by arrows showing a direction of information flow). More precisely, a petri net
is a seven-tuple (P, T, V, f, g, N, m), where (1) P is a nonempty finite set of nodes, (2)
T is a nonempty finite set of transitions, (3) V is a valuation space {0,1}, (4) f is a
binary function used in determining the connections from nodes to transitions (i.e. f: P x
T -V, and if f(p,t)=1 then node P connects to transition T, otherwise not), (5) g is a
binary function used in determining the transitions to connect to nodes (i.e. g: T x P -V
and a connection is made from t to p if and only if g(t,p)=1), (6) N is a set of markings
{0,1,2,...}, and (7) m is the initial marking function, m: P -N.
Phase Space
A mathematical space spanned by the dependent variables of a given
dynamical system. If the system is described by an ordinary differential flow the entire
phase history is given by a smooth curve in phase space. Each point on this curve
represents a particular state of the system at a particular time. For closed systems, no
such curve can cross itself. If a phase history a given system returns to its initial
condition in phase space, then the system is periodic and it will cycle through this
closed curve for all time. Example: a mechanical oscillator moving in one-dimension has a
two-dimensional phase space spanned by the position and momentum variables.
Phase Transition
An abrupt change in a system's behavior. A common example is the
gas-liquid phase transition undergone by water. In such a transition, a plot of density
versus temperature shows a distinct discontinuity at the critical temperature marking the
transition point. Similar behavior can be seen in systems described by ordinary
differential flows and discrete mappings. In nonlinear dynamical systems, the transition
from self-organizing to chaotic behavior is sometimes referred to as a phase transition
(or, more specifically, as an order-disorder transition).
Phenotype
The overall attributes of an organism arising from the interaction of
its Genotype with the environment.
Poincare Map
A dynamical system is usually defined as a continuous flow, that is
(1) is completely defined at all times by the values of N variables -x1(t), x2(t), ...,
xN(t), where xi(t) represents any physical quantity of interest, and (2) its temporal
evolution is specified by an autonomous system of N, possibly coupled, ordinary
first-order differential equations. Once the initial state is specified, all future states
are uniquely defined for all times t. A convenient method for visualizing continuous
trajectories is to construct an equivalent discrete-time mapping by a periodic
"stroboscopic" sampling of points along a trajectory. One way of accomplishing
this is by the so-called Poincare map (or surface-of-section) method. Suppose the
trajectories of the system are curves that live in a three-dimensional Phase
Space.The method consists essentially of keeping track only of the intersections of
this curve with a two-dimensional plane placed somewhere within the phase space.
Prisoner's Dilemma
The prisoner's dilemma is a two person non-zerosum game
that has been widely used in experimental and theoretical investigations of
cooperative behavior. Two persons suspected of a crime are caught,
but there is not enough evidence to sentence them unless one of them confesses. If they
are both quiet (or cooperate, C), both will have to be released. If one confesses
(defects, D) but the other does not, the one who confesses will be released but the other
will be imprisoned for a long time. Finally, if both confess, both will be imprisoned, but
for a shorter time. It is assumed that the prisoner's make their respective choices
separately and independently of one another. If the game is "played" once, each
player find defection to be the optimal behavior, regardless of what his opponent chooses
to do. Finding the optimal strategy to follow over time, however, is considerably more
difficult.
Probabilistic CA
Cellular Automata for which the deterministic
state transitions are replaced with specifications of the probabilities of cell-value
assignments. For such systems, the focus of analysis shifts from studying evolutions of
arbitrary initial states to studying ensembles of trajectories.
Punctuated Equilibrium
A theory introduced in 1972 to account for what the fossil record
appears to suggest are a series of irregularly spaced periods of chaotic and rapid
evolutionary change in what are otherwise long periods of evolutionary stasis. Some Artificial Life studies suggest that this kind of behavior may be
generic for evolutionary processes in complex adaptive systems.
Quasiperiodic
Characterizes behavior of a dynamical system that is almost, but not
quite, periodic.Quasiperiodic regions of Phase Space are frequently
linked together to form a Strange Attractor. The transition between
such quasiperiodic regions is characterized by the crossing of a Homoclinic
Point. Quasiperiodicity often results when nonlinear dynamical systems are driven by
periodic driving forces with periods that are incommensurate with (i.e. not a rational
fraction of) the system response time.
Random Boolean Networks
A size N random Boolean network of size k generalizes the basic
binary Cellular Automata model by evolving each site variable xi =
0 or 1 according to a randomly selected Boolean Function of k inputs. Since there are two
choices for every combination of states of the k inputs at each site, the Boolean function
is randomly selected from among the 2^(2n) possible Boolean functions of k inputs. This
model was first introduced by Kauffman in 1969 in a study of cellular differentiation in a
biological system (binary sites were interpreted as elements of an ensemble of genes
switching on and off according to some set of random rules). Since its conception,
however, related models have found wide application in an increasingly large domain of
diverse problems. Such models of strongly disordered systems exhibit remarkable and
unexpected order.
Reaction-Diffusion Models
Reaction-diffusion systems, the first studies of which date back to
the 1950s, often exhibit a variety of interesting spatial patterns that evolve in
self-organized fashion. One of the most famous reaction-diffusion systems -widely regarded
as the prototypical example of oscillating chemical reactions -is the so-called
Belousov-Zhabotinskii (or BZ) reaction. The BZ model involves the reaction of bromate ions
with an organic substrate (typically malonic acid) in a sulfuric acid solution with cerium
(or some other metal-ion catalyst). When this mixture is allowed to react exothermally at
room temperature, interesting spatial and temporal oscillations (i.e. chemical waves)
result. The system oscillates, changing from yellow to colorless to back to yellow about
twice a minute with the oscillations typically lasting for over an hour (until the organic
substrate is exhausted). A number of Cellular Automata models have
been found that exhibit BZ-like spatial waves.
Relativistic Information Theory
Relativistic information theory is a concept introduced by Jumarie
and has been suggested as a possible formalism for describing certain aspects of military
command and control processes by Woodcock and Dockery. The basic idea is that a
generalized entropy is endowed with four components, so that it is equivalent to a
four-vector and may be transformed by a Lorentz transformation (As in relativity). These
four components consists of: (1) the external entropy of the environment (Ho), (2) the
internal entropy of the system (Hi), (3) system goals, and (4) the internal transformation
potential, which measures the efficiency of the system's internal information
transformation. An additional factor, called the organizability, plays the role of
"velocity." Woodcock and Dockery show that it is possible to use relativistic
information theory to compare the relative command and control system response of two
command structures to the world around them. The quantity of interest is dHi/dHo, or the
rate of change of the internal information environment with respect to changes in the
surrounding environment.
Scaling Laws
Theoretical studies of critical phenomena have focused on predicting
the value of critical exponents. One of the most important ideas is the scaling
hypothesis. This hypothesis is model-independent and applicable to all critical systems.
The underlying assumption is that the long-range correlation of the order parameter, such
as the density fluctuation in a fluid system near the critical temperature, is responsible
for all singular behavior. This assumption leads to a particular functional form for the
equation of state near the critical point.
Search Space
The variation of the Cost Function can be
imagined to be a landscape of potential solutions to a problem where the height of each
feature represents its cost. This landscape is sometimes referred to as the search space.
Self-Organization
The spontaneous emergence of macroscopic nonequilibrium organized
structure due to the collective interactions among a large assemblage of simple
microscopic objects.
Self-Organized Criticality
Self-organized criticality (SOC) describes a large body of both
phenomenological and theoretical work having to do with a particular class of time-scale
invariant and spatial-scale invariant phenomena. Fundamentally, SOC embodies the idea that
dynamical systems with many degrees of freedom naturally self-organize into a critical
state in which the same events that brought that critical state into being can occur in
all sizes, with the sizes being distributed according to a power-law. The kinds of
structures SOC seeks to describe the underlying mechanisms for look like equilibrium
systems near critical points (see Criticality) but are not near
equilibrium; instead, they continue interacting with their environment, "tuning
themselves" to a point at which critical-like behavior appears. Introduced in 1988,
SOC is arguably the only existing holistic mathematical theory of self-organization
in complex systems, describing the behavior of many real systems in physics, biology and
economics. It is also a universal theory in that it predicts that the global properties of
complex systems are independent of the microscopic details of their structure, and is
therefore consistent with the "the whole is greater than the sum of its parts"
approach to complex systems. Put in the simplest possible terms, SOC asserts that
complexity is criticality. That is to say, that SOC is nature's way of driving everything
towards a state of maximum complexity.
Simulated Annealing
A mathematical technique for general combinatorial optimization
problems.The name comes from the physical process of annealing, during which a material is
first heated and then slowly cooled. During annealing, the component atoms of a material
are allowed to settle into a lower energy state so that a more stable arrangement of atoms
is maintained throughout the cooling process.
Solitons
A mathematically appealing model of real particles is that of
solitons. It is known that in a dispersive medium, a general wave form changes its shape
as it moves. In a nonlinear system, however, shape-preserving solitary waves exist.
Spatio-Temporal Chaos
A large class of spatially extended systems undergoes a sequence of
transitions leading to dynamical regimes displaying chaos in both
space and time. In the same way as temporal chaos is characterized by the coexistence of a
large number of interacting time scales, spatio-temporal chaos is characterized by having
a large number of interacting space scales. Examples of systems leading to spatio-temporal
chaos include the Navier-Stokes Equations and reaction-diffusion
equations. Coupled-map Lattices have been used for study.
Spin Glasses
A magnetic material whose magnetic magnets respond to both
ferromagnetic and antiferromagnetic interactions causing frustration,
so that not all the constraints necessary to minimize the system's overall energy can be
simultaneously satisfied. There are exponentially stable states, but finding the global
ground state is an NP-Hard optimization problem.
Strange Attractors
Describes a form of long-term behavior in dissipative
dynamical systems. A strange attractor is an Attractor that
displays sensitivity to initial conditions. That it to say, an attractor such that
initially close points become exponentially separated in time. This has the important
consequence that while the behavior for each initial point may be accurately followed for
short times, prediction of long time behavior of trajectories lying on strange attractors
becomes effectively impossible. Strange attractors also frequently exhibit a self-similar
or fractal structure.
Symbolic Dynamics
Symbolic dynamics is a tool that is used to obtain a coarse-grained
representation of dynamical orbits consisting of discrete-symbol sequences. This is done
by first partitioning the Phase Space into a finite number of cells
C1, C2,..., CN and and focusing on the successive cell-to-cell transitions of the
trajectory. The states of the cells, S(C1), S(C2),..., S(CN), are treated as symbols of an
N-letter alphabet. Looked at in this way, the continuous dynamics thus induces on the
partition a symbolic dynamics describing how the letters of the alphabet evolve in time.
Synergetics
Synergetics refers to what can loosely be called the
"European" (vice US) approach to the study of complex systems. Consider a
complex system (that is, a system composed of many individual parts) that is controlled
from the outside in some manner by a control parameter (say, the system is driven by a
constant influx of energy and/or matter). As the control parameter is changed, the
system's state can become unstable and be replaced by a new state characterized by
particular kinds of spatial, temporal or functional structures. Synergetics consists of
strategies of describing what happens when the macroscopic state of systems undergoes a
qualitative change. More colloquially, "synergy" is used to refer to how the
action of two or more entities ("parts") can achieve an effect that cannot be
achieved by any of the parts alone (see Emergence).
Topological Dimension
The topological dimension of object X is an integer defining the
number of coordinates needed to specify a given point of X. A single point therefore a
topological dimension equal to zero; a curve has dimension one, a surface has dimension
two, and so on.
Universality
Universal behavior, when used to describe the behavior of a dynamic
system, refers to behavior that is independent of the details of the system's dynamics. It
is a term borrowed from thermodynamics. According to thermodynamics and statistical
mechanics the critical exponents describing the divergence of certain physical measurables
(such as specific heat, magnetization, or correlation length) are universal at a phase transition in that they are essentially independent of the
physical substance undergoing the phase transition and depend only on a few fundamental
parameters (such as the dimension of the space).
Universal Computer
Universal Turing Machine
Unstable Equilibrium
A stationary state of a dynamical system such that an arbitrarily
small perturbation can cause a disturbance of arbitrarily large magnitude. Example: an egg
poised on the vertex of a cone.
