 Computer Explorations of Fractals, Chaos,Complex Systems, and Adaptation · title page · home* · cover artwork · jacket text · table of contents · the author* · ordering information Book Contents
 · three themes · part synopses · selected excerpts · all figures from book · quotes from book · glossary from book · bibliography · slide show Source Code
 · overview &documentation · FAQ list* · download source code · java applets Miscellany
 · news* · reviews & awards · errata · for educators · bibliography (BibTeX format) · other links   Glossary

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# A

Activation     The time-varying value that is the output of a neuron.

Activation Function     A function that translates a neuron's net input to an activation value.

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.

Affine     An equation that can be written in terms of matrix-vector multiplication and vector addition.

AI     An abbreviation for Artificial Intelligence.

Algorithm     A detailed and unambiguous sequence of instructions that describes how a computation is to proceed and can be implemented as a program.

Algorithmic Complexity     The size of the smallest program that can produce a particular sequence of numbers. Regular patterns have low algorithmic complexity and random sequences have high algorithmic complexity.

Always Cooperate     A Prisoner's Dilemma strategy that cooperates with its opponent under all circumstances (the exact opposite of always defect).

Always Defect     A Prisoner's Dilemma strategy that never cooperates with its opponent under any circumstance (the exact opposite of always cooperate).

Analog     Having a continuous value.

Analytical     Can be symbolically represented in a closed form that does not require any of the complex aspects of a program such as an iterative sum.

Analytical Solution     An exact solution to a problem that can be calculated symbolically by manipulating equations (unlike a numerical solution).

Arms Race     Two or more species experience adaptation to one another in a coevolutionary manner. This often seen in predator-prey systems.

Artificial Intelligence     The science of making computers do interesting things that humans do effortlessly.

Artificial Life     The study of life processes within the confines of a computer.

Associative Memory     Memory that can be referenced by content, as opposed to location. Hopfield networks will act as associative memories when trained with the Hebbian learning rule.

Asynchronous     Describes events that occur independently of each other but on a similar time scale.

Attractor     A characterization of the long-term behavior of a dissipative dynamical system. Over long periods of time, the state space of some dynamical systems will contract toward this region. Attractors may be fixed points, periodic, quasiperiodic, or chaotic. They may also be stable or unstable.

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. A boid is an example of an autonomous agent.

Axiom     A statement that is assumed to be true and can later be used along with theorems to prove other theorems. Also, the starting configuration of an L-System.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# B

Backpropagation     An algorithm for efficiently calculating the error gradient of a neural network, which can then be used as the basis of learning. Backpropagation is equivalent to the delta rule for perceptrons, but can also calculate appropriate weight changes for the hidden layer weights of a multilayer perceptron by generalizing the notion of an error correction term. In the simplest case, backpropagation is a type of steepest descent in the search space of the network weights, and it will usually converge to a local minimum.

Basin of Attraction     A region of state space in which all included states of a dynamical system ultimately lead into the attractor.

Bias     See threshold.

Bifurcation     The splitting of a single mode of a system's behavior into two new modes. This usually occurs as a function of a continuously varying control parameter. A cascade of bifurcations will usually precede the onset of chaos.

Binary     Written in a form that uses only 0s and 1s. A string of bits.

Bit     The smallest unit of information; the answer to a yes/no question; the outcome of a coin toss; a 0 or a 1.

Boid     An autonomous agent that behaves like a simplified bird but will display flocking patterns in the presence of other boids.

Boolean     Taking only 0/1, true/false, yes/no values.

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

Brown Noise/Brownian Motion     A form of randomness that is the result of cumulatively adding white noise, to yield a random walk pattern.

Bucket Brigade Algorithm     A learning algorithm that is a method for adjusting the strengths of the classifiers of a classifier system. ``Winning'' classifiers pay a portion of their earnings to other classifiers that assisted them in being activated, similar to an economic system.

Byte     Eight bits. In programming, often used to store a single text character.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# C

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

Chaos/Chaotic     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.

Chomsky Hierarchy     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).

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

Classifier System     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 algorithm.

Coevolution     Two or more entities experience evolution in response to one another. Due to feedback mechanisms, this often results in a biological arms race.

Complement     A set composed of all elements that are not members of another set.

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

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

Complex Number     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).

Complex System     A collection of many simple nonlinear units that operate in parallel and interact locally with each other so as to produce emergent behavior.

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

Compressible     Having a description that is smaller than itself; not random; possessing regularity.

Computable     Expressible as a yes/no question that can be answered in any case by a computer in finite time.

Computation     The realization of a program in a computer.

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

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

Consistence     In formal systems, having the property that all statements are either true or false.

Continuous     Taking a real value, i.e., not discrete. Dynamical systems may operate in continuous time or space.

Control     Exerting actions to manipulate a system or environment in a goal-seeking manner.

Convergence     For computers, halting with an answer; for dynamical systems, falling into an attractor; for searches (e.g., backpropagation and 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 universal computation.

Co-Recursively Enumerable (CO-RE)     The complement of a set that can be recursively enumerated.

Countable Infinity     Having the same number of objects as the set of natural numbers.

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

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# D

Darwinism     The theory of evolution as proposed by Charles Darwin, which combined variation of inheritable traits with natural selection. After the discovery of the physical mechanism of genetics, this was further refined into neo-Darwinism.

Delta Rule     The perceptron learning rule that specifies that weight changes should be proportional to the product of a weight's input and the error (or delta) term for the perceptron.

Derivative     An expression that characterizes how the output of a function changes as the input is varied. Unlike integrals, derivatives can be calculated in an analytical manner very easily.

Decision Problem     A problem in which all questions take the form ``Is something a member of a particular set?'' and all answers are either ``yes'' or ``no.''

Detector     A sensor that translates the state of a classifier's environment into a message that is suitable for posting to the message list of the classifier system.

Determinant     A quantity of a matrix that characterizes the amount of expansion or contraction that the matrix inflicts on a vector when that vector is multiplied by the matrix.

Deterministic     Occurring in a non-random manner such that the next state of a system depends only on prior states of the system or the environment. Perfect knowledge of previous states implies perfect knowledge of the next state.

Diagonal Matrix     A matrix that has 0 entries along all nondiagonal entries, i.e., only the main diagonal may have non-zero values.

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 analytical solution such that all future states can be known without simulation of the time evolution of the system. However, most can have a numerical solution with only limited accuracy.

Differentiation     The act of calculating a derivative; the inverse operation of calculating an integral.

Diffusion Limited Aggregation     A type of stochastic fractal formed by particles floating about in a random manner until they stick to something solid.

Discrete     Taking only non-continuous values, e.g., Boolean or natural numbers.

Dissipative System     A dynamical system that contains internal friction that deforms the structure of its attractor, thus making motion such as fixed points, limit cycles, quasiperiodicity, and chaos possible. Dissipative systems often have internal structure despite being far from equilibrium, like a whirlpool that preserves its basic form despite being in the midst of constant change.

Diverge     For algorithms or computers, to run forever and never halt; for iterative systems (like the equations for the Mandelbrot set), reaching a state such that all future states explode in size.

Dot Product     The inner product of two vectors.

Dynamical System     A system that changes over time according to a set of fixed rules that determine how one state of the system moves to another state.

Dynamics/Dynamical     Pertaining to the change in behavior of a system over time.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# E

Ecology     The study of the relationships and interactions between organisms and environments.

Ecosystem     A biological system consisting of many organisms from different species.

Edge of Chaos     The hypothesis that many natural systems tend toward dynamical behavior that borders static patterns and the chaotic regime.

Effector     The part of a classifier system that can translate messages into actions that can manipulate a system or an environment.

Eigenvalue     The change in length that occurs when the corresponding eigenvector is multiplied by its matrix.

Eigenvector     A unit length vector that retains its direction when multiplied to the matrix that it corresponds to. An (n * n) matrix can have as many as n unique eigenvectors, each of which will have its own eigenvalue.

Embedding     A method of taking a scalar time series and using delayed snapshots of the values at fixed time intervals in the past so that the dynamics of the underlying system can be observed as a function of the previously observed states.

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 behaviors of the ants, and not from any single ant. Usually, the emergent behavior is unanticipated and cannot be directly deduced from the lower-level behaviors. Complex systems are usually emergent.

Entropy     A measure of a system's degree of randomness or disorder.

Environment     If that which is under study is a system, then the rest of the world is the environment.

Equilibrium     A state of a system that, if not subjected to perturbation, will remain unchanged.

Ergodic     The property of a dynamical system such that all regions of a state space are visited with similar frequency and that all regions will be revisited (within a small proximity) if given enough time.

Euclidean     Pertaining to standard geometry, i.e., points, lines, planes, volumes, squares, cubes, triangles, etc.

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.

Evolutionary Stable Strategy (ESS)     In game theory and biology, a strategy that, when possessed by an entire population, results in an equilibrium such that mutation of the strategy can never result in an improvement for an individual. Always Defect is an ESS, while Always Cooperate is not.

Excitatory     Refers to a neural synapse or weight that is positive such that activity in the source neuron encourages activity in the connected neuron; the opposite of inhibitory.

Experimentation     One process by which scientists attempt to understand nature. A phenomenon is observed and/or manipulated so that changes in the phenomenon's state can be seen. The resulting data can be used to derive new models of a process or to confirm an existing model. Experimentation is the complement of theorization. See also simulation.

Expert System     A special program that resembles a collection of ``if ... then'' rules. The rules usually represent knowledge contained by a domain expert (such as a physician adept at diagnosis) and can be used to simulate how a human expert would perform a task.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# F

Feedback     A loop in information flow or in cause and effect.

Feedback Neural Network     A neural network that has every neuron potentially connected to every other neuron. The activations of all neurons are updated in parallel (synchronous or asynchronous order), unlike a feedforward or recurrent neural network.

Feedforward Neural Network     A neural network that is organized with separate layers of neurons. Connections in such a network are limited to one direction such that the activations of the input neurons are updated first, followed by any hidden layers, and then finished with the outputs.

Feigenbaum Constant     A constant number that characterizes when bump-like maps such as the logistic map will bifurcate.

Finite-State Automaton (FSA)     The simplest computing device. Although it is not nearly powerful enough to perform universal computation, it can recognize regular expressions. FSAs are defined by a 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 landscape, and if changes in genetic material are mapped to movements in the landscape, then evolution will tend to make populations move in an uphill direction on the fitness landscape.

Fixed Point     A point in a dynamical system's state space that maps back to itself, i.e., the system will stay at the fixed point if it does not undergo a perturbation.

Formal System     A mathematical formalism in which statements can be constructed and manipulated with logical rules. Some formal systems are built around a few basic axioms (such as Euclidean geometry) and can be expanded with theorems that can be deduced through proofs.

Fractal     An object with a fractal dimension. Fractals are self-similar and may be deterministic or stochastic. See also Cantor Set, Diffusion Limited Aggregation, IFS, Julia Set, L-Systems, MRCM, Mandelbrot Set, and Strange Attractor.

Fractal Dimension     An extension of the notion of dimension found in Euclidean geometry. Fractal dimensions can be non-integer, meaning that objects can be ``more than a line but less than a plane'' and so on. There is more than one way of computing a fractal dimension, one common type being the Hausdorff-Besicovich dimension. Roughly speaking, a fractal dimension can be calculated as the quotient of the logarithm of the object's size and the logarithm of the measuring scale, in the limit as the scale approaches 0. Under this definition, standard Euclidean objects retain their original dimension.

Function     A mapping from one space to another. This is usually understood to be a relationship between numbers. Functions that are computable can be calculated by a universal computer.

Function Approximation     The task of finding an instance from a class of functions that is minimally different from an unknown function. This is a common task for neural networks.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# G

Game Theory     A mathematical formalism used to study human games, economics, military conflicts, and biology. The goal of game theory is to find the optimal strategy for one player to use when his opponent also plays optimally. A strategy may incorporate randomness, in which case it is referred to as a mixed strategy.

Gaussian     Normally distributed (with a bell-shaped curve) and having a mean at the center of the curve with tail widths proportional to the standard deviation of the data about the mean.

Generalized Delta Rule     Another name for backpropagation.

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 in Conway's Game of Life that builds and emits gliders, which can then be collided in purposeful ways to construct more complicated objects.

Global Minimum (Maximum)     In a search space, the lowest (or highest) point of the surface, which usually represents the best possible solution in the space with respect to some problem.

G�del Number     A natural number computed via a G�delization procedure that uniquely corresponds to a string.

G�delization     A method for mapping arbitrary strings to natural numbers such that the process is one-to-one and invertible. The process usually exploits the properties of prime numbers. Since G�delization can be defined as a computable function, and since functions can be G�delized, some functions (or programs) can assert statements about other functions or programs, or themselves.

G�del's Incompleteness Theorem     Any sufficiently interesting formal system can express true statements for which there can be no proof in the original formal system.

G�del's Statement     Given the formal statement ``There does not exist any proof for the statement with G�del number x applied to x,'' which has it own G�del number, g, G�del's statement paraphrased is ``There does not exist a proof of the statement with G�del number g applied to itself.'' G�del's statement is true, but cannot be proven true in the formal system in which it is constructed, which leads to G�del's Incompleteness Theorem.

Gradient     A vector of partial derivatives of a function that operates on vectors. Intuitively, the gradient represents the slope of a high-dimensional surface.

Graph     A construct that consists of many nodes connected with edges. The edges usually represent 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.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# H

Halting Problem     The problem of determining if a program halts or doesn't halt on a particular input. This is an incomputable problem.

Halting Set     The recursively enumerable set of G�del numbers that correspond to programs that halt if given their own G�del number as input.

Hebbian Learning     A rule that specifies that the strength of a synapse between two neurons should be proportional to the product of the activations of the two neurons. cd

H�non Map     A chaotic system (defined by the two equations x(t+1) = a - x(t)^2 + b y(t) and y(t+1) = x(t)) that has a fractal strange attractor and operates in discrete time.

Hidden Layer     In a feedforward or recurrent neural network, a layer of neurons that is neither the input layer nor the output layer but is physically between the two.

Hill-Climbing     One of the simplest search methods that attempts to find a local maximum by moving in an uphill direction. It is related to steepest ascent. Hill-climbing may use gradient information, or random sampling of nearby points, in order to estimate the uphill direction.

Holism     The idea that ``the whole is greater than the sum of the parts.'' Holism is credible on the basis of emergence alone, since reductionism and bottom-up descriptions of nature often fail to predict complex higher-level patterns. See also top-down.

Hopfield Network     A type of feedback neural network that is often used as an associative memory or as a solution to a combinatorial optimization problem.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# I

IFS     An iterated functional system; it constructs a fractal by iterating a vector quantity through an affine equation that is randomly selected on each iteration.

Imaginary Number     The square root of a negative number. The square root of -1 is often denoted as i for the purpose of writing out complex numbers.

Implicit Parallelism     The idea that genetic algorithms have an extra built-in form of parallelism that is expressed when a GA searches through a search space. Implicit parallelism depends on the similarities and differences between individuals in the population. The theory posits that GAs process more schemata than there are strings in a population, thus getting something of a free lunch. See also no free lunch.

Incomputable     Something that cannot be characterized by a program that always halts. Sets that are incomputable may be recursively enumerable (like the halting set), co-recursively enumerable (e.g., the halting set's complement), or not recursively enumerable (which, if also not CO-RE, is a random set).

Incomputable Number     A real number with an infinite decimal (or binary) expansion that cannot be enumerated by any universal computer.

Inheritable     Refers to a trait that can be genetically passed from parent to offspring.

Inhibitory     Refers to a neural synapse or weight that is negative such that activity in the source neuron encourages inactivity in the connected neuron. The opposite of excitatory.

Inner Product     For two vectors of the same dimensionality, the sum of the pairwise products of the two vector components.

Integral     The cumulative continuous sum of a function. The integral of a differential equation represents the future state of a dynamical system; however, most integrals do not have an analytical solution, which means that they may only have numerical solutions, an admittedly inexact process.

Integration     The act of calculating an integral, by either a numerical or an analytical solution; the inverse operation of differentiation.

Invertible     A function is invertible (with a unique inverse) if the output uniquely determines the input (i.e., it is one-to-one) and the set of legal outputs is equal to the set of legal inputs. The function x^2 is not strictly invertible, while x^3 has an inverse. For operations the definition is slightly looser. While integration and differentiation are considered to be inverse operations, there are an infinite number of integrals that are valid results for integrating any function; thus, the process is not one-to-one.

Irrational Number     A real number that cannot be represented as a fraction.

Iterated Prisoner's Dilemma     The Prisoner's Dilemma 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.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# J

Julia Set     A set of complex numbers that do not diverge if iterated an infinite number of times via a simple equation. The points form an extremely complex fractal. There is an uncountable infinity of Julia sets, each of which corresponds to a particular complex number that appears as a constant in the iterative procedure. Julia sets are similar to co-recursively enumerable sets because only points that are not a members of the set can actually be identified as such. All of the Julia sets are related to the Mandelbrot set.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# K

Koch Curve     A fractal curve that looks like the edge of a snowflake. It has no derivative at any point.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# L

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.

Lambda Calculus     A model of computation that is capable of universal computation. The Lisp programming language was inspired by Lambda calculus.

Learning     A process of adaptation by which synapses, weights of neural network's, classifier strengths, or some other set of adjustable parameters is automatically modified so that some objective is more readily achieved. The backpropagation and bucket brigade algorithms are two types of learning procedures.

Limit Cycle     A periodic cycle in a dynamical system such that previous states are returned to repeatedly.

Linear     Having only a multiplicative factor. If f(x) is a linear function, then f(a+b) = f(a) + f(b) and c f(x) = f(cx) must both be true for all values of a, b, c, and x. Most things in nature are nonlinear.

Linearly (In)separable     Two classes of points are linearly separable if a linear function exists such that one class of points resides on one side of the hyperplane (defined by the linear function), and all points in the other class are on the other side. The XOR mapping defines two sets of points that are linearly inseparable.

Lisp     A programming language designed to manipulate lists that was inspired by Lambda Calculus and was the inspiration for Stutter.

Local Minimum (Maximum)     The bottom of a valley or the top of a peak; a point in a search space such that all nearby points are either higher (for a minimum) or lower (for a maximum). In a continuous search space, local minima and maxima have a 0 gradient vector. Note that this particular valley (or peak) may not necessarily be the lowest (or highest) location in the space, which is referred to as the global minimum (maximum).

Logistic Map     The simplest chaotic system that works in discrete time and is defined by the map x(t) = 4r x(t) (1-x(t)). Feigenbaum's constant was first identified for this map.

Lorenz System     A system of three differential equations that was the first concrete example of chaos and a strange attractor.

Lotka-Volterra System     A two-species predator-prey system that in its simplest form can display only fixed points or limit cycles. More complicated versions with three or more species can yield chaos.

L-System     A method of constructing a fractal that is also a model for plant growth. L-systems use an axiom as a starting string and iteratively apply a set of parallel string substitution rules to yield one long string that can be used as instructions for drawing the fractal. One method of interpreting the resulting string is as an instruction to a turtle graphics plotter. Many fractals, including the Cantor set, Koch curve, and Peano curve, can be expressed as an L-system.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# M

Mackey-Glass System     A delay differential equation (dx/dt = (ax(t-tau))/(1 + x^10(t-tau)) - bx(t)) that can display a wide variety of behaviors via an adjustable delay term, tau. Even though this system generates a single scalar time series, it can be extremely chaotic because its value at any time may depend on its entire previous history.

Mandelbrot Set     An extremely complex fractal that is related to Julia sets in the way that it is constructed and by the fact that it acts as a sort of index to the Julia sets. Like the Julia sets, the Mandelbrot set is calculated via an iterative procedure. Starting conditions that do not diverge after an infinite number of iterations are considered to be inside the set. If, and only if, a complex number is in the Mandelbrot set, then the Julia set that uses that complex number as a constant will be connected; otherwise, the corresponding Julia set will be unconnected.

Map     A function that is usually understood to be iterated in discrete time steps.

Matrix     A rectangular two-dimensional array of numbers that can be thought of as a linear operator on vectors. Matrix-vector multiplication can be used to describe geometric transformations such as scaling, rotation, reflection, and translation. They can also describe the affine transformation used to construct IFS and MRCM fractals.

Mean     The arithmetical average of a collection of numbers; the center of a Gaussian distribution.

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.

Message     The basic unit of information in a classifier system that is stored in the message list. A message may correspond to an external state of an environment or an internal state of the classifier system.

Message List     The portion of a classifier system that retains information in the form of messages.

Mixed Strategy     In game theory, a strategy that uses randomness by employing different actions in identical circumstances with different probabilities.

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 behavior in anticipation of what will happen in the environment.

Model of Computation     An idealized version of a computing device that usually has some simplifications such as infinite memory. A Turing machine, the lambda calculus, and Post production systems are all models of computation.

Monotonic     The property of a function that is always strictly increasing or strictly decreasing, but never both. The sigmoidal activation function of a multilayer perceptron is monotonically increasing.

MRCM     The Multiple Reduction Copy Machine algorithm, which can be used to make affine fractals. MRCM fractals are related to IFS fractals in that they both use the same types of affine transformations. The MRCM algorithm performs several affine transformations of a seed image in parallel to yield a secondary seed image. The output of the MRCM is recursively passed back through to its input multiple times, to yield the fractal.

Multilayer Perceptron (MLP)     A type of feedforward neural network that is an extension of the perceptron in that it has at least one hidden layer of neurons. Layers are updated by starting at the inputs and ending with the outputs. Each neuron computes a weighted sum of the incoming signals, to yield a net input, and passes this value through its sigmoidal activation function to yield the neuron's activation value. Unlike the perceptron, an MLP can solve linearly inseparable problems.

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.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# N

Nash Equilibrium     In game theory, a pair of strategies for a game such that neither player can improve his outcome by changing his strategy. A Nash equilibrium sometimes takes the form of a saddle structure. Under some cases, when a strategy is at a Nash equilibrium with itself, the strategy resembles an evolutionary stable strategy.

Natural Number     Any of the standard counting numbers; a positive integer.

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

Neo-Darwinism     A synthesis of Darwinism with the mechanisms of genetics; the idea that adaptation equals a combination of variation, heredity, and selection. See also evolution, inheritable, and natural selection.

Net Input     The weighted sum of incoming signals into a neuron plus a neuron's threshold value.

Neural Network (NN)     A network of neurons that are connected through synapses 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 activations 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.

Neuron     A simple computational unit that performs a weighted sum on incoming signals, adds a threshold or bias term to this value to yield a net input, and maps this last value through an activation function to compute its own activation. Some neurons, such as those found in feedback or Hopfield networks, will retain a portion of their previous activation.

Newton's Method     An iterative method for finding 0 values of a function.

Niche     A way for an animal to make a living in an ecosystem.

No Free Lunch (NFL)     A theorem that states that in the worst case, and averaged over an infinite number of search spaces, all search methods perform equally well. More than being a condemnation of any search method, the NFL theorem actually hints that most naturally occurring search spaces are, in fact, not random.

Nonlinear     A function that is not linear. Most things in nature are nonlinear. This means that in a very real way, the whole is at least different from the sum of the parts. See also holism.

Not Recursively Enumerable (not-RE)     An infinite set that cannot be recursively enumerated. Sets of this type that are also not co-recursively enumerable are effectively random.

NP     Nondeterministic polynomial time problems; a class of computational problems that may or may not be solvable in polynomial time but are expressed in such a way that candidate solutions can be tested for correctness in polynomial time. See also time complexity and NP-Complete.

NP-Complete     A problem type in which any instance of any other NP class problem can be translated to in polynomial time. This means that if a fast algorithm exists for an NP-complete problem, then any problem that is in NP can be solved with the same algorithm.

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.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# O

Occam's Razor     The principle that when faced with multiple but equivalent interpretations of some phenomenon, one should always choose the simplest explanation that correctly fits the data. Occam's Razor is useful for selecting competing models for some phenomena.

One-to-One     A function or map that for every possible output has only one input that yields that particular output; if f(a) = f(b), then a = b.

Optimization     The process of finding parameters that minimizes or maximizes a function.

Outer Product     An operation on two vectors that yields a matrix. Given two vectors with the same dimensionality, the outer product is a square symmetric matrix that contains the product of all pairs of elements from the two vectors, i.e., A[i,j] = x[i] y[j].

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# P

Parallel/Parallelism     Many things happening at once.

Pattern Classification     A task that neural networks are often trained to do. Given some input pattern, the task is to make an accurate class assignment to the input. For example, classifying many images of letters to one of the twenty-six letters of the alphabet is a pattern classification task.

Payoff     In game theory, the amount that a player wins, given the player's and his opponent's actions.

Peano Curve     A fractal space-filling curve that can fill a plane even though it is a line of infinite length. Oddly enough, it has an integer fractal dimension of 2.

Perceptron     The simplest type of feedforward neural network. It has only inputs and outputs, i.e., no hidden layers.

Periodic     Refers to motion that goes through a finite number of regions, returns to a previous state, and repeats the same fixed pattern forever.

Perturbation     A slight nudge.

Phase Space     In this book, another name for state space. In the scientific literature, ``phase space'' is used to denote the space of motion in a dynamical system that moves in continuous time, while state space is often used for discrete time systems.

Phase Transition     In physics, a change from one state of matter to another. In dynamical systems theory, a change from one mode of behavior to another.

Planning     In computer science, and particularly in artificial intelligence, the task of determining a stepwise plan to accomplish a very specific task.

Polynomial     A function in which the output is the sum of terms that are the products of constant values and the input raised to some integer power. The polynomial of a polynomial is another polynomial. From a time complexity point of view, polynomials are well-behaved.

Post Production System     A model of computation that resembles a collection of ``if ... then'' rules and is capable of universal computation.

Predator-Prey System     An ecosystem in which one portion of the population consumes another. With three or more species, simple predator-prey interactions can lead to chaos and biological arms races. See also Lotka-Volterra system.

Prime Number     A natural number that can be evenly divided only by itself and 1.

Prisoner's Dilemma     A non-zero-sum game in which both players have incentive not to cooperate under any circumstances. Thus, the optimal game theory strategy of always defect has the paradoxical property that both players would have a higher payoff if they ignored the advice of game theory.

Probability     The likelihood that a random event will occur.

Program     An algorithm that is written in a programming language for execution on a physical computer.

Proof     A sequence of statements in which each subsequent statement is derivable from one of the previous statements or from an axiom of a formal system. The final statement of a proof is usually the theorem that one has set out to prove.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# Q

Quasiperiodic     Refers to a form of motion that is regular but never exactly repeating. Quasiperiodic motion is always composed of multiple but simpler periodic motions. In the general case, for motion that is the sum of simpler periodic motions, if there exists a length of time that evenly divides the frequencies of the underlying motions, then the composite motion will also be periodic; however, if no such length of time exists, then the motion will be quasiperiodic.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# R

Random/Randomness     Without cause; not compressible; obeying the statistics of a fair coin toss.

Random Walk     A walk in one or more dimensions that is dictated by the outcome of a coin toss. The direction of each step of the walk is specified by the coin toss. The resulting random motion is often referred to as Brownian motion.

Rational Number     A number that can be expressed as a fraction.

Real Number     Any number that can be represented with a potentially infinite decimal expansion to the right of the decimal point. Natural, rational, irrational, and incomputable numbers are all real numbers.

Recurrent Neural Network     A network similar to a feedforward neural network except that there may be connections from an output or hidden layer to the inputs. Recurrent neural networks are capable of universal computation.

Recursive     Strictly speaking, a set or function is recursive if it is computable; however, in the usual sense of the word, a function is said to be recursive if its definition make reference to itself. For example, factorial can be defined as x! = x * (x - 1)! with the base case of 1! equal to 1. See also self-referential.

Recursively Enumerable (RE)     A potentially infinite set whose members can be enumerated by a universal computer; however, a universal computer may not be able to determine that something is not a member of a recursively enumerable set. The halting set is recursively enumerable but not recursive.

Reductionism     The idea that nature can be understood by dissection. In other words, knowing the lowest-level details of how things work (at, say, the level of subatomic physics) reveals how higher-level phenomena come about. This is a bottom-up way of looking at the universe, and is the exact opposite of holism.

Regular Expression     A definition for a class of strings that can be recognized by a finite-state automaton. An example of a class of strings that is regular would be legal mathematical expressions using only ``+'' and digits. An example that is not regular is the same legal mathematical expressions as before, but with properly nested parentheses.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# S

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.

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.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# T

Theorem     A statement in a formal system that has proof.

Theorization     A process by which scientists attempt to understand nature; it is the complement to experimentation. Theorization is the process of building mathematical models for how things work. Scientists always desire theories that are simpler than the data they explain. See also Occam's Razor and simulation.

Three Body Problem     The problem of determining the future positions and velocities of three gravitational bodies. The problem was proved unsolvable in the general case by Henri Poincar�, which forshadowed the importance of chaos. Although no analytical solutions are possible in the worst case, a numerical solution is sometimes sufficient for many tasks.

Threshold     A quantity added to (or subtracted from) the weighted sum of inputs into a neuron, which forms the neuron's net input. Intuitively, the net input (or bias) is proportional to the amount that the incoming neural activations must exceed in order for a neuron to fire.

Time Complexity     A function that describes the amount of time 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 space complexity.

Time-Reversible     A property of dynamical systems that can be run unambiguously both forward and backward in time. The H�non map, Lorenz system, and vant cellular automata are all time-reversible, while the logistic map, the Mackey-Glass system, and most other cellular automata are not. Time-reversible systems are described by functions that are invertible.

Time Series     A sequence of values generated from a dynamical system over time. Chaotic systems can be analyzed by examining the time series generated by a single portion of the system. See also embedding.

Tit-for-Tat     An effective strategy for playing the Iterated Prisoner's Dilemma. Tit-for-Tat starts by cooperating, and then does whatever its opponent did in the previous round of play.

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. See also holism and reductionism.

Transpose     An operation that flips a matrix about the main diagonal.

Turing Machine     A model of computation that uses an underlying finite-state automaton but also has an infinite tape to use as memory. Turing machines are capable of universal computation.

Turtle Graphics     A simple language for drawing graphics in which a ``turtle'' is used to make strokes on a plotting device. Typical commands include ``move forward,'' ``draw forward,'' and ``turn left.''

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# U

Uncountable Infinity     An order of infinity that is larger than the number of natural numbers. The number of real numbers is uncountably infinite.

Universal Approximation     Having the ability to approximate any function to an arbitrary degree of accuracy. Neural networks are universal approximators.

Universal Computation     Capable of computing anything that can in principle be computed; being equivalent in computing power to a Turing machine, the lambda calculus, or a Post production system.

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 are not universal computers because they have only a finite amount of memory. However, in practice, this is usually ignored.

Unstable     Having a basin of attraction that is 0 in size; being such that the slightest perturbation will forever change the state of a system. A pencil balanced on its point is unstable.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# V

Value Function     A built-in function in Lisp or Stutter that evaluates all of its arguments prior to being executed, e.g., car, cdr, and cons.

Vant     A virtual ant; a type of cellular automaton that vaguely emulates the activity of one or more ants.

Variation     Genetic differences among individuals in a population.

Vector     A one-dimensional array of numbers that can be used to represent a point in a multidimensional space.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# W

Weight     In a neural network, the strength of a synapse (or connection) between two neurons. Weights may be positive (excitatory) or negative (inhibitory). The thresholds of a neuron are also considered weights, since they undergo adaptation by a learning algorithm.

White Noise     Noise that uniformly distributed in the frequency domain; randomness that is uniformly distributed; thus, a white noise process with a range of 0 to 1 would yield a random number in this range with probability equal for all possible values. Brown noise is a result of cumulatively adding white noise.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# X

XOR     The exclusive-or function; given two Boolean inputs, the output of XOR is 1 if and only if the two inputs are different; otherwise, the output is 0.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ]

# Z

Zero-Sum Game     In game theory, a game in which a win for one player results in an equal but opposite loss for the other players.

 [ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z ] Copyright © Gary William Flake, 1998-2002. All Rights Reserved. Last modified: 30 Nov 2002