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.