by Seth Lloyd
Marty Asher at Knopf was a patient and sensitive editor. Any style in the prose is due to Sara Lippincott, who turned my jotting into writing. John Brockman forced me to write the book in the first place, and Katinka Matson held my hand while I did it.
Finally, I’d like to thank those who are no longer here to be thanked, notably Heinz Pagels, Rolf Landauer, and Alexis Belash.
Further Reading
Discussions of the universe as a computer abound. In addition to Asimov’s “The Last Question” (1956), see, e.g., H. R. Pagels, The Cosmic Code (Simon & Schuster, 1982), J. D. Barrow, Theories of Everything (Clarendon Press, 1991), and F. J. Tipler, The Physics of Immortality (Doubleday, 1994).
The idea that the universe might be a classical digital computer was put forth in the 1960s by Konrad Zuse and Ed Fredkin. Zuse’s book is Rechnender Raum (Schriften zur Datenverarbeitung, Band 1, Friedrich Vieweg & Sohn, Braunschweig, 1969), translated as Calculating Space (MIT Technical Translation AZT-70-164-GEMIT, MIT [Proj. MAC], Cambridge, Mass. 02139, February 1970, http://www.idsia.ch/~juergen/zuse.html). Fredkin’s work can be found at http://www.digitalphilosophy.org/. The particular type of computer that they proposed was a “cellular automaton.” A cellular automaton consists of a regular array of cells, each of which contains one or more bits. Each cell updates itself from time step to time step as a function of its own state and that of its neighbors. The idea of universe as cellular automaton has more recently been popularized by Stephen Wolfram in A New Kind of Science (Wolfram Media, 2002).
For the mathematics behind monkeys typing on computers, see R. J. Solomonoff, “A Formal Theory of Inductive Inference,” Information and Control 7 (1964), 1–22; G. J. Chaitin, Algorithmic Information Theory (Cambridge University Press, 1987); A. N. Kolmogorov, “Three Approaches to the Quantitative Definition of Information,” Problems of Information Transmission 1 (1965), 1–11. Further discussion of the concept of algorithmic information and its relationship to the generation of complexity can be found the writings of Juergen Schmidhuber at http://www.idsia.ch/~juergen. See also Max Tegmark, “Is ‘The Theory of Everything’ Merely the Ultimate Ensemble Theory?” Annals of Physics 270 (1998), 1–51 (arXiv/gr-qc/9704009). For the relationship between algorithmic information and the second law of thermodynamics, see, e.g., W. H. Zurek, Nature 341 (1989), 119–24.
The idea that the undecidability problem and the halting problem are related to the problem of free will was suggested by Turing in his article “Computing Machinery and Intelligence,” Mind (1950), 433–60. See also K. R. Popper, “Indeterminism in Quantum Physics and Classical Physics,” British Journal for Philosophy of Science 1 (1951), 179–88. A classic paper on this topic is J. R. Lucas, “Minds, Machines, and Gödel,” Philosophy 36 (1961), 112–27. A more recent exploration of free will is Elbow Room: The Varieties of Free Will Worth Wanting, by Daniel C. Dennett (MIT Press, 1984). A study of the implications of the computational ability of the universe for our ability to predict its behavior can be found in D. R. Wolpert, “Computational Capabilities of Physical Systems,” Physical Review E 65, 016128 (2001) (arXiv/physics/0005058, physics/0005059).
A summary of the second law of thermodynamics and the nature of time asymmetry can be found in P. C. W. Davies, The Physics of Time Asymmetry (University of California Press, 1989). Physical Origins of Time Asymmetry, edited by J. J. Halliwell, J. Pérez Mercader, and W. H. Zurek (Cambridge University Press, 1996), is a collection of scientific articles on the subject. Many of the original papers on Maxwell’s demon can be found in Maxwell’s Demon 2: Entropy, Classical and Quantum Information, Computing, Harvey S. Leff, Andrew F. Rex (editors), Institute of Physics, 2003.
Many of the classic papers on quantum mechanics are collected, with commentary, in Quantum Theory and Measurement (ed. J. A. Wheeler and W. H. Zurek, Princeton University Press, 1983). A textbook on quantum mechanics with an emphasis on foundational issues is Quantum Theory: Concepts and Methods by A. Peres (Springer, 1995). The decoherent histories approach to quantum mechanics is described by Robert Griffiths in his book Consistent Quantum Theory (Cambridge, 2003). The way in which decoherence and chaos conspire to generate information is described in F. M. Cucchietti, D. A. R. Dalvit, J. P. Paz, W. H. Zurek, Physical Review Letters 91 (2003), p. 210403.
An introduction to quantum mechanics and quantum computation can be found in A Shortcut Through Time: The Path to the Quantum Computer by G. Johnson (Knopf, 2003). The standard textbook on quantum computers is Quantum Computation and Quantum Information by M. A. Nielsen and I. L. Chuang (Cambridge University Press, 2000).
Some of my work on the physical limits to computation and the computational capacity of the universe can be found in “Universe as Quantum Computer,” Complexity 3(1) (1997), 32–35 (arXiv/quant-ph/9912088); “Ultimate Physical Limits to Computation,” Nature 406 (2000), 1047–54 (arXiv/quant-ph/9908043); and “Computational Capacity of the Universe,” Physical Review Letters 88, 237901 (2002) (arXiv/quant-ph/0110141). A popular account of quantum gravity is Three Roads to Quantum Gravity by L. Smolin (Perseus Books, 2002). A technical version of my theory of quantum gravity based on quantum computation is “The Computational Universe: Quantum Gravity from Quantum Computation,” arXiv/quant-ph/0501135.
Accounts of the sciences of complexity can be found in The Quark and the Jaguar: Adventures in the Simple and Complex by Murray Gell-Mann (Freeman, 1995); Emergence: From Chaos to Order by John H. Holland (Perseus, 1999); and At Home in the Universe: The Search for Laws of Self-Organization and Complexity by Stuart Kauffman (Oxford, 1996). Charles Bennett’s analysis of complexity and definition of logical depth can be found in “Dissipation, Information, Computational Complexity, and the Definition of Organization,” in Emerging Syntheses in Science, edited by D. Pines (Addison Wesley, 1987), and “Logical Depth and Physical Complexity,” in The Universal Turing Machine: A Half-Century Survey edited by R. Herken (Oxford, 1988), pp. 227–57. The complementary notion of thermodynamic depth is described in S. Lloyd and H. Pagels, “Complexity as Thermodynamic Depth,” Annals of Physics 188 (1988), 186–213.
A NOTE ABOUT THE AUTHOR
Seth Lloyd is Professor of Mechanical Engineering at MIT and a principal investigator at the Research Laboratory of Electronics. He is also adjunct professor at the Santa Fe Institute. His work addresses problems having to do with information and complex systems, from the very small (how do atoms process information? how can you make them compute?) to the very large (how does society process information? how can we understand society in terms of its ability to process information?). His seminal work in the fields of quantum computation and quantum communications—including proposing the first technologically feasible design for a quantum computer, demonstrating the viability of quantum analog computation, proving quantum analogs of Shannon’s noisy channel theorem, and designing novel methods for quantum error correction and noise reduction—has gained him a reputation as an innovator and leader in the field of quantum computing.
www.sethlloyd.com
THIS IS A BORZOI BOOK
PUBLISHED BY ALFRED A. KNOPF
Copyright © 2006 by Seth Lloyd
All rights reserved.
Published in the United States by Alfred A. Knopf, a division of Random House, Inc., New York, and in Canada by Random House of Canada Limited, Toronto.
www.aaknopf.com
Knopf, Borzoi Books, and the colophon are registered trademarks of Random House, Inc.
Library of Congress Cataloging-in-Publication Data
Lloyd, Seth, [date]
Programming the universe : a quantum computer scientist takes on the cosmos / by Seth Lloyd.
p. cm.
eISBN-13: 978-0-307-26471-8
eISBN-10: 0-307-26471-8
1. Quantum theory—Mathematical models. 2. Microcomputers—Programming. 3. Quantum computers. I. Title.
QC174.12.L57 2006
530.12—dc22 2005050408
v1.0
1 By 1700 B.C. the Babylonian
s had a well-established “Arabic” number system, but zero was inferred from context, not written (i.e., 210 and 21 were written the same way). The oldest known “proto-abacus,” the Salamis counting tablet, dates to 300 B.C. The use of 0 for zero was introduced by Ptolemy in A.D. 130 and was well established in India by A.D. 650.
2 As in the bumper sticker “To err is human. To really screw things up requires a computer.”
3 In some cosmological theories the universe has been around forever; the Big Bang was preceded by a Big Crunch. In these models, our universe will expand, and then recontract in another Big Crunch, followed by another Big Bang, and so on. While allowed within the laws of physics, such oscillating universe models are not currently favored by observation.
4 Note that the discovery of new cosmic objects does not come about simply because telescopes are getting better and better. As time goes on, the distance we can see increases, at the rate of about one light-year per year—so the number of objects we can see increases. In cosmology this phenomenon is known as the “expansion of our horizon,” which is getting farther and farther away second by second.
5 Ramsey also gave me a good lesson in the language more usually called the language of love. I happened to be in his office when two members of the Academie Française came to call. “Why, Professeur Ramsey,” they inquired, “is French not the international language of Science?” Ramsey immediately answered them in his fluent French, with a thick midwestern accent. Horrified, they dropped the subject. In fact, the French Academy of Sciences caused the adoption of English as the international language of science in the seventeenth century by being the first national academy to abandon the previous international language, Latin, and publish their proceedings in their own language. The English and the Germans followed suit. The rest is just an accident of history.
6 Technically, a device that tries to extract work from heat without any exhaust to get rid of the information is called a perpetual motion machine of the second kind; perpetual motion machines of the first kind try to run forever without ever turning energy into heat or vice versa.
7 Charles H. Bennett, “Demons, Engines, and the Second Law,” Scientific American 257, no. 5 (November 1987): 108–16.
8 “Use of Mutual Information to Decrease Entropy: Implications for the Second Law of Thermodynamics,” Physical Review A 39 (1989): 5378–86.
9 For the full text of the debate, see http://hotwired.wired.com/synapse/braintennis/97/41/index0a.html.
10 “Universal Quantum Simulators,” Science 273, no. 5278 (Aug. 23, 1996): 1073–78.
11 Nature 406 (Aug. 31, 2000): 1047–54.
12 Norman Margolus and Lev B. Levitin, “The Maximum Speed of Dynamical Evolution,” Physica D 120 (1998): 188–95.
13 Running Word on a PC is not completely equivalent to running it on a Mac, however; Word may run more slowly on one than on the other. Certain versions of Word run famously slowly on the Macintosh. Translations are accurate, but they aren’t always efficient.
14 S. Lloyd, “Measures of Complexity: A Nonexhaustive List,” IEEE Cont. Syst. Mag. 21, no. 4 (2001): 7–8.
15 “Entropy in an Expanding Universe,” Science 217, no. 4560 (Aug. 13, 1982): 593–99.
16 For a pessimistic view of the ultimate future of life, see “The Fate of Life in the Universe,” by Lawrence Krauss and Glen Starkman, Scientific American 281 (November 1999). The authors cite recent observations indicating that the expansion of the universe is accelerating. If this acceleration continues at the observed rate, eventually the amount of available energy within the horizon will go to zero. For a more optimistic view, see “The Ultimate Fate of Life in an Accelerating Universe,” by Katherine Freese and William H. Kinney (http://arXiv.org/astro-ph/0205279). These authors anticipate that the expansion rate will slow and the amount of available energy within the horizon continue to increase.
17 “Time Without End: Physics and Biology in an Open Universe,” Reviews of Modern Physics 51, no. 3 (July 1979): 447–460.
18 To deny the evidence for natural selection is to insult the intelligence of the universe.