A simple fractal set composed of an uncountable
infinity of dust-like points, but that also has 0 measure (meaning
that the sum width of all points is 0). The Cantor set is constructed
by removing the middle third of a unit line segment, and then
recursively removing the middle third of any remaining line
segments, for an infinite number of steps.
Cellular Automaton (CA)
A discrete dynamical system that is composed of an array of
cells, each of which behaves like a finite-state automaton. All
interactions are local, with the next state of a cell being a
function of the current state of itself and its neighbors.
Conway's Game of Life is a CA.
Irregular motion of a dynamical system that is
deterministic, sensitive to initial conditions, and impossible
to predict in the long term with anything less than an infinite and
perfect representation of analog values.
Four classes of languages (or computing machines) that have increasing
complexity: regular (finite-state automata), context-free
(push-down automata), context-sensitive (linear bounded automata), and
recursive (Turing machines).
A rule that is part of a classifier system and has a condition
that must be matched before its message (or action) can be posted
(or effected). The strength of a classifier determines the
likelihood that it can outbid other classifiers if more than one
condition is matched.
An adaptive system similar to a Post production system
that contains many ``if ... then'' rules called classifiers.
The state of the environment is encoded as a message by a
detector and placed on the message list from which
the condition portion of the classifiers can be matched. ``Winning''
classifiers can then post their own messages to the message list,
ultimately forming a type of computation that may result in a message
being translated into an action by an effector. The
strengths of the classifiers are modified by the bucket
brigade algorithm, and new rules can be introduced via a genetic
Two or more entities experience evolution in response to one
another. Due to feedback mechanisms, this often results in a
biological arms race.
A set composed of all elements that are not members of another
A class of problems in which the number of candidate solutions is
combinatorial in size. Each possible solution has an associated cost.
The goal is to find the solution with the lowest cost. Because of the
vast numbers involved, explicit search an entire
search space is not always possible.
Describes a formal system in which all statements can be
proved as being true or false. Most interesting formal systems are
not complete, as proved in Gödel's Incompleteness Theorem.
A number that has a real component and an imaginary
component and is characterized as a point on a plane (instead of the
real number line).
A collection of many simple nonlinear units that operate in
parallel and interact locally with each other so as to produce
An ill-defined term that means many things to many people. Complex
things are neither random nor regular, but hover somewhere in
between. Intuitively, complexity is a measure of how interesting
something is. Other types of complexity may be well defined; see the
index for other references.
Having a description that is smaller than itself; not random;
Expressible as a yes/no question that can be answered in any case by a
computer in finite time.
The realization of a program in a computer.
The amount of interaction in a system, the structure of the
weights in a neural network, or the relative number of
edges in a graph.
A dynamical system that preserves the volume of its state
space under motion and, therefore, does not display the types of
behavior found in dissipative systems.
In formal systems, having the property that all statements
are either true or false.
Taking a real value, i.e., not discrete. Dynamical
systems may operate in continuous time or space.
Exerting actions to manipulate a system or environment in a
For computers, halting with an answer; for dynamical systems,
falling into an attractor; for searches (e.g.,
genetic algorithms), finding a location that cannot be improved
upon; for infinite summations, approaching a definite value.
Conway's Game of Life
A cellular automaton rule set that operates on a two-dimensional
grid. Each cell changes its state according to the states of its
eight nearest neighbors: dead cells come alive with exactly three live
neighbors, and cells die if they have anything but two or three
neighbors. The Game of Life can display complex patterns such as
gliders, fish, and glider guns, and is also capable of
Co-Recursively Enumerable (CO-RE)
The complement of a set that can be recursively
Having the same number of objects as the set of natural
A genetic operator that splices information from two or more parents
to form a composite offspring that has genetic material from all