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.