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, Bantam (1984); J.D. Barrow, Theories of Everything, Oxford University Press (1991); and F.J. Tipler, The Physics of Immortality, Macmillan, London (1995).

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; English language version: Calculating Space, MIT Technical Translation AZT-70-164-GEMIT, MIT (Proj. MAC), Cambridge, Mass. 02139, February 1970, zuse.html). Fredkin's work can be found at

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

The history of the image of monkeys typing on a typewriter can be found in the Wikipedia. For the mathematics behind monkeys typing on computers, see R.J. Solomonoff, 'A formal theory of inductive inference,' Information and Control 7, 1-22 (1964); G.J. Chaitin, Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987; A.N. Kolmogorov, 'Three approaches to the quantitative definition of information,' Problems of Information Transmission 1, 1-11, 1965.

An accurate description of algorithmic information theory together with links to original texts can be found at information theory.

Further discussion of the concept of algorithmic information and its relationship to the generation of complexity can be found the writings of Juergen Schmidhuber: See also Max Tegmark: 'Is 'the theory of everything' merely the ultimate ensemble theory?' Annals of Physics 270, 1-51 (1998);

The idea that the undecidability and the halting problem are related to the problem of free will was suggested by Turing in his article, 'Computing Machinery and Intelligence,' Mind, 433-60 (1950) (see test for the original article and further discussion). See also K. R. Popper, 'Indeterminism in Quantum Physics and Classical Physics,' British Journal for Philosophy of Science 1 179-88 (1951). A classic paper on this topic is J.R. Lucas, 'Minds, Machines and G¬odel,' Philosophy XXXVI, 112-127 (1961); jrlucas/Godel/mmg.html. More recent explorations of free will include Daniel Dennett's Elbow Room: The Varieties of Free Will Worth Wanting, MIT Press (1984), and Freedom Evolves, Viking (2003).

An exploration 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);,

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, ed. J.J. Halliwell, J. P«erez Mercader, W.H. Zurek, eds., Cambridge University Press (1996), is a collection of scientific articles on the subject.

Many of the classic papers on quantum mechanics are collected, with commentary, in Quantum theory and measurement, J.A. Wheeler, W.H. Zurek, eds., 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).

An introduction to quantum mechanics and quantum computation can be found in A Shortcut Through Time: The Path to the Quantum Computer, G. Johnson, Vintage (2004).

The standard textbook on quantum computers is Quantum Computation and Quantum Information, M.A. Nielsen, 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), 32-35 (1997),; 'Ultimate Physical Limits to Computation,' Nature 406, 1047-1054 (2000),; and 'Computational capacity of the universe, Physical Review Letters 88, 237901 (2002),

A popular account of quantum gravity is Three Roads to Quantum Gravity, 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, D. Pines, ed., Addison Wesley (1987); and 'Logical Depth and Physical Complexity,' in The Universal Turing Machine, A Half-Century Survey, R. Herken, ed., pp. 227-257, Oxford (1988). The complementary notion of thermodynamic depth is described in S. Lloyd and H. Pagels, 'Complexity as Thermodynamic Depth,' Annals of Physics 188, 186-213 (1988). 2

Programming the Universe