Complexity: A Guided Tour - Melanie Mitchell (2009)

NOTES

Preface

“REDUCTIONISM is”: Hofstadter, D. R., Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books, 1979, p. 312.

“to divide all the difficulties under examination”: Descartes, R., A Discourse on the Method. Translated by Ian Maclean. Oxford: Oxford University Press, 1637/2006, p. 17.

“it seems probable that most of the grand underlying principles”: Quoted in Horgan, J., The End of Science: Facing the Limits of Knowledge in the Twilight of the Scientific Age. Reading, MA: Addison-Wesley, 1996, p. 19.

“emerging syntheses in science”: The proceedings of this meeting were published as a book: Pines, D., Emerging Syntheses in Science. Reading, MA: Addison-Wesley, 1988.

“pursue research on a large number of highly complex and interactive systems”; “promote a unity of knowledge”: G. Cowan, Plans for the future. In Pines, D., Emerging Syntheses in Science. Reading, MA: Addison-Wesley, 1988, pp. 235, 237.

“a conference … on the subject of ‘emergent computation’ ”: The proceedings of this meeting were published as a book: Forrest, S., Emergent Computation. Cambridge, MA: MIT Press, 1991.

Part I

“Science has explored the microcosmos and the macrocosmos”: Pagels, H., The Dreams of Reason. New York: Simon & Schuster, 1988, p. 12.

Chapter 1

“Ideas thus made up”: Locke, J., An Essay Concerning Human Understanding. Edited by P. H. Nidditch. Oxford: Clarendon Press, 1690/1975, p. 2.12.1.

“Half a million army ants”: This description of army ant behavior was gleaned from the following sources: Franks, N. R., Army ants: A collective intelligence. American Scientist, 77(2), 1989, pp. 138-145; and Hölldobler, B. and Wilson, E. O., The Ants. Cambridge, MA: Belknap Press, 1990.

“The solitary army ant”: Franks, N. R., Army ants: A collective intelligence. American Scientist, 77(2), 1989, pp. 138-145.

“what some have called a ‘superorganism’ ”: E.g., Hölldobler, B. and Wilson, E. O., The Ants. Cambridge, MA: Belknap Press, 1990, p. 107.

“I have studied E. burchelli”: Franks, N. R., Army ants: A collective intelligence. American Scientist, 77(2), 1989, p. 140.

“Douglas Hofstadter, in his book Gödel, Escher, Bach”: Hofstadter, D. R., Ant fugue. In Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books, 1979.

Chapter 2

“It makes me so happy”: Stoppard, T., Arcadia. New York: Faber & Faber, 1993, pp. 47-48.

“nature is exceedingly simple”: Quoted in Westfall, R. S., Never at Rest: A Biography of Isaac Newton. Cambridge: Cambridge University Press, 1983, p. 389.

“it was possible, in principle, to predict everything for all time”: Laplace, P. S., Essai Philosophique Sur Les Probabilites. Paris: Courcier, 1814.

“influences whose physical magnitude”: Liu, Huajie, A brief history of the concept of chaos, 1999 [http://members.tripod.com/~huajie/Paper/chaos.htm].

“If we knew exactly the laws of nature”: Poincaré, H., Science and Method. Translated by Francis Maitland. London: Nelson and Sons, 1914.

“Edward Lorenz found”: Lorenz, E. N., Deterministic nonperiodic flow. Journal of Atmospheric Science, 357, 1963, pp. 130-141.

“This is a linear system”: One could argue that this is not actually a linear system, since the population increases exponentially over time: n_t = 2^tn0. However, it is the map from n_t to n_t+1 that is the linear system being discussed here.

“an equation called the logistic model”: From [http://mathworld.wolfram.com/LogisticEquation.html]: “The logistic equation (sometimes called the Verhulst model, logistic map, or logistic growth curve) is a model of population growth first published by Pierre Verhulst (1845). The model is continuous in time, but a modification of the continuous equation to a discrete quadratic recurrence equation is also known as the logistic equation.” The logistic map is the name given to one particularly useful way of expressing the logistic model.

“I won’t give the actual equation”: Here is the logistic model:

where n_t is the population at the current generation and k is the carrying capacity. To derive the logistic map from this model, let x_t = n_t/k, and R = (birthrate − deathrate). Note that x_t is the “fraction of carrying capacity”: the ratio of the current population to the maximum possible population. Then

x_t+1 = Rx_t (1 − x_t).

Because the population size n_t is always between 0 and k, x_t is always between 0 and 1.

“the logistic map”: The following references provide technical discussions of the logistic map, aimed at the general scientifically educated reader: Feigenbaum, M. J., Universal behavior in nonlinear systems. Los Alamos Science, 1 (1), 1980, pp. 4-27; Hofstadter, D. R., Mathematical chaos and strange attractors. In Metamagical Themas. New York: Basic Books, 1985; Kadanoff, Leo P., Chaos, A view of complexity in the physical sciences. In From Order to Chaos: Essays: Critical, Chaotic, and Otherwise. Singapore: World Scientific, 1993.

“a 1971 article by the mathematical biologist Robert May”: May, R. M., Simple mathematical models with very complicated dynamics. Nature, 261, pp. 459-467, 1976.

“Stanislaw Ulam, John von Neumann, Nicholas Metropolis, Paul Stein, and Myron Stein”: Ulam, S. M., and von Neumann, J., Bulletin of the American Mathematical Society, 53, 1947, p. 1120. Metropolis, N., Stein, M. L., & Stein, P. R., On finite limit sets for transformations on the unit interval. Journal of Combinatorial Theory, 15(A), 1973, pp. 25-44.

“The values of x … become chaotic”: How do we know that the system will not settle down to a regular oscillation after a large number of iterations? This can be shown mathematically; e.g., see Strogtaz, S., Nonlinear Dynamics and Chaos. Reading, MA: Addison-Wesley, 1994, pp. 368-369.

“a basis for constructing pseudo-random numbers”: A pseudo-random number generator is a deterministic function or algorithm that outputs values whose distribution and lack of correlation satisfies certain statistical tests of randomness. Such algorithms are used in modern computing for many different applications. Using the logistic map as a basis for pseudo-random number generators was first suggested in Ulam, S. M. and von Neumann, J., On combination of stochastic and deterministic processes (abstract). Bulletin of the American Mathematical Society, 53, 1947, p. 1120. This has been further investigated by many others, for example, Wagner, N. R., The logistic equation in random number generation. In Proceedings of the Thirtieth Annual Allerton Conference on Communications, Control, and Computing, University of Illinois at Urbana-Champaign, 1993, pp. 922-931.

“The fact that the simple and deterministic equation”: May, R. M., Simple mathematical models with very complicated dynamics. Nature, 261, 1976, pp. 459-467.

“The term chaos … T. Y. Li and James York”: Li, T. Y. and Yorke, J. A., Period three implies chaos. American Mathematical Monthly 82, 1975, p. 985.

“The period-doubling route to chaos has a rich history”: For an interesting history of the study of chaos, see Aubin, D. and Dalmedico, A. D., Writing the history of dynamical systems and chaos: Longue Durée and revolution, disciplines, and cultures. Historia Mathematica 29, 2002, pp. 273-339.

“Feigenbaum adapted it for dynamical systems theory”: For an accessible explanation of Feigenbaum’s theory, see Hofstadter, D. R., Mathematical chaos and strange attractors. In Metamagical Themas. New York: Basic Books, 1985.

“the best thing that can happen to a scientist”: Quoted in Gleick, J., Chaos: Making a New Science. New York: Viking, 1987, p. 189.

“certain computer models of weather”: see, e.g., Selvam, A. M.. The dynamics of deterministic chaos in numerical weather prediction models. Proceedings of the American Meteorological Society, 8th Conference on Numerical Weather Prediction, Baltimore, MD, 1988; and Lee, B. and Ajjarapu, V., Period-doubling route to chaos in an electrical power system. IEE Proceedings, Part C, 140, 1993, pp. 490-496.

“Pierre Coullet and Charles Tresser, who also used the technique of renormalization”: Coullet, P., and Tresser, C., Itérations d’endomorphismes et groupe de renormalization. Comptes Rendues de Académie des Sciences, Paris A, 287, 1978, pp. 577-580.

Chapter 3

“The law that entropy increases”: Eddington, A. E., The Nature of the Physical World. Macmillan, New York, 1928, p. 74.

“complex systems sense, store, and deploy more information”: Cohen, I., Informational landscapes in art, science, and evolution. Bulletin of Mathematical Biology, 68, 2006, p. 1218.

“evolution can perform its tricks”: Beinhocker, E. D., The Origin of Wealth: Evolution, Complexity, and the Radical Remaking of Economics. Cambridge, MA: Harvard Business School Press, 2006, p. 12.

“Although they differ widely in their physical attributes”: Gell-Mann, M., The Quark and the Jaguar. New York: W. H. Freeman, 1994, p. 21.

“Why the second law should”: Rothman, T., The evolution of entropy. In Science à la Mode. Princeton, NJ: Princeton University Press, 1989, p. 82.

“the hot system”: Maxwell, quoted in Leff, H. S. and Rex, A. F., Maxwell’s Demon: Entropy, Information, Computing. Princeton University Press. Second edition 2003, Institute of Physics Pub., 1990, p. 5.

“In a famous paper”: Szilard, L., On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings. Zeitschrift fuer Physik, 53, 1929, pp. 840-856.

“the mathematician Charles Bennett showed”: Bennett’s arguments are subtle; the details can be found in Bennett, C. H., The thermodynamics of computation—a review. International Journal of Theoretical Physics, 21, 1982, pp. 905-940. Many of these ideas were independently discovered by the physicist Oliver Penrose (Leff, H. S. and Rex, A. F., Maxwell’s Demon: Entropy, Information, Computing, Taylor & Francis, 1990; second edition Institute of Physics Pub., 2003).

“the demon remains controversial to this day”: E.g., see Maddox, J., Slamming the door. Nature, 417, 2007, p. 903.

“repellent to many other scientists”: Evidently Boltzmann was himself a feisty critic of the work of others. As William Everdell reports, Boltzmann wrote a paper entitled “On a thesis of Schopenhauer,” but later wrote that he had wanted to call it “Proof that Schopenhauer Was a Degenerate, Unthinking, Unknowing, Nonsense-Scribbling Philosopher, Whose Understanding Consisted Solely of Empty Verbal Trash.” Everdell, W. R., The First Moderns: Profiles in the Origins of Twentieth-Century Thought. Chicago, IL: University of Chicago Press, 1998, p. 370.

“Boltzmann defined the entropy of a macrostate”: This version of Boltzmann’s entropy assumes all microstates that correspond to a given macrostate are equally probable. Boltzmann also gave a more general formula that defines entropy for non-equiprobable microstates.

“The actual equation”: In the equation for Boltzmann’s entropy, S = k log W, S is entropy, W is the number of possible microstates corresponding to a given macrostate, and k is “Boltzmann’s constant,” a number used to put entropy into standard units.

“In his 1948 paper ‘A Mathematical Theory of Communication’ ”: Shannon, C., A mathematical theory of communication. The Bell System Technical Journal, 27, 1948, pp. 379-423, 623-656.

“efforts to marry communication theory”: Pierce, J. R., An Introduction to Information Theory: Symbols, Signals, and Noise. New York: Dover, 1980, p. 24. (First edition, 1961.)

Chapter 4

“Quo facto”: Leibniz, G. (1890). In C. Gerhardt (Ed.), Die Philosophischen Schriften von Gottfried Wilheml Liebniz, Volume VII. Berlin: Olms. Translation from Russell, B., A History of Western Philosophy, Touchstone, 1967, p. 592. (First edition, 1901.)

“computation in cells and tissues”: E.g., Paton, R., Bolouri, H., Holcombe, M., Parish, J. H., and Tateson. R., editors. Computation in Cells and Tissues: Perspectives and Tools of Thought, Berlin: Springer-Verlag, 2004.

“immune system computation”: Cohen, I. R., Immune system computation and the immunological homunculus. In O. Nierstrasz et al. (Editors), MoDELS 2006, Lecture Notes in Computer Science 4199. Springer-Verlag, 2006, pp. 499-512.

“the nature and limits of distributed computation in markets”: lecture by David Pennock entitled “Information and complexity in securities markets,” Institute for Computational and Mathematical Engineering, Stanford University, November 2005.

“emergent computation in plants”: Peak, D., West, J. D., Messinger, S. M., and Mott, K. A., Evidence for complex, collective dynamics and emergent, distributed computation in plants. Proceedings of the National Academy of Sciences, USA, 101(4), 2004, pp. 918-922.

“there is no such thing as an unsolvable problem”: Quoted in Hodges, A., Alan Turing: The Enigma, New York: Simon & Schuster, 1983, p. 92.

“Gödel’s proof is complicated”: For excellent expositions of the proof, see Nagel, E. and Newman, J. R., Gödel’s Proof. New York: New York University, 1958; and Hofstadter, D. R., Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books, 1979.

“This was an amazing new turn”: Hodges, A., Alan Turing: The Enigma. New York: Simon & Schuster, 1983, p. 92.

“Turing killed off the third”: Another mathematician, Alonzo Church, also proved that there are undecidable statements in mathematics, but Turing’s results ended up being more influential.

“his answer, again, was ‘no’ ”: Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(42), 1936, pp. 230-265.

“According to his biographer Hao Wang”: Wang, H., Reflections on Kurt Gödel. Cambridge, MA: MIT Press, 1987.

Chapter 5

“All great truths begin as blasphemies”: Shaw, G. B., Annajanska, the Bolshevik Empress. London: Kessinger Publishing, 1919/2004, p. 15.

“Subject to decay are all componded things”: Quoted in Bowker, J. (editor), The Cambridge Illustrated History of Religions. Cambridge, UK: Cambridge University Press, 2002, p. 76.

“The earth shall wax old like a garment”: Isaiah 51:6. The Holy Bible, King James Version.

“O! How shall summer’s honey breath hold out”: From Shakespeare, Sonnet 65.

“If I were to give an award for the single best idea anyone has ever had”: Dennett, D. R., Darwin’s Dangerous Idea. New York: Simon & Schuster, 1995, p. 21.

“Organic life beneath the shoreless waves”: Darwin, E., The Temple of Nature; or, The Origin of Society: A Poem with Philosophical Notes. London: J. Johnson, 1803.

“Lamarck … had few clear facts”: Quoted in Grinnell, G. J., The rise and fall of Darwin’s second theory. Journal of the History of Biology, 18 (1), 1985, p. 53.

“if [the] instinctual life of animals permits of any explanation at all”: Freud, S., Moses and Monotheism. New York: Vintage Books, 1939, pp. 128-129. Quoted in Cochrane, E., Viva Lamarck: A brief history of the inheritance of acquired characteristics. Aeon 2:2, 1997, pp. 5-39.

“You care for nothing but shooting, dogs, and rat-catching”: Darwin, C. and Barlow, N. D., The Autobiography of Charles Darwin. Reissue edition, New York: W. W. Norton, 1958/1993, p. 28.

“Darwin also read Adam Smith’s free-market manifesto”: Darwin writes in a letter to W. D. Fox (January 1829), “My studies consist of Adam Smith & Locke.” The Correspondence of Charles Darwin, Volume 1 (F. Burkhardt and S. Smith, editors). Cambridge, U.K.: Cambridge University Press, 1985, p. 72.

“the type of beak was adapted”: For further reading on this, see Weiner, J., The Beak of the Finch: A Story of Evolution in Our Time. New York: Knopf, 1994.

“I am almost convinced”: Quoted in Bowlby, J., Charles Darwin: A New Life. New York W. W. Norton, 1992, p. 254.

“Plato … says”: Barrett, P. (editor), Charles Darwin’s Notebooks, 1836-1844: Geology, Transmutation of Species, Metaphysical Enquiries. Ithaca, NY: Cornell University Press, 1987, p. 551.

“[A]ll my originality”: Darwin’s letter to Charles Lyell, June 18, 1858. Listed in The Darwin Correspondence Online Database, [http://www.darwinproject.ac.uk], Letter 2285.

“base and paltry”: Darwin’s letter to Charles Lyell, June 25, 1858. Ibid, Letter 2294.

“I freely acknowledge that Mr. Matthew”: Quoted in Darwin, C., The Autobiography of Charles Darwin. Lanham, MD: Barnes & Noble Publishing, Endnote 21, 2005, p. 382. Originally published 1887.

“How extremely stupid not to have thought of that!”: Quoted in Provine, W. B., The Origins of Theoretical Population Genetics. Chicago: University of Chicago Press, 1971, p. 4.

“This unification of Darwinism and Mendelism”: The term “Modern Synthesis” came from Julian Huxley’s influential book Evolution: The Modern Synthesis, New York, London: Harper, 1942. The Modern Synthesis has also been called the Neo-Darwinian Synthesis, the Modern Evolutionary Synthesis, and, for those particularly in the know, simply the Synthesis.

“Nobody could ever again look at the evolutionary process without very consciously standing on the edifice of the Synthesis”: Tattersall, I., Becoming Human: Evolution and Human Uniqueness. New York: Harvest Books, 1999, p. 83.

“Motoo Kimura proposed a theory of ‘neutral evolution’ ”: For a discussion of Kimura’s theory see Dietrich, M. R., The origins of the neutral theory of molecular evolution. Journal of the History of Biology, 27 (1), 1994, pp. 21-59.

“Manfred Eigen and Peter Schuster observed”: For a good exposition of Eigen and Schuster’s work, see Eigen, M., Steps Towards Life. Oxford: Oxford University Press, 1992.

86-87. “the synthetic theory … is effectively dead”: Gould, S. J., Is a new and general theory of evolution emerging? Paleobiology, 6, 1980, p. 120.

“The view of evolution due to the Modern Synthesis ‘is one of the greatest myths’ ”: Eldredge, N. and Tattersall, I., The Myths of Human Evolution. New York: Columbia University Press, 1982, p. 43.

“I am of the opinion that nothing is seriously wrong with the achievements”: Mayr, E., An overview of current evolutionary biology. In Warren, L. and Koprowski, H. (editors), New Perspectives on Evolution. New York: Wiley-Liss, 1991, p. 12.

“The theory of evolution by cumulative natural selection”: Dawkins, R., The Extended Phenotype (Reprint edition). Oxford University Press, 1989, p. 317. Originally published 1982.

Chapter 6

“the cell’s flash cards”: Hofstadter, D. R. The Genetic Code: Arbitrary? In Metamagical Themas. New York: Basic Books, 1985, p. 681.

Chapter 7

“what the term gene refers to”: See Pearson, H., “What is a gene?” Nature, vol. 441, 2006, pp. 399-401.

“The physicist Seth Lloyd published a paper in 2001”: Lloyd, S., Measures of complexity: A non-exhaustive list. IEEE Control Systems Magazine, August 2001.

“This is called the algorithmic information content”: A detailed reference to Kolmogorov, Chaitin, and Solmonoff’s ideas is Li, M. and Vitanyi, P., An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition. New York: Springer-Verlag, 1997.

“Murray Gell-Mann proposed a related measure”: Gell-Mann, M. What is complexity? Complexity, 1 (1), 1995, pp. 16-19.

“the subjectivity of its definition remains a problem”: See, e.g., McAllister, J. W., Effective complexity as a measure of information content. Philosophy of Science 70, 2003, pp. 302-307.

“Logically deep objects”: Bennett, C. H., How to define complexity in physics, and why. In W. H. Zurek (editor), Complexity, Entropy, and the Physics of Information, Reading, MA: Addison-Wesley, 1990, p. 142.

“It is an appealing idea”: Lloyd, S., The calculus of intricacy. The Sciences, 30, 1990, p. 42.

“Seth Lloyd and Heinz Pagels proposed”: Lloyd, S. and Pagels, H., Complexity as thermodynamic depth. Annals of Physics, 188, 1988, pp. 186-213.

“the most plausible scientifically determined” and “the total amount of thermodynamic and informational resources”: Lloyd, S., The calculus of intricacy. The Sciences, 30, 1990, p. 42.

“As pointed out by some critics”: Crutchfield, J. P. and Shalizi, C. R., Thermodynamic depth of causal states: When paddling around in Occam’s pool shallowness is a virtue. Physical Review E, 59 (1), 1999, pp. 275-283.

“Stephen Wolfram, for example, has proposed”: Wolfram, S., Universality and complexity in cellular automata. Physica D, 10, 1984, pp. 1-35.

“However, as Charles Bennett and others have argued”: e.g., see Bennett, C. H., Dissipation, information, computational complexity and the definition of organization. In D. Pines (editors), Emerging Syntheses in Science. Redwood City, CA: Addison-Wesley, 1985, pp. 215-233.

“statistical complexity”: Crutchfield, J. P. and Young, K., Inferring statistical complexity, Physics Review Letters 63, 1989, pp. 105-108.

“the atomic structure of complicated crystals”: Varn, D. P., Canright, G. S., and Crutchfield, J. P., Discovering planar disorder in close-packed structures from X-ray diffraction: Beyond the fault model. Physical Review B, 66, 2002, pp. 174110-1-174110-4.

“the firing patterns of neurons”: Haslinger, R., Klinkner, K. L., and Shalizi, C. R., The computational structure of spike trains. Unpublished manuscript, 2007.

“the universe is fractal-like”: Mandelbrot, B. B., The Fractal Geometry of Nature. New York: W. H. Freeman, 1977.

“in general a fractal is a geometric shape”: Strogatz, S., Nonlinear Dynamics and Chaos. Reading, MA: Addison-Wesley, 1994.

“fractal dimension”: A great introduction to fractals and the concept of fractal dimension is Mandelbrot’s book The Fractal Geometry of Nature. New York: W. H. Freeman, 1977.

“I’ll do a calculation out of your sight”: For the Koch curve, 3 dimension = 4. To solve for dimension, take the logarithm (using any base) of both sides:

log(3^dimension) = dimension × log(3) = log(4). Thus dimension

= log(4)/ log(3) ≈ 1.26.

“the cascade of detail”: Bovill, C., Fractal Geometry in Architecture and Design. Birkhäuser Boston, 1996, p. 4.

“The Architecture of Complexity”: Simon, H. A., The architecture of complexity. Proceedings of the American Philosophical Society, 106 (96), 1962, pp. 467-482.

“the complex system being composed of subsystems”: Ibid, p. 468.

“Daniel McShea … has proposed a hierarchy scale”: McShea, D. W., The hierarchical structure of organisms: A scale and documentation of a trend in the maximum. Paleobiology, 27 (2), 2001, pp. 405-423.

Part II

“Nature proceeds little by little”: Quoted in Grene, M. and Depew, D., The Philosophy of Biology: An Episodic History. Cambridge University Press, 2004, p. 14.

“[W]e all know intuitively what life is”: Lovelock, J. E, The Ages of Gaia. New York: W. W. Norton, 1988, p. 16.

Chapter 8

“Self-Reproducing Computer Programs”: Parts of this chapter were adapted from Mitchell, M., Life and evolution in computers. History and Philosophy of the Life Sciences, 23, 2001, pp. 361-383.

“ … there has been some fascinating research”: See, for example, Luisi, P. L., The Emergence of Life: From Chemical Origins to Synthetic Biology. Cambridge: Cambridge University Press, 2006; or Fry, I., The Emergence of Life on Earth: A Historical and Scientific Overview. Piscataway, NJ: Rutgers University Press, 2000.

“the field of artificial life”: For more information about the field of artificial life, see, for example, Langton, C. G., Artificial Life: An Overview. Cambridge, MA: MIT Press, 1997; or Adami, C., Introduction to Artificial Life. New York: Springer, 1998.

“The complete work was eventually published”: Von Neumann, J., Theory of Self-Reproducing Automata (edited and completed by A. W. Burks). Urbana: University of Illinois Press, 1966. For descriptions of von Neumann’s self-replicating automaton, see Burks, A. W., Von Neumann’s self-reproducing automata. In A. W. Burks (editor), Essays on Cellular Automata. Urbana: University of Illinois Press, 1970; or Mitchell, M., Computation in cellular automata: A selected review. In T. Gramss et al. (editors), Nonstandard Computation, 1998, pp. 95-140. Weinheim, Germany: Wiley-VCH. For an account of self-replication in DNA and how it relates to mathematical logic and self-copying computer programs, see Hofstadter, D. R., Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books, 1979, pp. 495-548.

“reproductive potentialities of the machines of the future’ ”: Quoted in Heims, S. J., John Von Neumann and Norbert Wiener: From Mathematics to the Technologies of Life and Death. Cambridge, MA: MIT Press, 1980, pp. 212-213.

“their respective nonfiction”: Kurzweil, R., The Age of Spiritual Machines: When Computers Exceed Human Intelligence. New York: Viking, 1999; and Moravec, H., Robot: Mere Machine to Transcendent Mind. New York: Oxford University Press, 1999.

“now famous article in Wired”: Joy, B., Why the future doesn’t need us. Wired, April 2000.

“some simple self-reproducing robots”: Zykov, V. Mytilinaios, E., Adams, B., and Lipson, H., Self-reproducing machines. Nature, 435, 2005, pp. 163-164.

“When his mother once stared rather aimlessly”: Macrae, N., John von Neumann. New York: Pantheon, 1992, p. 52.

“the greatest paper on mathematical economics”: Quoted in Macrae, N., John von Neumann. New York: Pantheon, 1992, p. 23.

“the most important document ever written on computing and computers”: Goldstine, H. H., The Computer, from Pascal to von Neumann. Princeton, NJ: Princeton University Press, first edition, 1972, p. 191.

“Five of Hungary’s six Nobel Prize winners”: Macrae, N., John von Neumann. New York: Pantheon, 1992, p. 32.

“The [IAS] School of Mathematics”: Quoted in Macrae, N., John von Neumann. New York: Pantheon, 1992, p. 324.

“to have no experimental science”: Quoted in Regis, E., Who Got Einstein’s Office? Eccentricity and Genius at the Institute for Advanced Study. Menlo Park, CA: Addison-Wesley, 1987, p. 114.

“The snobs took revenge”: Regis, E., Who Got Einstein’s Office? Eccentricity and Genius at the Institute for Advanced Study. Menlo Park, CA: Addison-Wesley, 1987, p. 114.

Chapter 9

“ evolutionary computation”: For a history of early work on evolutionary computation, see Fogel, D. B., Evolutionary Computation: The Fossil Record. New York: Wiley-IEEE Press, 1998.

“That’s where genetic algorithms came from”: John Holland, quoted in Williams, S. Unnatural selection. Technology Review, March 2, 2005.

“automating parts of aircraft design,” Hammond, W. E. Design Methodologies for Space Transportation Systems, 2001, Reston, VA: American Institute of Aeronautics and Astronautics, Inc., p. 548.

“analyzing satellite images”: See, e.g., Harvey, N. R., Theiler, J., Brumby, S. P., Perkins, S. Szymanski, J. J., Bloch, J. J., Porter, R. B., Galassi, M., and Young, A. C. Comparison of GENIE and conventional supervised classifiers for mulitspectral image feature extraction. IEEE Transactions on Geoscience and Remote Sensing, 40, 2002, pp. 393-404.

“automating assembly line scheduling.” Begley, S. Software au naturel. Newsweek, May 8, 1995.

“computer chip design”: Ibid.

“realistic computer-animated horses”: See Morton, O., Attack of the stuntbots. Wired, 12.01, 2004.

“realistic computer-animated stunt doubles”: “Virtual Stuntmen Debut in Hollywood Epic Troy,” news release, NaturalMotion Ltd. [http://www.naturalmotion.com/files/nm_troy.pdf].

“discovery of new drugs”: See, e.g., Felton, M. J., Survival of the fittest in drug design. Modern Drug Discovery, 3(9), 2000, pp. 49-50.

“detecting fraudulent trades”: Bolton, R. J. and Hand, D. J., Statistical fraud detection: A review. Statistical Science, 17(3), 2002, pp. 235-255.

“analysis of credit card data”: Holtham, C., Fear and opportunity. Information Age, July 11, 2007.

“forecasting financial markets”: See, e.g., Williams, F., Artificial intelligence has a small but loyal following. Pensions and Investments, May 14, 2001.

“portfolio optimization”: Coale, K., Darwin in a box. Wired, June 14, 1997.

“artwork created by an interactive genetic algorithm”: see [http://www.karlsims.com].

“I will take you through a simple extended example”: This example is inspired by a project at the MIT Artificial Intelligence Lab, in which a robot named “Herbert” wandered around the halls and offices collecting empty soda cans and taking them to the recycling bin. See Connell, J. H., Minimalist Mobile Robotics: A Colony-Style Architecture for an Artificial Creature. San Diego: Academic Press, 1990.

“This means that there are 243 different possible situations”: There are five different sites each with three possible types of contents, thus there are 3 × 3 × 3 × 3 × 3 = 243 different possible situations.

“Evolutionary algorithms are a great tool”: Jason Lohn, quoted in Williams, S., Unnatural selection. Technology Review, March 2, 2005.

Part III

“The proper domain of computer science”: Quoted in Lewin, R., Complexity: Life at the Edge of Chaos. New York: Macmillan, 1992, p. 48.

Chapter 10

“a recent article in Science magazine”: Shouse, B., Getting the behavior of social insects to compute. Science, 295(5564), 2002, 2357.

“‘Is the brain a computer?’”: Churchland, P. S., Koch, C., and Sejnowski, T. J., What is computational neuroscience? In E. L. Schwartz (editor), Computational Neuroscience. Cambridge, MA: MIT Press, 1994, pp. 46-55.

“The answer is … 2⁵¹²”: As will be described later in the chapter, to define a rule, you must specify the update state for the center lightbulb given all possible configurations of its local neighborhood. Since a local neighborhood consists of eight neighbors plus the center bulb itself, and each bulb can be either on or off, the number of possible configurations of a local neighborhood is 2⁹ = 512. For each configuration, one can assign either “on” or “off” as the update state, so the number of possible assignments to all 512 configurations is 2⁵¹² ≈ 1.3 × 10¹⁵⁴.

“The Game of Life”: Much of what is described here can be found in the following sources: Berlekamp, E., Conway, J. H., and Guy, R., Winning Ways for Your Mathematical Plays, Volume 2. San Diego: Academic Press, 1982; Poundstone, W., The Recursive Universe. William Morrow, 1984; and many of the thousands of Web sites devoted to the Game of Life.

“John Conway also sketched a proof”: Berlekamp, E., Conway, J. H., and Guy, R., Winning Ways for Your Mathematical Plays, volume 2. San Diego: Academic Press, 1982.

“later refined by others”: e.g., see Rendell, P., Turing universality of the game of Life. In A. Adamatzky (editor), Collision-Based Computing, pp. 513-539. London: Springer-Verlag, 2001.

“a review on how to convert base 2 numbers to decimal”: Recall that for decimal (base 10) number, say, 235, each “place” in the number corresponds to a power of 10: 235 = 2 × 10² + 3 × 10¹ + 5 × 10⁰ (where 10⁰ = 1). In base 2, each place corresponds to a power of 2. For example, 235 in base 2 is 11101011:

11101011 = 1 × 2⁷ + 1 × 2⁶ + 1 × 2⁵ + 0 × 2⁴ + 1 × 2³ + 0 × 2²

+ 1 × 2¹ + 1 × 2⁰ = 235.

“The Rule 30 automaton is the most surprising thing I’ve ever seen in science”: Quoted in Malone, M. S., God, Stephen Wolfram, and everything else. Forbes ASAP, November 27, 2000. [http://members.forbes.com/asap/2000/1127/162.html]

“In fact, Wolfram was so impressed by rule 30”: “Random Sequence Generators” U.S. Patent 4691291, September 1, 1987.

“class 4 involves a mixture”: Wolfram, S., A New Kind of Science. Champaign, IL, Wolfram Media, 2002, p. 235.

“Matthew Cook … finally proved that rule 110 was indeed universal”: Cook, M., Universality in elementary cellular automata. Complex Systems 15(1), 2004, 1-40.

“A New Kind of Science”: Wolfram, S., A New Kind of Science. Champaign; IL: Wolfram Media, 2002, p. 235.

“you would be able to build such a computer to solve the halting problem”: See Moore, C., Recursion theory on the reals and continuous-time computation. Theoretical Computer Science, 162, 1996, pp. 23-44.

“definite ultimate model for the universe”: Wolfram, S., A New Kind of Science. Champaign, IL: Wolfram Media, 2002, p. 466.

“I’m guessing it’s really short”: Stephen Wolfram, quoted in Levy, S., The man who cracked the code to everything …. Wired, Issue 10.06, June 2002.

158-159. “Konrad Zuse and Edward Fredkin had both theorized”: See Zuse, K., Rechnender Raum Braunschweig: Friedrich Vieweg & Sohn, 1969 (English translation: Calculating Space. MIT Technical Translation AZT-70-164-GEMIT, Massachusetts Institute of Technology (Project MAC), Cambridge, MA, 02139, February 1970); and Wright, R., Did the universe just happen? Atlantic Monthly, April 1988, pp. 29-44.

Chapter 11

“Computing with Particles”: A detailed description of our work on cellular automata and particles can be found in Crutchfield, J. P., Mitchell, M., and Das, R., Evolutionary design of collective computation in cellular automata. In J. P. Crutchfield and P. K. Schuster (editors), Evolutionary Dynamics—Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2003, pp. 361-411.

“an article by the physicist Norman Packard”: Packard, N. H., Adaptation toward the edge of chaos. In J. A. S. Kelso, A. J. Mandell, M. F. Shlesinger, eds., Dynamic Patterns in Complex Systems. Singapore: World Scientific, 1988, pp. 293-301.

“majority classification”: The majority classification task is also known in the cellular automata literature as “density classification.”

“Jim Crutchfield had earlier invented”: See, e.g., Crutchfield, J. P., and Hanson, J. E., Turbulent pattern bases for cellular automata. Physica D 69, 1993, pp. 279-301.

“Twenty Problems in the Theory of Cellular Automata”: Wolfram, S., Twenty problems in the theory of cellular automata. Physica Scripta, T9, 1985, pp. 170-183.

“Botanist Keith Mott, physicist David Peak”: See Peak, D., West, J. D., Messinger, S. M., and Mott, K. A., Evidence for complex, collective dynamics and emergent, distributed computation in plants. Proceedings of the National Academy of Sciences, USA, 101 (4), 2004, pp. 918-922.

Chapter 12

“Information Processing in Living Systems”: Parts of this chapter were adapted from Mitchell, M., Complex systems: Network thinking. Artificial Intelligence, 170 (18), 2006, pp. 1194-1212.

“we need to answer the following”: My questions are related to the three levels of description of information processing proposed by David Marr, described in his book Vision: Marr, D. Vision. San Francisco, Freeman, 1982. Questions similar to mine were formulated by Ron McClamrock; see McClamrock, R., Marr’s three levels: A re-evaluation. Minds and Machines, 1 (2), 1991, pp. 185-196.

“The Immune System”: Two excellent, readable overviews of the immune system are Sompayrac, L. M., How the Immune System Works, 2nd edition, Blackwell Publishing, 1991; and Hofmeyr, S. A., An interpretive introduction to the immune system. In L. A. Segel and I. R. Cohen (editors), Design Principles for the Immune System and Other Distributed Autonomous Systems. New York: Oxford University Press, 2001.

“A third mechanism has been hypothesized”: For more details, see Lesley, R. Xu, Y., Kalled, S. L., Hess, D. M., Schwab, S. R., Shu, H.-B., and Cyster, J. G., Reduced competitiveness of autoantigen-engaged B cells due to increased dependence on BAFF. Immunity, 20 (4), 2004, pp. 441-453.

“foraging for food works roughly as follows”: For more detailed descriptions of ant foraging, see Bonabeau, E., Dorigo, M., and Theraulaz, G., Swarm Intelligence: From Natural to Artificial Systems. New York: Oxford University Press, 1999.

“The ecologist Deborah Gordon has studied task allocation”: See, e.g., Gordon, D. M., Task allocation in ant colonies. In L. A. Segel and I. R. Cohen. (editors), Design Principles for the Immune System and Other Distributed Autonomous Systems. New York: Oxford University Press., 2001.

“construction of bridges or shelters”: e.g., see Lioni, A., Sauwens, C., Theraulaz, G., and Deneubourg, J.-L., Chain formation in OEcophylla longinoda. Journal of Insect Behavior, 14 (5), 2001, pp. 679-696.

“All three systems described above use randomness”: The role of randomness in complex adaptive systems is also explored in Millonas, M. M., The importance of being noisy. Bulletin of the Santa Fe Institute, Summer, 1994.

“Eventually, the ants will have established a detailed map”: Ziff, E. and Rosenfield, I., Evolving evolution. The New York Review of Books, 53, 8, May 11, 2006.

“‘parallel terraced scan’ ”: Hofstadter D., Fluid Concepts and Creative Analogies. New York: Basic Books, 1995, p. 92.

“Maintaining a correct balance”: This is discussed in Holland, J. H., Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press, 1992 (first edition, 1975); and Hofstadter, D. R. and Mitchell, M., The Copycat project: A model of mental fluidity and analogy-making. In K. Holyoak and J. Barnden (editors), Advances in Connectionist and Neural Computation Theory, Volume 2: Analogical Connections, 1994, pp. 31-112.

“ who or what actually perceives the meaning”: Some of the many books and articles addressing these issues from a philosophical standpoint are the following: Hofstadter, D. R., Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books, 1979; Dennett, D. R., Consciousness Explained. Boston: Little, Brown, 1991; Bickhard, M. H., The biological foundations of cognitive science. In Mind 4: Proceedings of the 4th Annual Meeting of the Cognitive Science Society of Ireland. Dublin, Ireland: J. Benjamins, 1999; Floridi, L., Open problems in the philosophy of information. Metaphilosophy, 35 (4), 2004, pp. 554-582; and Hofstadter, D., I am a Strange Loop. New York: Basic Books, 2007.

“artificial immune systems”: See, e.g., Hofmeyr, S. A. and Forrest, S., Architecture for an artificial immune system. Evolutionary Computation, 8 (4), 2000, pp. 443-473.

“ant colony optimization algorithms”: See, e.g., Dorigo, M. and Stützle, T., Ant Colony Optimization, MIT Press, 2004.

Chapter 13

“How to Make Analogies”: Parts of this chapter were adapted from Mitchell, M., Analogy-Making as Perception, MIT Press, 1993; and Mitchell, M., Analogy-making as a complex adaptive system. In L. Segel and I. Cohen (editors), Design Principles for the Immune System and Other Distributed Autonomous Systems. New York: Oxford University Press, 2001.

“About a year ago, the Sacramento Bee ”: Lohr, S., This boring headline is written for Google. New York Times, April 9, 2006.

“At conferences you are hearing the phrase ‘human-level AI’ ”: Eric Horvitz, quoted in Markoff, J., Brainy robots start stepping into daily life. New York Times, July 18, 2006.

“Easy things are hard”: Minsky, M., The Society of Mind. New York: Simon & Schuster, 1987, p. 29.

“All perception of truth is the detection of an analogy”: Thoreau, H. D. (with L. D. Walls, editor). Material Faith: Thoreau on Science. New York: Mariner Books, 1999, p. 28.

“a relatively new book written by a Computer Science professor”: Hofstadter, D. R., Gödel, Escher, Bach: an Eternal Golden Braid. New York: Basic Books, 1979.

“an even more impressive array of successor programs”: For descriptions of several of these programs, including Copycat, see Hofstadter D., Fluid Concepts and Creative Analogies. New York: Basic Books, 1995.

“the barrier of meaning”: Rota, G.-C., In memoriam of Stan Ulam—The barrier of meaning. Physica D, 2 (1-3), 1986, pp. 1-3.

Chapter 14

“necessary and sufficient components of all models in physics”: Garber, D., Descartes, mechanics, and the mechanical philosophy. Midwest Studies in Philosophy 26 (1), 2002, pp. 185-204.

“he pictured the Earth like a sponge”: Kubrin, D., Newton and the cyclical cosmos: Providence and the mechanical philosophy. Journal of the History of Ideas, 28 (3), 1967.

“intuition pumps”: Dennett, D. R., Elbow Room: The Varieties of Free Will Worth Wanting. Cambridge, MA: MIT Press, 1984, p. 12.

“Merrill Flood and Melvin Drescher, invented the Prisoner’s Dilemma”: For an entertaining and enlightening discussion of the Prisoner’s Dilemma, and, more generally, game theory and its history and applications, see Poundstone, W., Prisoner’s Dilemma. New York: Doubleday, 1992.

“the pursuit of self-interest for each”: Axelrod, R., The Evolution of Cooperation. New York: Basic Books, 1984, p. 7.

“the tragedy of the commons”: Hardin, G., The tragedy of the commons. Science, 162, 1968, pp. 1243-1248.

“Under what conditions will cooperation emerge”: Axelrod, R., The Evolution of Cooperation. New York: Basic Books, 1984, p. 3.

“Thomas Hobbes, who concluded that cooperation could develop”: Hobbes’ arguments about centralized governments can be found in Hobbes, T., Leviathan. First published in 1651; 1991 edition edited by R. Tuck. Cambridge University Press, 1991.

“Albert Einstein similarly proposed”: Einstein’s thoughts about world government and many other issues can be found in a collection of his writings, Einstein, A., Out of My Later Years. First published in 1950; revised edition published in 2005 by Castle Books.

“Axelrod experimented with adding norms”: Axelrod, R., An evolutionary approach to norms. American Political Science Review, 80 (4), 1986, pp. 1095-1111.

“Meta-norms can promote and sustain cooperation”: Axelrod, R., An evolutionary approach to norms. American Political Science Review, 80 (4), 1986, pp. 1095-1111.

“Nowak performed computer simulations”: Nowak, M. A. and May, R. M., Evolutionary games and spatial chaos. Nature, 359 (6398), 1992, pp. 826-829.

“We believe that deterministically generated spatial structure”: Ibid.

“chaotically changing”: Ibid.

“That territoriality favours cooperation”: Sigmund, K., On prisoners and cells, Nature, 359 (6398), 1992, p. 774.

“John Holland has likened such models to ‘flight simulators’”: Holland, J. H., Emergence: From Chaos to Order. Perseus Books, 1998, p. 243.

“proposals for improving peer-to-peer networks”: e.g., Hales, D. and Arteconi, S., SLACER: A Self-Organizing Protocol for Coordination in Peer-to-Peer Networks. IEEE Intelligent Systems, 21 (2), 2006, pp. 29-35.

“preventing fraud in electronic commerce”: e.g., see Kollock, P., The production of trust in online markets. In E. J. Lawler, M. Macy, S. Thyne, and H. A. Walker (editors), Advances in Group Processes, Vol. 16. Greenwich, CT: JAI Press, 1999.

“ … work by Martin Nowak”: Nowak, M. A., Five rules for the evolution of cooperation. Science, 314 (5805), 2006, pp. 1560-1563.

“New Energy Finance … recently put out a report”: Liebreich, M., How to Save the Planet: Be Nice, Retaliatory, Forgiving, & Clear. White Paper, New Energy Finance, Ltd., 2007. [http://www.newenergyfinance.com/
docs/Press/
NEF_WP_Carbon-Game-Theory_05.pdf]

“impact on policy-making research regarding government response to terrorism, arms control, and environmental governance policies”: For example, see Cupitt, R. T., Target rogue behavior, not rogue states. The Nonproliferation Review, 3, 1996, pp. 46-54; Cupitt, R. T. and Grillot, S. R., COCOM is dead, long live COCOM: Persistence and change in multilateral security institutions. British Journal of Political Science 27, 7, pp. 361-89; and Friedheim, R. L., Ocean governance at the millennium: Where we have been, where we should go: Cooperation and discord in the world economy. Ocean and Coastal Management, 42 (9), 1999, pp. 747-765.

“areas ranging from the maintenance of biodiversity to the effectiveness of bacteria in producing new antibiotics”: E.g., Nowak, M. A. and Sigmund, K., Biodiversity: Bacterial game dynamics. Nature, 418, 2002, pp. 138-139; Wiener, P., Antibiotic production in a spatially structured environment. Ecology Letters, 3(2), 2000, pp. 122-130.

“All models are wrong”: Box, G.E.P. and Draper, N. R., Empirical Model Building and Response Surfaces. New York: Wiley 1997, p. 424.

“Replication is one of the hallmarks”: Axelrod R., Advancing the art of simulation in the social sciences. In Conte, R., Hegselmann, R., Terna, P. (editors), Simulating Social Phenomena. (Lecture Notes in Economics and Mathematical Systems 456). Berlin: Springer-Verlag, 1997.

“Bernardo Huberman and Natalie Glance re-implemented”: Huberman, B. A. and Glance, N. S., Evolutionary games and computer simulations. Proceedings of the National Academy of Science, USA, 90, 1993, pp. 7716-7718.

“A similar result was obtained independently by Arijit Mukherji, Vijay Rajan, and James Slagle”: Mukherji, A., Rajan, V., and Slagle, J. R., Robustness of cooperation. Nature, 379, 1996, pp. 125-126.

“Nowak, May, and their collaborator Sebastian Bonhoeffer replied”: Nowak, M. A., Bonhoeffer, S., and May, R. M., Spatial games and the maintenance of cooperation. Proceedings of the National Academy of Sciences, USA, 91, 1994, pp. 4877-4881; Nowak, M. A., Bonhoeffer, S., and May, R. M., Reply to Mukherji et al. Nature, 379, 1996, p. 126.

“Jose Manuel Galan and Luis Izquierdo published results”: Galan, J. M. and Izquierdo, L. R., Appearances can be deceiving: Lessons learned re-implementing Axelrod’s ‘Evolutionary Approaches to Norms.’ Journal of Artificial Societies and Social Simulation, 8 (3), 2005, [http://jasss.soc.surrey.ac.uk/8/3/2.html].

“The art of model building”: Anderson, Nobel Prize acceptance speech, 1977.

Part IV

“In Ersilia”: From Calvino, I. Invisible Cities. New York: Harcourt Brace Jovanovich, 1974, p. 76. (Translated by W. Weaver.)

Chapter 15

“The Science of Networks”: Parts of this chapter were adapted from Mitchell, M., Complex systems: Network thinking. Artificial Intelligence, 170 (18), 2006, pp. 1194-1212.

“Milgram wrote of one example”: From Milgram, S., The small-world problem. Psychology Today 1, 1967, pp. 61-67.

“Later work by psychologist Judith Kleinfeld”: see Kleinfeld, Could it be a big world after all? Society, 39, 2002.

228. an “urban myth”: Kleinfeld, J. S., Six degrees: Urban myth? Psychology Today, 74, March/April 2002.

“When people experience an unexpected social connection”: Kleinfeld, J. S., Could it be a big world after all? The “six degrees of separation” myth. Society, 39, 2002.

“the ‘new science of networks’”: E.g., Barabási, A.-L., Linked: The New Science of Networks. Cambridge, MA: Perseus, 2002.

“the publication of two important papers”: Watts, D. J. and Strogatz, S. H., Collective dynamics of ‘small world’ networks. Nature 393, 1998, pp. 440-442; Barabási, A.-L. and Albert, R., Emergence of scaling in random networks, Science, 286, 1999, pp. 509-512.

“No one descends with such fury”: Watts, D. J., Six Degrees: The Science of a Connected Age. New York: W. W. Norton & Co, 2003, p. 32.

“network thinking is poised”: Barabási, A.-L. Linked: The New Science of Networks. Cambridge, MA: Perseus, 2002, p. 222.

“123 incoming links”: All the in-link counts in this chapter were obtained from [http://www.microsoft-watch.org/cgi-bin/ranking.htm]. The count includes only in-links from outside the Web page’s domain.

“mathematically define the concept of ‘small-world network’”: See Watts, D. J. and Strogatz, S. H., Collective dynamics of ‘small world’ networks. Nature, 393, 1998, pp. 440-442.

“The average path length of the regular network of figure 15.4 turns out to be 15”: This value was calculated using the formula l = N/2k. Here l is the average path length, N is the number of nodes, and k is the degree of each node (here 2). See Albert, R. and Barabási, A-L., Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 2002, pp. 48-97.

“the average path-length has shrunk to about 9”: This value was estimated from the results given in Newman, M. E. J., Moore, C., and Watts, D. J., Mean-field solution of the small-world network model. Physical Review Letters, 84, 1999, pp. 3201-3204.

“only a few random links can generate a very large effect”: Watts, D. J., Six Degrees: The Science of a Connected Age. New York: W. W. Norton, 2003, p. 89.

“small-world property”: The formal definition of the small-world property is that, even though relatively few long-distance connections are present, the shortest path length (number of link hops) between two nodes scales logarithmically or slower with network size n for fixed average degree.

“Kevin Bacon game”: See, e.g., [http://en.wikipedia.org/wiki/Six_Degrees_of_
Kevin_Bacon].

“neuroscientists had already mapped out every neuron and neural connection”: For more information, see Achacoso, T. B. and Yamamoto, W. S., AY’s Neuroanatomy of C. Elegans for Computation. Boca Raton, FL: CRC Press, 1991.

“do not actually have the kinds of degree distributions”: The Watts-Strogatz model produces networks with exponential degree distributions, rather than the much more commonly observed power-law degree distributions in real-world networks. For details, see Albert, R. and Barabási, A-L., (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 2002, pp. 48-97.

“report about Washington State apple prices”: [http://www.americanfruitgrower.com/e_notes/page.php?page=news].

“information about the Great Huon Apple Race of Tasmania”: [http://www.huonfranklincottage.com.au/events.htm].

“this rule actually fits the data”: The in-link degree distribution of the Web is fit reasonably well with the power law k^−2.3 and cutoff k_min = 3684 (see Clauset, A., Shalizi, C. R., and Newman, M. E. J., Power-law distributions in empirical data. Preprint, 2007 [http://arxiv.org/abs/0706.1062].) The expression k⁻² given in this chapter is an approximation used for simplifying the discussion; plots of the k^−2.3 distribution look very similar to those given in the chapter.

Chapter 16

“neuroscientists have mapped the connectivity structure”: e.g., see Bassett, D. S. and Bullmore, D., Small-world brain networks. The Neuroscientist, 12, 2006, pp. 512-523; and Stam, C. J. and Reijneveld, J. C., Graph theoretical analysis of complex networks in the brain. Nonlinear Biomedical Physics, 1(1), 2007, p. 3.

“Genetic Regulatory Networks”: For more details on the application of network ideas to genetic regulation, see Barabási, A.-L. and Oltvai, Z. N., Network biology: Understanding the cell’s functional organization. Nature Reviews: Genetics, 5, 2004, pp. 101-113.

“Albert-László Barabási and colleagues looked in detail at the structure of metabolic networks”: Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., and Barabási, A.-L., The large-scale organization of metabolic networks. Nature, 407, 2000, pp. 651-654. Examples of other work on the structure of metabolic networks are Fell, D. A. and Wagner, A., The small world of metabolism. Nature Biotechnology, 18, 2000, pp. 1121-1122; and Burgard, A. P., Nikolaev, E. V., Schilling, C. H., and Maranas, C. D., Flux coupling analysis of genome-scale metabolic network reconstructions. Genome Research, 14, 2004, pp. 301-312.

“Although later studies debunked the theory”: See, e.g., Robbins, K. E., Lemey, P., Pybus, O. G., Jaffe, H. W., Youngpairoj, A. S., Brown, T. M., Salemi, M., Vandamme, A. M., and Kalish, M. L., U.S. human immunodeficiency virus type 1 epidemic: Date of origin, population history, and characterization of early strains. Journal of Virology, 77 (11), 2003, pp. 6359-6366.

“Recently, a group consisting of”: Liljeros, F., Edling, C. R., Nunes Amaral, L. A., Stanely, H. E., and Aberg, Y., The web of human sexual contacts. Nature, 441, 2001, pp. 907-908.

“similar results have been found in studies of other sexual networks”: e.g., Schneeberger, A., Mercer, C. H., Gregson, S. A., Ferguson, N. M., Nyamukapa, C. A., Anderson, R. M., Johnson, A. M., and Garnett, G. P., Scale-free networks and sexually transmitted diseases: A description of observed patterns of sexual contacts in Britain and Zimbabwe. Sexually Transmitted Diseases, 31 (6), 2004, pp. 380-387.

“A very clever yet simple method was proposed”: Cohen, R., ben-Avraham, D., and Havlin, S., Efficient immunization strategies for computer networks and populations. Physics Review Letters, 91 (24), 2003, p. 247901.

“one should target anti-virus methods”: Newman, M. E. J., Forrest, S., and Balthrop, J., Email networks and the spread of computer viruses. Physical Review E, 66, 2002, p. 035101.

“the ecology research community has recently seen a lot of debate”: See, e.g., Montoya, J. M. and Solé, R. V., Small world patterns in food webs. Journal of Theoretical Biology, 214 (3), 2002, pp. 405-412; Dunne, J. A., Williams, R. J., and Martinez, N. D., Food-web structure and network theory: The role of connectance and size. Proceedings of the National Academy of Science, USA, 99 (20), 2002, pp. 12917-12922; and Dunne, J. A., The network structure of food webs. In M. Pascual and J. A. Dunne (editors), Ecological Networks: Linking Structure to Dynamics in Food Webs. New York: Oxford University Press, 2006, pp. 27-86.

“Where Do Scale-Free Networks Come From?” Parts of this section were adapted from Mitchell, M., Complex systems: Network thinking. Artificial Intelligence, 170 (18), 2006, pp. 1194-1212.

“Albert-László Barabási and Réka Albert proposed”: Barabási, A.-L. and Albert, R., Emergence of scaling in random networks, Science, 286, 1999, pp. 509-512.

“this process and its power-law outcome had been discovered independently”: Yule, G. U., A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis. Philosophical Transactions of the Royal Society of London, Ser. B 213, 1924, pp. 21-87; Simon, H. A., On a class of skew distribution functions.” Biometrika 42 (3-4), 1955, p. 425; and Price, D. J., Networks of scientific papers. Science 149, 1965, pp. 510-515.

“the growth of so-called scientific citation networks”: e.g., see Redner, S., How popular is your paper? An empirical study of the citation distribution. European Physical Journal B, 4(2), 1998, pp. 131-134.

“what the writer Malcolm Gladwell called tipping points”: Gladwell, M., The Tipping Point: How Little Things Can Make a Big Difference. Boston: Little, Brown, 2000.

“A number of networks previously identified to be ‘scale-free’”: Clauset, A., Shalizi, C. R., and Newman, M. E. J., Power-law distributions in empirical data. Preprint, 2007, [http://arxiv.org/abs/0706.1062].

“Current assessments of the commonality of power-laws”: Keller, E. F., Revisiting ‘scale-free’ networks. BioEssays, 27, 2005, pp. 1060-1068.

“Our tendency to hallucinate”: Shalizi, C., Networks and Netwars, 2005. Essay at [http://www.cscs.umich.edu/~crshalizi/weblog/347.html].

“there turn out to be nine and sixty ways”: Shalizi, C., Power Law Distributions, 1/f noise, Long-Memory Time Series, 2007. Essay at [http://cscs.umich.edu/~crshalizi/notebooks/power-laws.html].

“a new hypothesized mechanism that resulted in power law distributions”: For surveys of some such mechanisms, see Mitzenmacher, M., A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2), 2003, pp. 226-251; and Newman, M. E. J., Power laws, Pareto distributions and Zipf’s law. Contemporary Physics, 46, 2005, pp. 323-351.

“The reported cause of the shutdown”: The cascading failure and its causes are described in detail in the U.S.-Canada Power System Outage Task Force’s Final Report on the August 14, 2003 Blackout in the United States and Canada: Causes and Recommendations [https://reports.energy.gov/].

“The computer system of the US Customs and Border protection agency”: see Schlossberg, D. “LAX Computer Crash Strands International Passengers.” ConsumerAffairs.com, August 13, 2007, [http://www.consumeraffairs.com/news04/
2007/08/lax_computers.html]; and Schwartz, J., “Who Needs Hackers?” New York Times, September 12, 2007.

“Long-Term Capital Management”: see, e.g., Government Accounting Office, Long-Term Capital Management: Regulators Need to Focus Greater Attention on Systemic Risk. Report to Congressional Request, 1999, [http://www.gao.gov/cgi-bin/getrpt?GGD-00-3]; and Coy, P., Woolley, S., Spiro, L. N., and Glasgall, W., Failed wizards of Wall Street. Business Week, September 21, 1998.

“The threat is complexity itself”: Andreas Antonopoulos, quoted in Schwartz, J., “Who Needs Hackers?” New York Times, September 12, 2007.

“Self-Organized Criticality”: for an introduction to SOC, see Bak, P., How Nature Works: The Science of Self-Organized Criticality. New York: Springer, 1996.

“Highly Optimized Tolerance”: For an introduction to HOT, see Carlson, J. M. and Doyle, J., Complexity and robustness. Proceedings of the National Academy of Science, USA 99, 2002, pp. 2538-2545.

“Next to the mysteries of dynamics on a network”: Watts, D. J., Six Degrees: The Science of a Connected Age. New York: W. W. Norton, 2003, p. 161.

Chapter 17

“the surface area scales as the volume raised to the two-thirds power”: Let V denote volume, S denote surface area, and r denote radius. V is proportional to r³, so cube-root (V) is proportional to the radius. Surface area is proportional to radius², and thus to cube-root(V)², which is .

“If you plot a power law on a double logarithmic plot, it will look like a straight line, and the slope of that line will be equal to the power law’s exponent”: In the example here, the power law is

metabolic rate α body mass^3/4.

Taking the logarithm of both sides, we get

log (metabolic rate) α 3/4 log (body mass).

This is the equation of a straight line with slope 3/4, if we plot log (metabolic rate) against log (body mass), which is actually what is plotted in figure 16.2

“Enquist later described the group’s math results as ‘pyrotechnics’”: Grant, B., The powers that be. The Scientist, 21 (3), 2007.

“You really have to think in terms of two separate scales”: G. B. West, quoted in Mackenzie, D., Biophysics: New clues to why size equals destiny. Science, 284 (5420), 1999, pp. 1607-1609.

“The mathematical details of the model”: A technical, but not too difficult to understand, description of the Metabolic Scaling model is given in West, G. B. and Brown, J. H., Life’s universal scaling laws. Physics Today, 57 (9), 2004, pp. 36-43.

“Although living things occupy a three-dimensional space”: West, G. B., Brown, J. H., and Enquist, B. J., The fourth dimension of life: Fractal geometry and allometric scaling of organisms. Science, 284, pp. 1677-1679.

“the potential to unify all of biology”: Grant, B., The powers that be. The Scientist, 21 (3), 2007.

“as potentially important to biology as Newton’s contributions are to physics”: Niklas, K. J., Size matters! Trends in Ecology and Evolution 16 (8), 2001, p. 468.

“We see the prospects for the emergence of a general theory of metabolism”: West, G. B. and Brown, J. H., The origin of allometric scaling laws in biology from genomes to ecosystems: Towards a quantitative unifying theory of biological structure and organization. Journal of Experimental Biology 208, 2005, pp. 1575-1592.

“Still others argue that Kleiber was wrong all along”: A review of various critiques of metabolic scaling theory is given in Agutter P. S and Wheatley, D. N., Metabolic scaling: Consensus or Controversy? Theoretical Biology and Medical Modeling, 18, 2004, pp. 283-289.

“The more detail that one knows about the particular physiology involved”: H. Horn, quoted in Whitfield, J., All creatures great and small. Nature, 413, 2001, pp. 342-344.

“It’s nice when things are simple”: H. Müller-Landau, quoted in Grant, B., The powers that be. The Scientist, 21 (3), 2007.

“There have been arguments that the mathematics in metabolic scaling theory is incorrect”: e.g., Kozlowski, J. and Konarzweski, M., Is West, Brown and Enquist’s model of allometric scaling mathematically correct and biologically relevant? Functional Ecology, 18, 2004, pp. 283-289.

“The authors of metabolic scaling theory have strongly stood by their work”: E.g., see West, G. B., Brown, J. H., and Enquist, B. J., Yes, West, Brown and Enquist’s model of allometric scaling is both mathematically correct and biologically relevant. (Reply to Kozlowski and Konarzweski, 2004.) Functional Ecology, 19, 2005, pp. 735-738; and Borrell, B., Metabolic theory spat heats up. The Scientist (News), November 8, 2007. [http://www.the-scientist.com/news/display/53846/].

“Part of me doesn’t want to be cowered”: G. West, quoted in Grant, B., The powers that be. The Scientist, 21 (3), 2007.

“I suspect that West, Enquist et al. will continue repeating their central arguments”: H. Müller-Landau, quoted in Borrell, B., Metabolic theory spat heats up. The Scientist (News), November 8, 2007. [http://www.the-scientist.com/news/display/53846/].

“more normal than ‘normal’”: “The presence of [power-law] distributions”: Willinger, W., Alderson, D., Doyle, J. C., and Li, L., More ‘normal’ than normal: Scaling distributions and complex systems. In R. G. Ingalls et al., Proceedings of the 2004 Winter Simulation Conference, pp. 130-141. Piscataway, NJ: IEEE Press, 2004.

“This relation is now called Zipf’s law”: Zipf’s original publication on this work is a book: Zipf, G. K., Selected Studies of the Principle of Relative Frequency in Language. Cambridge, MA: Harvard University Press, 1932.

“Benoit Mandelbrot … had a somewhat different explanation”: Mandelbrot. B., An informational theory of the statistical structure of languages. In W. Jackson (editor), Communicaiton Theory, Woburn, MA: Butterworth, 1953, pp. 486-502.

“Herbert Simon proposed yet another explanation”: Simon, H. A., On a class of skew distribution functions.” Biometrika 42 (3-4), 1955, p. 425.

“Evidently Mandelbrot and Simon had a rather heated argument”: Mitzenmacher, M., A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1 (2), 2003, pp. 226-251.

“the psychologist George Miller showed”: Miller, G. A., Some effects of intermittent silence. The American Journal of Psychology, 70, 1957, pp. 311-314.

Chapter 18

“ ‘mobile genetic elements’”: A technical article on the proposed role of mobile genetic elements on brain diversity is Muotri, A. R., Chu, V. T., Marchetto, M. C. N., Deng, W., Moran, J. V. and Gage, F. H., Somatic mosaicism in neuronal precursor cells mediated by L1 retrotransposition. Nature, 435, 2005, pp. 903-910.

“Recently a group of science philosophers and biologists performed a survey”: Reported in Pearson, H., What is a gene? Nature, 441, 2006, pp. 399-401.

“The more expert scientists become in molecular genetics”: Ibid.

“the absence of necessary methylation”: See, e.g., Dean, W., Santos, F., Stojkovic, M., Zakhartchenko, V., Walter, J., Wolf, E., and Reik, W., Conservation of methylation reprogramming in mammalian development: Aberrant reprogramming in cloned embryos. Proceedings of the National Academy of Science, USA, 98 (24), 2001, pp. 13734-13738.

“a large proportion of the DNA that is transcribed into RNA is not subsequently translated into proteins”: See, e.g., Mattick, J. S., RNA regulation: A new genetics? Nature Reviews: Genetics, 5, 2004, pp. 316-323; Grosshans, H. and Filipowicz, W., The expanding world of small RNAs. Nature, 451, 2008, pp. 414-416.

“The significance of non-coding RNA”: For a discussion of some of the current research and controversies in this area, see Hüttenhofer, A., Scattner, P., and Polacek, N., Non-coding RNAs: Hope or Hype? Trends in Genetics, 21 (5), 2005, pp. 289-297.

“The presumption that genes operate independently”: Caruso, D., A challenge to gene theory, a tougher look at biotech. New York Times, July 1, 2007.

“encode a specific functional product”: U.S. patent law, quoted in ibid.

“Evidence of a networked genome shatters the scientific basis”: Ibid.

“more than 90% of our DNA is shared with mice”: Published estimates of DNA overlap between humans and different species differ. However, it seems that “over 90% shared” is a fairly safe statement.

“a ‘black box’ that somehow transformed genetic information”: Carroll, S. B., Endless Forms Most Beautiful: The New Science of Evo Devo and the Making of the Animal Kingdom. New York: W. W. Norton, 2005, p. 7.

“The irony … is that what was dismissed as junk”: In the video Gene Regulation; Science, 319, no 5871, 2008.

“To verify that the BMP4 gene itself could indeed trigger the growth”: From Yoon, C. K., From a few genes, life’s myriad shapes. New York Times, June 26, 2007.

“In a strange but revealing experiment”: This work is described in Travis, J., Eye-opening gene. Science News Online, May 10, 1997.

“This conclusion is still quite controversial among evolutionary biologists”: For discussion of this controversy, see, e.g., Erwin, D. H., The developmental origins of animal bodyplans. In S. Xiao and A. J. Kaufman (editors), Neoproterozoic Geobiology and Paleobiology, New York: Springer, 2006, pp. 159-197.

“a world-class intellectual riffer”: Horgan, J., From complexity to perplexity. Scientific American, 272, June 1995, pp. 74-79.

“the genomic networks that control development”: Kauffman, S. A., At Home in the Universe. New York: Oxford University Press, 1995, p. 26.

“life exists at the edge of chaos”: Ibid, p. 26.

“Most biologists, heritors of the Darwinian tradition”: Ibid, p. 25.

“a ‘candidate fourth law of thermodynamics’”: Kauffman, S. J., Investigations. New York: Oxford University Press, 2002, p. 3.

“Kauffman’s book: The Origins of Order”: Kauffman, S. A., The Origins of Order. New York: Oxford University Press, 1993.

“a fundamental reinterpretation of the place of selection”: Burian, R. M. and Richardson, R. C., Form and order in evolutionary biology: Stuart Kauffman’s transformation of theoretical biology. In PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, Vol. 2: Symposia and Invited Papers, 1990, pp. 267-287.

“His approach opens up new vistas”: Ibid.

“the first serious attempt to model a complete biology”: Bak, P., How Nature Works: The Science of Self-Organized Criticality. New York: Springer, 1996.

“dangerously seductive”: Dover, G. A., On the edge. Nature, 365, 1993, pp. 704-706.

“There are times when the bracing walk through hyperspace”: Ibid.

“noise has a significant effect on the behavior of RBNs”: E.g., see Goodrich, C. S. and Matache, M. T., The stabilizing effect of noise on the dynamics of a Boolean network. Physica A, 379(1), 2007, pp. 334-356.

“It has essentially become a matter of social responsibility”: Hoelzer, G. A., Smith, E., and Pepper, J. W., On the logical relationship between natural selection and self-organization. Journal of Evolutionary Biology, 19 (6), 2007, pp. 1785-1794.

“Evolutionary biologist Dan McShea has given me a useful way to think about these various issues”: D. W. McShea, personal communication.

“Evolutionary biology is in a state of intellectual chaos”: D. W. McShea, personal communication.

Part V

“I will put Chaos into fourteen lines”: In Millay, E. St. Vincent, Mine the Harvest: A Collection of New Poems. New York: Harper, 1949, p. 130.

Chapter 19

“John Horgan published an article”: Horgan, J., From complexity to perplexity. Scientific American, 272, June 1995, pp. 74-79.

“ The End of Science”: Horgan, J., The End of Science: Facing the Limits of Knowledge in the Twilight of the Scientific Age. Reading, MA: Addison-Wesley, 1996.

“[T]he hope that physics could be complete”: Crutchfield, J. P., Farmer, J. D., Packard, N. H., and Shaw, R. S., Chaos. Scientific American, 255, December 1986.

“Gravitation is not responsible”: This quotation is very commonly attributed to Einstein. However, it is apparently a (more elegant) rephrasing of what he actually said: “Falling in love is not at all the most stupid thing that people do—but gravitation cannot be held responsible for it.” Quoted in Dukas, H. and Hoffmann B. (editors), Albert Einstein, The Human Side: New Glimpses from His Archives. Princeton, NJ: Princeton University Press, 1979, p. 56.

“Recently, ideas about complexity”: Gordon, D. M., Control without hierarchy. Nature, 446 (7132), 2007, p. 143.

“a new discipline of cybernetics”: Fascinating histories of the field of cybernetics can be found in Aspray, W., John von Neumann and the Origins of Modern Computing. Cambridge, MA: MIT Press, 1990; and Heims, S. The Cybernetics Group. Cambridge, MIT Press, 1991.

“the entire field of control and communication”: Wiener, N. Cybernetics. Cambridge, MA: MIT Press, 1948, p. 11.

“H. Ross Ashby’s ‘Design for a Brain’”: Ashby, R. H., Design for a Brain. New York: Wiley, 1954.

“Warren McCulloch and Walter Pitts’ model of neurons”: McCulloch, W. and Pitts, W., A logical calculus of ideas immanent in nervous activity. Bulletin of Mathematical Biophysics 5, 1942, pp. 115-133.

“Margaret Mead and Gregory Bateson’s application of cybernetic ideas”: See, e.g., Bateson, G., Mind and Nature: A Necessary Unity. Cresskill, NJ: Hampton Press, 1979.

“Norbert Wiener’s books Cybernetics and The Human Use of Human Beings”: Wiener, N. Cybernetics: Or the Control and Communication in the Animal and the Machine. Cambridge, MA: MIT Press, 1948; Wiener, N. The Human Use of Human Beings. Boston: Houghton Mifflin, 1950.

“The two most important historical events”: Gregory Bateson, quoted in Heims, S., The Cybernetics Group. Cambridge: MIT Press, 1991, p. 96.

“vacuous in the extreme”: Max Delbrück, quoted in Heims, S., The Cybernetics Group. Cambridge: MIT Press, 1991, p. 95.

“bull sessions with a very elite group”: Leonard Savage, quoted in Heims, S., The Cybernetics Group, 1991, p. 96.

“in the end Wiener’s hope”: Aspray, W., John von Neumann and the Origins of Modern Computing. Cambridge: MIT Press, 1990, pp. 209-210.

“General System Theory”: see Von Bertalanffy, L., General System Theory: Foundations, Development, Applications, New York: G. Braziller, 1969; or Rapoport, A. General System Theory: Essential Concepts and Applications, Cambridge, MA: Abacus Press, 1986.

“the formulation and deduction of those principles …”: Von Bertanlanffy, L., An outline of general system theory. The British Journal for the Philosophy of Science, 1(92), 1950, pp. 134-165.

“biologists Humberto Maturana and Francisco Varela attempted …”: See, e.g., Maturana, H. R. and Varela, F. J., Autopoiesis and Cognition: The Realization of the Living. Boston, MA: D. Reidel Publishing Co., 1980.

“Hermann Haken’s Synergetics and Ilya Prigogine’s theories of dissipative structures and nonequilibrium systems …”. See Haken, H., The Science of Structure: Synergetics, New York: Van Nostrand Reinhold, 1984; and Prigogine, I. From Being to Becoming: Time and Complexity in the Physical Sciences, San Francisco: W. H. Freeman, 1980.

“vocabulary of complexity,” “A number of concepts that deal with mechanisms …”: Nicolis, G. and Prigogine, I., Exploring Complexity, New York: W. H. Freeman and Co., 1989, p. x.

“I think we may be missing the conceptual equivalent of calculus …”: Strogatz, S., Sync: How Order Emerges from Chaos in the Universe, Nature, and Daily Life. New York: Hyperion, 2004, p. 287.

“He was hampered by the chaos of language”: Gleick, J., Isaac Newton, New York: Pantheon Books, 2003, pp. 58-59.

“The physicist Per Bak introduced the notion of self-organized criticality”: See Bak, P., How Nature Works: The Science of Self-Organized Criticality. New York: Copernicus, 1996.

“The physicist Jim Crutchfield has proposed a theory of computational mechanics”: See, e.g., Crutchfield, J. P., The calculi of emergence. Physica D, 75, 1994, 11-54.

“the simplicity on the other side of complexity”: The famous quotation “I do not give a fig for the simplicity on this side of complexity, but I would give my life for the simplicity on the other side of complexity” is usually attributed to Oliver Wendell Holmes, but I could not find the source of this in his writings. I have also seen this quotation attributed to the poet Gerald Manley Hopkins.

“One doesn’t discover new lands”: Gide, A., The Counterfeiters. Translated by D. Bussy. New York: Vintage, 1973, p. 353. Original: Journal des Faux-Monnayeurs. Paris: Librairie Gallimard, 1927.