Glossary of Terms

After G.W. Flake's The Computational Beauty of Nature: Computer explorations of fractals, chaos, complex systems, and adaptation., MIT Press, 2000.

Adaptive
Subject to ADAPTATION; can change over time to improve fitness or accuracy.

Adaptation
An internal change in a SYSTEM that mirrors an external event in the system's ENVIRONMENT. Could be a consequence of LEARNING.

Always Cooperate
An ITERATED PRISONER'S DILEMMA STRATEGY that cooperates with its opponent under all circumstances (the exact opposite of ALWAYS DEFECT).

Always Defect
An ITERATED PRISONER'S DILEMMA STRATEGY that never cooperates with its opponent under any circumstance (the exact opposite of ALWAYS COOPERATE).

Autonomous Agent
An entity with limited perception of its ENVIRONMENT that can process information to calculate an action so as to be goal-seeking on a local scale.

Bottom-Up
A description that uses the lower-level details to explain higher-level patterns; related to REDUCTIONISM.

Cellular Automation (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 neighbours. CONWAY'S GAME OF LIFE is a CA.

Coevolution
Two or more entities experience EVOLUTION in response to one another. Due to FEEDBACK mechanisms, this often results in a biological ARMS RACE.

Conway's Game of Life
A CELLULAR AUTOMATON rule set that operates on a two-dimensional grid. Each cell changes its stat according to the states of its eight nearest neighbours: dead cells come alive with exactly three live neighbours, and cells die if they have anything but two or three neighbours. The Game of Life can display complex patterns such as GLIDERS, FISH, and GLIDER GUNS, and is also capable of UNIVERSAL COMPUTATION.

Crossover
A genetic operator that splices information from two or more parents to form a composite offspring that has genetic material from all parents.

Difference Equation
An equation that describes how something changes in DISCRETE time steps. NUMERICAL SOLUTIONS to INTEGRALS are usually realized as difference equations.

Differential Equation
A description of how something CONTINUOUSLY changes over time. Some differential equations can have an ANALYTICALLY SOLUTION such that all future states can be know without SIMULATION of the time evolution of the SYSTEM. However, most can have a NUMERICAL SOLUTION with only limited accuracy.

Dynamics/Dynamical
Pertaining to the change in behaviour of a SYSTEM over time.

Emergent
Refers to a property of a collection of simple subunits that comes about through the interactions of the subunits and is not a property of any single subunit. For example, the organization of an ant colony is said to "emerge" from the interactions of the lower-level behaviours of the ant, and not from any single ant. Usually, the emergent behaviour is unanticipated and cannot be directly deduced from the lower-level behaviours. COMPLEX SYSTEMS are usually emergent.

Euler's Method
The simplest method of obtaining a NUMERICAL SOLUTION of a DIFFERENTIAL EQUATION. There are many other numerical techniques that are more accurate; however, an ANALYTICAL SOLUTION (i.e., a closed form of an integral) is always preferred but not always possible.

Evolution
A process operating on populations that involves VARIATION among individuals, traits being INHERITABLE, and a level of FITNESS for individuals that is a FUNCTION of the possessed traits. Over relatively long periods of time, the distribution of inheritable traits will tend to reflect the fitness that the traits convey to the individual; thus, evolution acts as a filter that selects fitness-yielding traits over other traits.

Finite-State Automation (FSA)
The simplest computing device. Although it is not nearly powerful enough to preform UNIVERSAL COMPUTATION, it can recognize REGULAR EXPRESSIONS. FSAs are defined by state transition table that specifies how the FSA moves from one state to another when presented with a particular input. FSAs can be drawn as GRAPHS.

Fish
A simple object in CONWAY'S GAME OF LIFE that swims vertically or horizontally.

Fitness
A measure of an object's ability to reproduce viable offspring.

Fitness Landscape
A representation of how MUTATIONS can change the FITNESS of one or more organisms. If high fitness corresponds to high locations in the landscapes, and if changes in genetic material are mapped to movements in the landscape, then EVOLUTION will tend to make populations move in a uphill directions on the fitness landscape.

Genetic Algorithm (GA)
A method of SIMULATING the action of EVOLUTION within a computer. A population of fixed-length STRINGS is evolved with a GA by employing CROSSOVER and MUTATION operators along with a FITNESS FUNCTION that determines how likely individuals are to reproduce. Gas perform a type of SEARCH in a FITNESS LANDSCAPE.

Genetic Programming (GP)
A method of applying simulated EVOLUTION on PROGRAMS or program fragments. Modified forms of MUTATION and CROSSOVER are used along with a FITNESS function.

Glider
A simple object in CONWAY'S GAME OF LIFE that swims diagonally through the grid space.

Glider Gun
An object CONWAY'S GAME OF LIFE that builds and emits GLIDERS, which can then be collided in purposeful ways to construct more complicated objects.

Graph
A construct that consists of many nodes connected with edges. The edges usually represents a relationship between the objects represented by the nodes. For example, if the nodes are cities, then the edges may have numerical values that correspond to the distances between the cities. A graph can be equivalently represented as a MATRIX.

Iterated Prisoner's Dilemma
The PRISONER'S DELEMMA game played in an ITERATIVE manner for a number of rounds that is unknown to both players.

Iterate/Iterative
Doing something repeatedly. Doing something repeatedly. Doing something repeatedly. Doing something repeatedly. Doing something repeatedly.

Lamarckism
A method of heredity that does not apply to genetics but is applicable to social ADAPTATION. Lamarckism posits that acquired traits can be passed from parent to offspring.

Learning
A process of ADAPTATION by which a set of adjustable parameters is automatically modified so that some objective is more readily achieved.

Meme
A unit of cultural information that represents a basic idea that can be transferred from one individual to another, and subjected to MUTATION, CROSSOVER, and ADAPTATION.

Model
In the sciences, a model is an estimate of how something works. A model will usually have inputs and outputs that correspond to its real-world counterpart. An ADAPTIVE SYSTEM also contains an implicit model of its ENVIRONMENT that allows it to change its behaviour in anticipation of what will happen in the environment.

Monte Carlo Method
Any technique of statistical sampling employed to approximate solutions to quantitative problems. This technique is not what we mean by "simulation."

Mutation
A RANDOM change in any portion of genetic material. For a GENETIC ALGORITHM, this means that a value in a BIT STRING is randomly set.

Natural Selection
The natural filtering process by which individuals with higher FITNESS are more likely to reproduce than are individuals with lower fitness.

Neural Network (NN)
A network of NEURONS that are connected through SYNAPES or WEIGHTS. In this book, the term is used almost exclusively to denote an artificial neural network and not the real thing. Each neuron performs a simple calculation that is a FUNCTION of the AVTIVATIONS of the neurons that are connected to it. Through FEEDBACK mechanisms and/or the NONLINEAR output response of neurons, the network as a whole is capable of performing extremely complicated tasks, including UNIVERSAL COMPUTATION and UNIVERSAL APPROXIMATION. Three different classes of neural networks are FEEDFORWARD, FEEDBACK, and RECURRENT NEURAL NETWORKS, which differ in the degree and type of CONNECTIVITY that they possess.

Numerical Solution
A solution to a problem that is calculated through a SIMULATION. For example, solving the THREE BODY PROBLEM is not possible in the worst case; however, with the DIFFERENTIAL EQUATIONS that describe the motions of three bodies in space, one could simulate their movements by simulating each time step. Nevertheless, numerical solutions are usually error-prone due to SENSITIVITY and, therefore, can be used to estimate the future for only relatively short time spans, in the worst case.

Prisoner's Dilemma
A NON-ZERO-SUM game in which both players have the incentive not to cooperate independently, no matter what. But collectively they would be better off if they did cooperate. This tension between individual incentive and collective incentive is what makes the PD intriguing.

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 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.

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.

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 system and environment, interesting systems often posses FEEDBACK, which is SELF-REFERENTIAL in the strongest case.

Top-Down
A method of examining things that first looks at higher-level phenomena and then tries to explain lower-level patterns in terms of the higher-level observations. This is the exact opposite of BOTTOM-UP.

Turing Machine
A MODEL OF COMPUTATION that uses an underlying FINITE-STATE AUTOMATON but also has a infinite tape to use as memory. Turing machines are capable of UNIVERSAL COMPUTATION.

Universal Computer
A computer that is capable of UNIVERSAL COMPUTATION, which means that given a description of any other computer or PROGRAM and some data, it can perfectly emulate this second computer or program. Strictly speaking, home PCs amd Macintoshes are not universal computers because they have only a finite amount of memory.