Saddle
A type of surface that is neither a peak nor a valley but still has a
0 gradient. Saddle points are situated such that moving in
one direction takes one uphill, while moving in another direction
would be downhill. Hence, saddles look like the things that cowboys
ride on.
Scalar
A single number, as opposed to a multidimensional vector or
matrix.
Schema/Schemata
A similarity template used to analyze genetic algorithms. By
using wild-card characters, a schema defines an entire class of
strings that may be found in a population.
Search/Search Method
A method for finding a region of interest in a search space.
Usually, the interesting regions correspond to solutions to a specific
problem. Hill-climbing, steepest descent (ascent),
simulated annealing, and genetic algorithms are all search
methods.
Search Space
A characterization of every possible solution to a problem instance.
For a neural network the search space is defined as all possible
assignments to the network weights; for a genetic algorithm,
it is every conceivable value assignment to the strings in the
population.
Selection
See natural selection.
Self-Organization
A spontaneously formed higher-level pattern of structure or
function that is emergent through the interactions of
lower-level objects.
Self-Organized Criticality (SOC)
A mathematical theory that describes how systems composed of many
interacting parts can tune themselves toward dynamical behavior
that is critical in the sense that it is neither stable nor
unstable but at a region near a phase transition. SOC
systems display events in a power-law distribution and are never quite
at equilibrium. See also edge of chaos and
self-organization.
Self-Referential
Referring directly back to oneself through information flow,
influence, or cause and effect. See Self-Referential.
Self-Similar
An object that is structurally recursive in that a part will look
like the whole. See also fractal.
Sensitivity
The tendency of a system (sometimes chaotic) to change
dramatically with only small perturbations.
Set
A collection of things, usually numbers. Sets may be infinite in size.
Shadowing Lemma
Implies that a numerical simulation of chaos may ``shadow''
a real trajectory of a real chaotic system.
Sigmoidal
An ``S'' shaped function that is often used as an activation
function in a neural network.
Simulate/Simulation
Experimentation in the space of theories, or a combination
of experimentation and theorization. Some numerical simulations
are programs that represent a model for how nature works.
Usually, the outcome of a simulation is as much a surprise as the
outcome of a natural event, due to the richness and uncertainty of
computation.
Simulated Annealing
A partially random method of search and optimization
usually used for combinatorial optimization problems. The
technique is modeled on how the molecular structure of metals is
disordered at high temperatures but very ordered and crystalline at
low temperatures. In simulated annealing, a problem instance is
reformulated so that it loosely resembles disordered material.
Gradually, the temperature is lowered such that the ordered states
correspond to good solutions to a problem.
Space Complexity
A function that describes the amount of memory required for a
program to run on a computer to perform a particular task. The
function is parameterized by the length of the program's input. See
also time complexity.
Space-Filling
Refers to a curve that manages to twist and turn in such a way that it
actually fills a space or volume. All space-filling curves are
fractal.
Special Function
In Lisp or Stutter, a built-in function that may or may
not fully evaluate its arguments, such as the if primitive.
Stable
Having a basin of attraction that is non-zero in size; an
attractor that can withstand some form of perturbation.
Standard Deviation
A measure of the spread of a set of data. For a Gaussian
distribution, the standard deviation hints at the width of the tails
of the distribution function.
Statement
In a formal system, a string of characters that is formed
according to well-defined rules such that it is legal for the language
that is the formal system. For example, in the formal system of
arithmetic, the expression ``5 + 3 * (2 - 4)'' is a valid and
well-formed statement, but ``5 + )3 * * (2 (- 4)'' is not.
State Space
In this book, another name for the phase space of a dynamical
system. Roughly speaking, if the dynamics of a dynamical system
can be described by n values, then the state space is the
n-dimensional volume that the system moves through. Systems
that are continuous in time will form a smooth trajectory through
this volume, while discrete systems may jump to different
locations on subsequent time steps. In either case, if a system ever
returns to a previously visited location in the state space, then the
system is in either a fixed point or a limit cycle. For
chaotic systems, or for programs that never halt, the system
will always be at a previously unvisited portion of the state space.
Steepest Descent (Ascent)
A search method that uses the gradient information of a
search space and moves in the opposite direction from the gradient
until no further downhill (or uphill) progress can be made. See also
hill-climbing.
Stochastic
Something that is random.
Strange Attractor
An attractor of a dynamical system that is usually
fractal in dimension and is indicative of chaos.
Strategy
In game theory, a policy for playing a game. A strategy is a
complete recipe for how a player should act in a game under all
circumstances. Some policies may employ randomness, in which
case they are referred to as mixed strategies.
Strength
For a classifier system, a classifier's relative ability to
win a bidding match for the right to post its message on the
message list.
String
Any sequence of letters, numbers, digits, bits, or symbols.
Stutter
A silly programming language used in this book that is based on
Lisp and is capable of universal computation.
Symmetric Matrix
A matrix with the lower-left half equal to the mirror image of
the upper-right half.
Synapse
The junction between two neurons in which neural activity is
propagated from one neuron to another. See also
excitatory, inhibitory, and weight.
Synchronous
Acting in a lockstep fashion, with each event occurring in a precise
order, or in such a way as to eliminate the notion of order entirely.
System
Something that can be studied as a whole. Systems may consist of
subsystems that are interesting in their own right. Or they may exist
in an environment that consists of other similar systems.
Systems are generally understood to have an internal state, inputs
from an environment, and methods for manipulating the environment or
themselves. Since cause and effect can flow in both directions of a
system and environment, interesting systems often posses
feedback, which is self-referential in the strongest case.