Complexity theory 1977-1997

Mathematics:
Switch from Kolmogrov-Chaitin algorithmic complexity:

complexity
= randomness

to **Crutchfield-Smale
computational complexity**:

complexity
= “fractionalness” of fractal dimension (inverted U function).

**Cellular
automata**:
J.H. Conway takes von Neumann’s death wish and creates the “game of life.”
Amateurs at mainframes everywhere begin to play and discover a chaotic
self-organizing universe.

**Genetic
Algorithms**:
John Holland (U. Michigan) finds that a population of mutating, reproducing
digital systems can be selected for problem-solving behavior. Evolution can
create useful algorithms via bottom-up emergence.

**Dissipative
Systems**:
Belgian physicist I. Prigogene writes book on B-Z reactions, termite mounds,
etc. Varela and Maturana: “Autopoiesis.”

**Self-organizing
phenomena**:
Evelyn Fox Keller does work on slime molds, Arthur Winfree on tissue cultures
and insect colonies, showing emergence of scaling structures.

**Cooperation
in decision-making**: Axelrod’s “Evolution of Cooperation” shows that Rappoport’s
“tit-for-tat” strategy in an iterated prisoner’s dilemma population is stable
and robust.

**Decentralized
computing**:
Daniel Hillis begins commercial parallel computing, later genetic algorithms.
Stuart Kauffman’s Random Boolian networks show a digital version of neural nets
in which self-organization creates pools of stability, similar to models for
the origin of life and ecosystems. Hopfield and others re-animate analog neural
networks. Rodney Brooks creates decentralized robotics (“subsumption
architecture”).

**Artificial
Life**: Craig
Reynolds’ “boids” show spontaneous flocking behavior. Dawkins and Sims –
biomorphs and other evolving forms. Steve Wolfram and Chris Langton: cellular
automata maximize complexity at “the edge of chaos.” Thomas Ray: Tierra, an
artificial ecosystem. Popular versions: SimLife, SimEarth, SimCity. Foundation
of the Santa Fe Institute.