Complexity - A Guided Tour Part 21

"statistical complexity": Crutchfield, J. P. and Young, K., Inferring statistical complexity, Physics Review Letters 63, 1989, pp. 105108.

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

"the firing patterns of neurons": Haslinger, R., Klinkner, K. L., and Shalizi, C. R., The computational structure of spike trains. Unpublished ma.n.u.script, 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(3dimension) = 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. Birkhauser 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. 467482.

"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 doc.u.mentation of a trend in the maximum. Paleobiology, 27 (2), 2001, pp. 405423.

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 Mitch.e.l.l, M., Life and evolution in computers. History and Philosophy of the Life Sciences, 23, 2001, pp. 361383.

" ... 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 Mitch.e.l.l, M., Computation in cellular automata: A selected review. In T. Gramss et al. (editors), Nonstandard Computation, 1998, pp. 95140. 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.o.del, Escher, Bach: an Eternal Golden Braid. New York: Basic Books, 1979, pp. 495548.

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

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

"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 doc.u.ment 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 n.o.bel 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 Inst.i.tute for Advanced Study. Menlo Park, CA: Addison-Wesley, 1987, p. 114.

"The sn.o.bs took revenge": Regis, E., Who Got Einstein's Office? Eccentricity and Genius at the Inst.i.tute 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 s.p.a.ce Transportation Systems, 2001, Reston, VA: American Inst.i.tute of Aeronautics and Astronautics, Inc., p. 548.

"a.n.a.lyzing satellite images": See, e.g., Harvey, N. R., Theiler, J., Brumby, S. P., Perkins, S. Szymanski, J. J., Bloch, J. J., Porter, R. B., Gala.s.si, M., and Young, A. C. Comparison of GENIE and conventional supervised cla.s.sifiers for mulitspectral image feature extraction. IEEE Transactions on Geoscience and Remote Sensing, 40, 2002, pp. 393404.

"automating a.s.sembly 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. 4950.

"detecting fraudulent trades": Bolton, R. J. and Hand, D. J., Statistical fraud detection: A review. Statistical Science, 17(3), 2002, pp. 235255.

"a.n.a.lysis 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. 4655.

"The answer is ... 2512": 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 29 = 512. For each configuration, one can a.s.sign either "on" or "off" as the update state, so the number of possible a.s.signments to all 512 configurations is 2512 1.3 10154.

"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. 513539. 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 102 + 3 101 + 5 100 (where 100 = 1). In base 2, each place corresponds to a power of 2. For example, 235 in base 2 is 11101011: 11101011 = 1 27 + 1 26 + 1 25 + 0 24 + 1 23 + 0 22.

1 21 + 1 20 = 235.

"The Rule 30 automaton is the most surprising thing I've ever seen in science": Quoted in Malone, M. S., G.o.d, 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.

"cla.s.s 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, 140.

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

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

158159. "Konrad Zuse and Edward Fredkin had both theorized": See Zuse, K., Rechnender Raum Braunschweig: Friedrich Vieweg & Sohn, 1969 (English translation: Calculating s.p.a.ce. MIT Technical Translation AZT-70-164-GEMIT, Ma.s.sachusetts Inst.i.tute of Technology (Project MAC), Cambridge, MA, 02139, February 1970); and Wright, R., Did the universe just happen? Atlantic Monthly, April 1988, pp. 2944.

Chapter 11.

"Computing with Particles": A detailed description of our work on cellular automata and particles can be found in Crutchfield, J. P., Mitch.e.l.l, 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. 361411.

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

"majority cla.s.sification": The majority cla.s.sification task is also known in the cellular automata literature as "density cla.s.sification."