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