author : David Meltzer

Some papers abbreviated and compressed to the point of incomprehensibility for anyone not present at the workshop, or conversant with the previous seven? years developments

Discussions after the talks are also reported in detail

The parts are: Fundamental Concepts; Examples of Complex Adaptive Systems; Nonadaptive Systems, Scaling, Self-Similarity, and Measures of Complexity; and General Discussion

Contents

• Philip W. Anderson. The Eightfold Way to the Theory of Complexity: a prologue. 1994

(1) Mathematical and computational complexity, NP etc (2) Information theory and measures of complexity (3) Ergodic theory, chaos, attractors (4) Cellular automata (5) Large random physical systems, spin glasses, neural nets, etc (6) Self-organised criticality (7) AI, learning machines (8) Wetware, the brain • Even if there is no compressed description of a particular solution, even if the fastest way to find out what happens is to watch the system compute, there are compressed descriptions of general principles, of statistics of the solutions • Gell-Mann's measure of problem complexity: how much money do you need to solve it?

• Murray Gell-Mann. Complex Adaptive Systems. 1994

CASs perceive and respond to patterns: responding to patterns that are not actually there is "superstition", refusing to recognise patterns that are real is "denial" • Compression of perceived regularities, not just look-up tables • External fitness imposed by humans in the loop, versus internal emergent fitness where it is harder to define what is fit without being circular • Maladaptive: frozen accidents, mismatched timescales, ... • Hierarchies of CASs, higher level CASs composed of coevolving CASs

• Marcus W. Feldman, Luigi Luca Cavalli-Sforza, Lev A. Zhivotovsky. On the Complexity of Cultural Transmission and Evolution. 1994

Transmission and evolution of "atoms" of culture: traits and their variants • vertical transmission from parents to children (eg religion, hunting skills), horizontal transmission within a generation (eg fashions), oblique transmission between unrelated members of different generations (eg teacher-pupil transmission) • gene-culture co-transmission: difficult to separate the effects

• W. Brian Arthur. On the Evolution of Complexity. 1994

Systems get more complex in three ways: (1) growth of coevolutionary diversity: new individuals provide new niches, new opportunities for further new individuals and new niches, and so on (2) structural deepening: systems break out of limits by adding new functions or subsystems (3) "capturing" simpler elements and "programming" them • the economy is described in terms of the "dominant zeitgeist metaphor" of the time: originally this was static, deterministic, in equilibrium, now more dynamic, process oriented • big technology like the jet engine is maladaptive because of mismatched timescales: a jet engine design lasts for 20 years, but political and technological timescales are much shorter.

• Stuart A. Kauffman. Whispers from Carnot: the origins of order and principles of adaptation in complex nonequilibrium systems. 1994

Computational complexity shows it is not possible to have a general theory (compressed description) of all possible non-equilibrium systems, but there may be universal laws of self-constructing, self-organising, far from equilibrium systems • random graph theory suggests sufficiently complex sets of catalytic polymers will almost inevitably contain collectively autocatalytic sets • as diversity of molecules increases, a phase transition in the reaction graph occurs, autocatalytic sets "crystallise" -- low diversities catalyse few or no reactions for new molecules: subcritical behaviour -- high diversities catalyse many reactions for new molecules, leading to exploding diversity: supracritical behaviour • supracritical systems cannot stop changing, strongly subcritical systems cannot start changing -- so diversity in individual systems like cells might evolve towards being just subcritical • the biosphere is probably strongly supracritical • random Boolean networks exhibit chaotic (when each node is connected to K>4 other nodes) and ordered (when K=2) behaviour • adaptation by small incremental changes -- not chaotic systems, because of sensitivity; they change too radically -- not ordered systems, because small changes have only small effects; they converge too strongly to easily evolve new behaviour -- again, the complex region is best suited • as Boolean networks evolve to solve a problem they move towards this edge of chaos phase-transition region, from both ordered and chaotic starts • coevolution on coupled fitness landscapes moves to the edge of chaos, where each component acts selfishly, yet optimal mean fitness occurs • boundedly rational agents may move to the edge of chaos by coevolving optimally complex models of the others' behaviour • Carnot: second law of (equilibrium) thermodynamics -- we seek a new "second law" of non-equilibrium, dynamic, self-organising systems • (discussion) • evolving scientific theories about a fixed world may converge; many agents coevolving theories about each others' behaviour need not converge • the difference between organic chemistry (collectively autocatalytic sets) and evolution of species is that organic molecules don't change, but species change and go extinct

• Thomas S. Ray. Evolution and Complexity. 1994

Darwinian evolution is the generative force behind most complex system. Natural evolution acts so slowly it is difficult to study. Tierra provides a much faster artificial evolutionary environment. Tierra evolution, starting from one single "organism", exhibits optimisation, speciation, coevolution, cooperation, parasitism. Different random seeds give different ecologies. Think of a cloud of points moving through a multidimensional "program string", or artificial organism, space. Most of the space represents unviable organisms. As the points flow through the space, they may bifurcate or split into sub-clouds. Some regions are viable only if other regions are also populated. The mutation rate may be an analogue of Langton's lambda parameter: too low and evolution plods; too high and everything gets chaotic and dies; just right gives a rich ecological structure.

• Hans Frauenfelder. Proteins as Complex Adaptive Systems (abstract only). 1994

Proteins have had billions of years to evolve good folding: how well does a random sequence of amino acids fold?

• Alan S. Perelson. Two theoretical problems of immunology: AIDS and epitopes. 1994

A simple mathematical model of T-cell depletion can explain the observed depletion • T cells that strongly recognise "self" are killed in the thymus • only vertebrates have immune systems • there seems to be a strong immune response against the fastest growing HIV species, which makes the patient HIV+, but not a strong response to the slow-growing ones

• Brian C. Goodwin. Developmental complexity and evolutionary order. 1994

The space of possible biological forms is much smaller than the genetic program space • historical explanations are inadequate as scientific explanations • natural selection is a form of dynamic stability analysis • certain biological structures can be explained as high probability stable patterns in the morphogenetic field • no genetic program parameter changes are needed to explain the sequence of changes during [this particular] development; dynamics interacting with growth that changes that dynamics is sufficient • since simple rules can produce complex patterns, there is no need to produce an evolutionary reason for the existence every single piece of the pattern

• Walter Fontana, Leo W. Buss. What would be conserved if "the tape were played twice"?. 1994

A lambda-calculus model of chemical reactions that exhibits multi-level self-maintaining organisations that are robust to perturbations

• Charles F. Stevens. Complexity of brain circuits. 1994

Brain complexity (number of synapses per neuron) is roughly constant in mammalian brains: we just have more brain than does a mouse • if you reroute part of a hamster's brain, so that input to the visual cortex goes to the somatosensory cortex, the new target behaves like visual cortex, the processing is the same, and there is some evidence the animal "sees" with its somatosensory cortex • first-learned languages tend to be more compactly represented in the brain than later-learned languages

• Ben Martin. The Schema. 1994

A history of schemata as a means of organising and storing perceptions, providing a structure for how the mind models and interprets the world, from Aristotle and Plato, through Hume and Kant, to Bartlett, Minsky and beyond

• Alan Lapedes. A Complex Systems approach to computational molecular biology. 1994

Correlated sites distant on DNA might be physically close on the folded protein • using co-learning NNs to recognise 2ndary protein structure without using preexisting structure categories • emergent structures classified are not the standard alpha, beta, coil classes

• John Henry Holland. Echoing Emergence: objectives, rough definitions, and speculations for ECHO-class models. 1994

• Alfred Hubler, David Pines. Prediction and adaptation in an evolving chaotic environment. 1994

• Peter Schuster. How do RNA molecules and viruses explore their worlds?. 1994

• James H. Brown. Complex ecological systems. 1994

• Kenneth J. Arrow. Beyond general equilibrium (abstract only). 1994

• John Maynard Smith. The major transitions in evolution. 1994

• Erica Jen. Cellular Automata: complex nonadaptive systems (abstract only). 1994

• Per Bak. Self-Organized Criticality: a holistic view of nature. 1994

• Melanie Mitchell, James P. Crutchfield, Peter T. Hraber. Dynamics, Computation, and the "Edge of Chaos": a re-examination. 1994

• James P. Crutchfield. Is anything ever new? Considering emergence. 1994