Complexity - A Guided Tour Part 20

"If we knew exactly the laws of nature": Poincare, 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. 130141.

"This is a linear system": One could argue that this is not actually a linear system, since the population increases exponentially over time: nt = 2t n0. However, it is the map from nt to nt+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 nt is the population at the current generation and k is the carrying capacity. To derive the logistic map from this model, let xt = nt/k, and R = (birthrate deathrate). Note that xt is the "fraction of carrying capacity": the ratio of the current population to the maximum possible population. Then xt+1 = Rxt (1 xt).

Because the population size nt is always between 0 and k, xt 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. 427; 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. 459467, 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. 2544.

"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. 368369.

"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. 922931.

"The fact that the simple and deterministic equation": May, R. M., Simple mathematical models with very complicated dynamics. Nature, 261, 1976, pp. 459467.

"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 Duree and revolution, disciplines, and cultures. Historia Mathematica 29, 2002, pp. 273339.

"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. 490496.

"Pierre Coullet and Charles Tresser, who also used the technique of renormalization": Coullet, P., and Tresser, C., Iterations d'endomorphismes et groupe de renormalization. Comptes Rendues de Academie des Sciences, Paris A, 287, 1978, pp. 577580.

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 a 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, Inst.i.tute 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. 840856.

"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. 905940. 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 Inst.i.tute 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 ent.i.tled "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 a.s.sumes 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. 379423, 623656.

"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. 499512.

"the nature and limits of distributed computation in markets": lecture by David Pennock ent.i.tled "Information and complexity in securities markets," Inst.i.tute 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. 918922.

"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.o.del's proof is complicated": For excellent expositions of the proof, see Nagel, E. and Newman, J. R., G.o.del's Proof. New York: New York University, 1958; and Hofstadter, D. R., G.o.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. 230265.

"According to his biographer Hao w.a.n.g": w.a.n.g, H., Reflections on Kurt G.o.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 Ill.u.s.trated 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 sh.o.r.eless 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. 128129. Quoted in Cochrane, E., Viva Lamarck: A brief history of the inheritance of acquired characteristics. Aeon 2:2, 1997, pp. 539.

"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, Trans.m.u.tation 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 & n.o.ble 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.

"n.o.body 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. 2159.

"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.

8687. "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 c.u.mulative 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. 399401.

"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. 1619.

"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. 302307.

"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. 186213.

"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. 275283.

"Stephen Wolfram, for example, has proposed": Wolfram, S., Universality and complexity in cellular automata. Physica D, 10, 1984, pp. 135.

"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. 215233.