Complexity_ A Guided Tour - Melanie Mitchell [155]
“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 × 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., 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