Complexity Glossary

Adaptation Any change in the structure or function of an organism that allows it to survive and reproduce more effectively in its environment.

Afferent Conducting information inward; said of fibers in the nervous system that bring messages to the brain, and of the transfer of signals toward an individual neuron. Opposite of efferent.

Algorithm A procedure or series of steps that can be used to solve a computable problem. In computer science, it describes the logical sequence of operations to be carried out by a software program. Not all mathematical problems have corn putable solutions.

Algorithmic complexity A measure of the complexity of a problem given by the size of the smallest program that computes it or a complete description of it. Simpler things require smaller programs.

Amino acids The molecular building blocks of proteins.

Animats Artificial animals comprised of software and hardware.

Arithmetic A branch of mathematics concerned with the study of numbers and their properties.

Artificial intelligence A branch of computer science whose goal is the design of machines that have attributes associated with human intelligence, such as learnmg, reasoning, vision, understanding speech, and, ultimately, consciousness.

Artificial life A field of study that aims to discover the essential nature and universal features of "life": not only life as we currently know it, but life as it could be,whether on earth, within computers, or elsewhere, and in whatever shape or form that it may be found or made within our universe.

Artificial neural network A kind of computer model, loosely inspired by the neural network structure of the brain, and consisting of interconnected processing units that send signals to one another and turn on or off depending on the sum of their incoming signals. Artificial neural networks may be composed of either computer software or hardware or both.

Assembly language A language that is usually the lowest level available on a computer and, in its simplest form, bears a one-to-one relationship to the machine code that issues instructions directly to a microprocessor, but has additional facilities. It is converted into machine code by means of an assembler program.

Association The ability to relate different pieces of information. An associative memory is one that, given only partially complete input, can associate the corresponding complete set of stored data. Artificial neural networks display this property.

Attractor A way to describe the long-term behavior of a system. Equilibrium and steady states correspond to fixed point attractors, periodic states to limit-cycle attractors and chaotic states to strange attractors.

Autocatalysis Catalysis of a reaction by one of its own products.

Automata theory The mathematical study of machines and their capabilities for solving problems by means of algorithms.

Axon The long fiber extending from a neuron that carries a signal to other neurons. Belousov-Zhabotinski reaction A chemical reaction named after two Russian scientists that displays a remarkable wealth of self-organizing features.

Bifurcation A branch, when there are two distinct choices available to a system. In the case of a chemical-clock reaction, a biflircation can mark the concentration of a reactant beyond which the periodic color changes of the chemical clock occur.

Binary classifier Of genetic algorithms, when a solution to a classification problem is expressed as a binary string of information. Each bit corresponds to the presence (1) or absence (0) of a particular property in the same way that a chromosome contains genes corresponding to the presence of a protein in the body.

Binary logic A system in which variables can adopt one of only two different values, usually taken to be zero or unity.

Bit Contraction of "binary digit." A bit is the smallest unit of information in a binary number system. The value of a bit is usually referred to as a one or zero.

Brusselator A simplified theoretical model of a chemical reaction showing selforganizing features-like regular color changes in time.

Byte A group of binary digits eight bits long, which forms the basic unit of computer memory.

Catalyst A substance able to accelerate a chemical reaction, yet left chemically unchanged by the process.

Capacitor A device for storing an electrical charge.

Cell A discrete, membrane-bound portion of living matter; the smallest unit capable of an independent existence.

Cellular automaton A computer program or piece of hardware consisting of a regular lattice or array of cells. Each cell is assigned a set of instructions by means of an algorithm that tells it how to respond to the behavior of adjacent cell as the automaton advances from one discrete time step to the next. Cellular automata are inherently parallel computing devices.

Central processing unit (CPU) The main component of a computer that performs the actual execution of instructions.

Cerebral cortex The outer layer (grey matter) of the cerebral hemispheres, evolution's most recent addition to the nervous system.

Chaos The term used to describe unpredictable and apparently random behavior in dynamical systems.

Chromosome A long strand of nucleic acid, usually DNA, containing thousands of genes, in a protective package. There are twenty-three pairs in all human cells, except eggs and sperm.

Cognitive science The study of intelligence, embracing various academic disciplines: linguistics, experimental psychology, computer science, philosophy, neuroscience.

Compiler A computer program that translates a set of instructions written in a high-level language such as Fortran into a form (machine code) that can be understood directly by the computer.

Complexity The study of the behavior of macroscopic collections of simple units (e.g., atoms, molecules, bits, neurons) that are endowed with the potential to evolve in time.

Computability In mathematics, the property of being calculable on the basis of an algorithm, and hence by a computer (or universal Turing machine). The natural numbers underpinning mathematics comprise two groups, the computable and the noncomputable numbers; there are infinitely many more noncomputable than computable numbers.

Computable numbers A number that can be computed by an individual Turing machine.

Computation A calculation (usually of numbers) performed by means of an algorithm.

Computer A device that operates on data (input) according to specified instructions (program), usually contained within the computer and which produces results as output. In a digital computer, all tasks are carried out by numbers encoded as binary signals-such as ones and zeros-in contrast to an analog machine which operates using continuously variable signals.

Concentration gradient Change in the concentration of a substance from one area to another.

Connectionism Another narne for the study of artificial neural networks, derived from the myriad connections between processing elements in a network.

Content addressable memory Capability of recalling an item from a memory using only incomplete aspects of the memorized item, rather than using an explicit address for accessing.

Cost function In complex optimization problems, it measures how good any particular solution is-the lower (or higher) the value of this function, the better the solution. Also called a "fitness" function.

Determinism The doctrine that events are completely determined by previous causes rather than being affected by free will or random factors.

Differential equations Equations involving the instantaneous rate of change of certain quantities with respect to others. Newton's equations of motion, for example, are differential equations linking the force experienced by a body to the instantaneous rate of change of its velocity with time.

Dissipative structure An organized state of matter arising beyond the first bifurcation point when a system is maintained far from thermodynamic equilibrium.

DNA (deoxyribonucleic acid) A very large nucleic acid molecule carrying the generic blueprint for the design and assembly of proteins, the basic building blocks of life.

Dopamine A neurotransmitter that transmits impulses between neurons within the brain.

Dynamical systems General term for systems whose properties change with time.

Efferent Of neurons, conducting signals away from a given cell.

Emergent property A global property of a complex system that consists of n'any interacting subunits. For example, consciousness is an emergent property of the many neurons in a human brain.

Entropy A quantity that determines a system's capacity to evolve irreversibly in time. Loosely speaking, we may also think of entropy as measuring the degree of randomness or disorder in a system.

Enzyme A biological catalyst, usually composed of a large protein molecule which accelerates essential chemical reactions in living cells.

Epilepsy A disorder of brain function characterized by sporadic recurrence of seizure caused by avalance discharges of large numbers of neurons.

Equilibrium In thermodynamics, the final state of time evolution at which all capacity for change is spent. Equilibrium thermodynamics is concerned exclusively with the properties of such static states.

Eugenics (Greek, "well born") The study of ways in which the physical and mental quality' of a people can be controlled and improved by selective breeding.

Evolution General term for the unfolding of behavior with the passage of time. In biology, the Darwinian theory according to which higher forms of life have arisen out of lower forms with the passage of time.

Evolutionarily stable strategy An assemblage of behavioral or physical characters (collectively, a game theoretic strategy) of a population that is resistant to replacement by any forms bearing new traits, because the new traits will not be capable of successful reproduction.

Excitable medium A medium-such as the soup of chemicals in the Belousov-Zhabotinski reaction-that changes its state when subjected to a stimulus exceeding a certain threshold level. After excitation, such a medium becomes refractory; that is, it is unresponsive to further stimuli for a period of time.

Expert system Computer program that uses a direct encoding of human knowledge to help solve complex problems, such as diagnosing an illness or interpreting the law. Also called a knowledge-based system.

Feature detector A group of neurons that becomes active only if a particular feature is present in the sensory input.

Feedback A general term for the mechanism whereby the consequences of an ongoing process become factors in modifying or changing that process. The original process is reinforced in positive feedback and suppressed in negative feedback.

Feedforward networks Networks whose architectures are such that the neurons can be divided into layers, with the neural activities in one layer only being able to influence the activity in later (not earlier) layers. Also called multilayer perceptrons.

Ferromagnetic material Material that acquires strong magnetism when placed in an external magnetic field. Examples are iron, cobalt, nickel, and their alloys.

Fitness landscape A landscape representing the fitness measure or cost function of a problem, such as that in the traveling salesmen problem, spin glasses, or the reproductive capability of a real or virtual organism.

Flop A floating point operation in a computer-that is, an operation that can be applied to floating point numbers wh6se decimal points can be in any position. A computer's numerical processing power can be measured in flops-the number of floating point operations it can carry out per second.

Fluid mechanics The study of the macroscopic behavior of flowing fluids (liquids and gases).

Formalism A philosophical doctrine espoused by the German mathematician David Hilbert according to which the symbols contained in mathematical statements possess a structure with useful applications. Should be compared with intuitionism, logicism, and Platonism.

Fractal geometry From Latin fracius, "broken." The geometry used to describe an irregular pattern. Fractals display the characteristic of self-similarity, an unending series of motifs within motifs repeated at all length scales.

Frustration A term used in the physics of spin glasses and also applied to interactions in some types of neural networks, indicating the tendency for conflicting demands to be placed on spin or neuronal interactions. In the former case, this arises due to the existence of both ferromagnetic and antiferromagnetic interactions between spins; in the latter, owing to excitatory and inhibitory inputs experienced by neurons.

Fuzzy logic In mathematics and computing, a form of knowledge representation suitable for intrinsically imprecise notions such as "hot" and "cold," or "good" and "bad," which may depend on their context.

Gaia hypothesis The proposal that the earth's living and nonliving components form an inseparable whole that is regulated and kept adapted for life by complex feedback processes.

Game theory A branch of mathematics that deals with strategic problems such as those that arise in business, commerce, evolution, and warfare, by assuming that the contestants involved invariably try to maximize personal gain.

Gene A unit of heredity composed of the DNA molecule, responsible for passing on specific characteristics from parents to offspring.

Genetic algorithm An adaptive computational method that seeks good solutions to complex (typically NP hard problems using ideas based on Darwinian evolution).

Genetic code The sequence of chemical building blocks of DNA (bases) that spells out the instructions for making amino acids.

Genotype The genetic constitution of an individual.

Geological time The time scale embracing the history of the earth, from its physical origin to the present day.

Geometry The branch of mathematics concerned with the properties of space.

Giga Prefix signifying multiplication by 1,000,000,000.

Glucose A sugar present in blood that is the source of energy for the body.

Gödel's theorem One of the most important theorems in mathematical logic, which states that it is impossible to reduce mathematics to a finite set of axioms and rules.

GOFAI Good Old-Fashioned Artificial Intelligence, a top-down approach that tries to compartmentalize intelligence into discrete "modules" dealing with specific types of knowledge and information, such as perception, planning, and execuring actions. Each of these modules is equipped with explicit models of the external world, and they are supposed to interact by means of logical rules within an inference engine" to produce intelligent behavior. Expert systems are a product of the GOFAI philosophy.

Ground state The state of lowest energy in a system.

Halting problem The result, found by Alan Turing, that it is impossible to devise a mechanical procedure, or algorithm, that can decide whether an arbitrary computer program will halt after a finite number of steps. The reason is due to the existence of uncomputable numbers, and can ultimately be traced back to Gödel's theorem .

Hardware The physical parts of a computer system, usually consisting of mechanical, electronic, and optical components.

Hebbian learning rule A rule according to which a synaptic connection is strengthened whenever the two neurons involved fire simultaneously. Used in both biological and artificial neural networks.

Hemisphere One side, left or right, of the cerebral cortex.

High-level language In computing, a programming language designed to suit the needs of the programmer: it is independent of the internal machine code of any particular computer.

Homunculus The "little inner man" conjectured by the ancients to reside in the head, to observe the environment via the senses, and to respond appropriately. The so-called Cartesian theater of the mind would be played out before him.

Hydrodynamics The science of macroscopic fluid behavior, synonymous with fluid mechanics.

Hypercycle Proposed scenario for the origin of self-replicating molecular systems. These template-instructed replicating cycles involve catalytic feedback loops wherein molecule A begets molecule B which begets molecule C which begets molecule A and so on.

Integrated circuit The "silicon chip," a small piece of semiconductor material such as silicon that is fabricated so that it contains a complete electronic circuit.

Intractable A problem so computationally demanding that the time required to solve it is prohibitively long. Such problems, which are not solvable in polynomial time, are said to be in the class NP,

Intuitionism The philosophical doctrine that mathematics cannot deal with the properties of most infinite sets, and that only those statements that can be proved by finite methods can be justifiably asserted.

Irrational number A number that cannot be expressed as an exact fraction. One example is pi. Most irrational numbers are also uncomputable.

Irreversibility The one-way time evolution of a real system, giving rise to an arrow of time.

Iteration A method of solving a problem by performing the same steps repeatedly until a certain condition is satisfied.

Life Said of a system capable of undergoing Darwinian style evolution by natural selection.

Limit cycle attractor An attractor describing regular (periodic or quasi-periodic) temporal behavior, for instance, in a chemical clock undergoing regular color changes.

Linear equation A relationship between two variables that, when plotted on Cartesian axes, produces a straight-line graph.

Logic gate One of the basic logical components used in an electronic device. For example, the output of an AND gate will only be "true" if all its inputs are "true" and the output of an OR gate will be "true" if any of its inputs are "true."

Logicism The doctrine that all mathematics can be deduced from logic. Frege's attempt to achieve this was brought down by Russell's paradox, leading to the rise of formalism and intuitionism.

Machine code The sequence of binary patterns that is executed by the hardware of a computer; the set of instructions that a computer's central processing unit can understand and obey directly, without any translation.

Mainframe A now old-fashioned term for a large computer used for heavy duty processing. Because of the exponential increase in computing power over recent years, most mainframes are less powerful than today's desktop computers and workstations.

Measurement problem In quantum theory, the problem of accounting for the outcome of experimental measurements on microscopic systems.

Mega Prefix denoting multiplication by a million.

Memory In computer science, the space within a computer where information is stored while being actively processed.

Microscopic A term used to describe tiny dimensions, compared with the everyday or macroscopic dimensions of the world that can be directly perceived with the senses. The distinctions come into their own when contrasting a description of the world couched in terms of individual atoms and molecules with one that relies on global properties of vast numbers of atoms and molecules.

Microtubule Tiny hollow tube made of the tubulin protein found in almost all cells with a nucleus. Microtubules help to define the shape of a cell by forming a scaffolding that is part of the cytoskeleton.

MIPS Acronym for million instructions per second. One measure of the speed of a computer processor.

Molecular biology The study of the molecular basis of life, including the biochemistry of molecules such as DNA and RNA.

Morphogenesis The evolution of form in living things.

Mutation A change in genes produced by a chance or deliberate change in the DNA that makes up the hereditary material of an organism.

Nanotechnology The building of devices on a molecular scale.

Natural selection The process whereby gene frequencies in a population change through certain individuals producing more descendants than others because they are better able to survive and reproduce in their environment. The accumulated effect of natural selection is to produce adaptations. Can be used also for certain artificial systems.

Neural network The brain's actual interconnected mesh of neurons.

Neuron The nerve cell that is the flindamental signaling unit of the nervous system.

Neurotransmitter A molecule that diffuses across a synapse and thus transmits signals between nerve cells.

Nonequilibrium The state of a macroscopic system that has not attained thermodynamic equilibrium and thus still has the capacity to change with time.

Nonlinear The mathematical property of combining in a more complicated way than simple addition. Nonlinear behavior is typical of the real world and means in a qualitative sense "getting more than you bargained for" unlike linear systems, which produce no surprises. For example, dissipative nonlinear systems are capable of exhibiting self-organization and chaos.

NP-complete The hardest of all NP problems.

NP problem A problem whose solution requires a time that depends exponentially on its size (something to the power of N, where N represents the size of the problem). These problems are called intractable because the time required to solve them rapidly becomes unbounded as the size of the problem grows. Even the raw power of a computer has little effect. These problems, which are not solvable in polynomial time, are said to be in the class NP.

Nucleic acid Complex organic acid made up of a long chain of units called nucleotides. The two types, known as DNA and RNA, form the basis of hcrcdity.

Number theory The abstract study of the structure of number systems and the properties of positive integers (whole numbers).

Optimization The refinement process used to find the best solution to a problem. To solve an optimization problem computational ly, one writes a program in such a way as to maximize or minimize the value of a cost function.

Optoelectronics Branch of electronics concerned with the development of devices that respond not only to electrons but also photons.

Organic chemistry Branch of chemistry that deals with carbon-containing compounds.

Parallelism Leading-edge computer technique that allows more than one computation at the same time by using several different processing units running concurrently. The most extreme form is massive parallelism, in which thousands of individual processors work in unison on different parts of a single giant problem. Concurrent processing (time sharing) is achieved on serial machines by making the single CPU switch between several tasks.

Perceptron A simple computational model of a biological neuron comprising some input channels, a processing element, and a single output. Each input value is multiplied by a channel weight, summed by the processor, passed through a nonlinear filter and put into the output channel.

Phase change A change in the physical state of a substance from solid to liquid, liquid to gas, or solid to gas.

Phenotype The overall attributes of an organism arising due to the interaction of its genotype with the environment.

Pixel Acronym for a picture element, a single dot on a computer screen (the three-dimensional equivalent is called a voxel).

Platonism A philosophical doctrine according to which mathematical objects exist in advance of and independently of our knowledge of them and of any physical instantiation of them, and that our insight into mathematical truth is achieved by the construction of proofs. Should be compared with logicism, intuitionism, and formalism.

Polymer A chemical substance formed by the chain-like linkage of simpler molecules. Postsynaptic Pertaining to the receiving side of a synapse; by contrast, the presynaptic pertains to the transmitting side of the synapse.

Program The set of instructions that implements an algorithm that can be understood by a computer.

Protein A class of large molecules found in living organisms, consisting of strings of amino acids folded into complex but well-defined three-dimensional structures.

Punctuated equilibrium Evolutionary theory developed to explain discontinuities in the fossil record.

Quantum computer A hitherto theoretical device that could compute various things that are uncomputable using a universal Turing machine.

Quantum mechanics The mechanics that rules the microscopic world, when energy changes occur in abrupt, tiny quantum jumps

RAM Acronym for Random Access Memory. A memory device used in almost all modern computers.

Random number One of a series of numbers having no detectable pattern. No universal Turing machine (i.e., computer) can generate truly random numbers, since these are uncomputable; though a universal quantum computer should in principle be able to achieve this.

Rational number Any number that can be expressed as an exact fraction, and is therefore computable

Reaction In chemistry, the coming together of atoms or molecules with the result that a chemical change takes place.

Real number Any of the rational or irrational numbers.

Reductionism A doctrine according to which complex phenomena can be explained in terms of something simpler. In particular, atomistic reductionism contends that macroscopic phenomena can be explained in terms of the properties of atoms and molecules.

Reynolds number A number used in fluid mechanics that indicates whether a fluid flow in a particular situation will be smooth or turbulent.

RISC Acronym for Reduced Instruction Set Computer. A microprocessor that carries out fewer instructions than traditional microprocessors so that it can work more quickly.

RNA (ribonucleic acid) The genetic material used to translate DNA into proteins. In some organisms, it can also be the principal genetic material.

ROM Acronym for Read Only Memory. Unlike RAM, ROM chips can only be read and not written to.

Scalar A quantity with magnitude but no direction. Examples include mass and temperature.

Scanning tunneling microscope A microscope that produces a magnified image by moving a tiny tungsten probe across a specimen. By the magnitude of the flow of charge between tip and specimen, the contours of the surface can be determined.

Search space The variation in a cost function is best envisaged as a landscape of potential solutions where the height of each feature is a measure of its cost. This undulating landscape is sometimes called the search space.

Self-organization The spontaneous emergence of nonequilibrium structural organization on a macroscopic level due to collective interactions between a large number of simple, usually microscopic, objects.

Self-organized criticality A generic pattern of self-organized nonequilibrium behavior in which there are characteristic long-range temporal and spatial regularities.

Simulated annealing A method for searching a landscape of possibilities for the best solution to a complex problem, as expressed by the lowest (or highest) point on that landscape. The name comes from the process of annealing, during which a material is first heated and then slowly cooled to enhance ductility and strength. During annealing, the component atoms of the metal are allowed to settle into a lower energy, more stable arrangement than prior to the process.

Software The programs executed by a computer system, as distinct from the hardware.

Soma The main body of a neuron. Computationally, it acts approximately like a linear threshold filter.

Speech recognition Any technique by which a computer can understand ordinary speech.

Spin glass Magnetic material (typically an alloy) whose atomic magnets are involved in a mixture of 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 many stable states, and finding the global ground state is an NP-hard optimization problem. Spin glasses share many properties in common with associative Hopfield networks.

Statistical mechanics The discipline that attempts to relate the properties of macroscopic systems to their atomic and molecular constituents.

Steady state A nonequilibrium state that does not change with time.

Strange attractor An attractor that has a fractal (fractional) dimension: describes chaotic dynamics in dissipative dynamical systems.

Supercomputer The fastest, largest, and most powerful type of computer.

Synapse The junction between two nerve cells across which a nerve impulse is transmitted.

Teleology The study (or doctrine) of final causes, particularly in relation to design or purpose in nature.

Tera A prefix indicating one million million.

Thermodynamics The science of heat and work.

Transistor A solid-state electronic component made of a semiconductor with three or more electrodes that can r'egulate a current passing through it. Used as an amplifier, oscillator, or switch.

Turing machine In modern terminology, a computer program.

Uncertainty principle The quantum mechanical principle that says it is meaningless to speak of a particle's position, momentum, or other parameters, except as the result of measurements. It gives a theoretical limit to the precision with which a particle's momentum and position can be measured simultaneously: the more accurately one is determined, the more uncertainty there is in another.

Uncomputable number A number that cannot be computed by any Turing machine, including the universal one.

Universal Turing Machine In modern terminology, a general-purpose programmable computer, which can perform any computable sequence of operations.

Vector Any quantity with a magnitude and a direction. Examples are velocity and acceleration.

Virtual reality Advanced form of three-dimensional computer graphical simulation in which a participant is plunged into an artificial multimedia environment.

Virus A short stretch of computer code that can copy itself into one or more larger "host" computer programs when it is activated. In biology, a virus is a scrap of genetic material, usually wrapped in a protein overcoat, that needs a host cell to reproduce, and which can also evolve.

Wave function The central quantity in quantum theory that is used to calculate the probability of an event occurring-for instance, an atom emitting a photon-when a measurement is made.





Related Articles

Logic

Ordinary Miracles Complexity Theory

Everyone's a Winner Quantum Theory

Lifes Patterns

The Science of Complexity

The Spirit of Complexity

Fuzzy Logic

The Raven Paradox

The Prosecutor's Fallacy

Bayesian Probability

Bayes Theorem

Falsifiability

Boolean Algebra

Occam's Razor

Church's Lambda Calculus

Gödel's Incompleteness Theorem

Kolmogorov Complexity

A Random Walk in Arithmetic by Greg Chaitin

Rationally Speaking Massimo Pigliucci's page

Random Reality by Greg Chaitin