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 AZT70164GEMIT,
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).
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, 122 (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, 111, 1965.
An accurate description of algorithmic information
theory together with links to original texts can be found at
http://en.wikipedia.org/wiki/Algorithmic 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:
http://www.idsia.ch/juergen.
See also Max Tegmark: 'Is 'the theory of everything' merely the ultimate ensemble theory?'
Annals of Physics 270, 151 (1998); http://arxiv.org/abs/grqc/9704009.
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, 43360 (1950) (see http://en.wikipedia.org/wiki/Turing 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 17988 (1951).
A classic paper on this topic is J.R. Lucas, 'Minds, Machines and G¬odel,' Philosophy
XXXVI, 112127 (1961); http://users.ox.ac.uk/ 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); http://arxiv.org/abs/physics/0005058,
http://arxiv.org/abs/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, 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), 3235 (1997), http://arxiv.org/abs/quantph/9912088; 'Ultimate Physical Limits
to Computation,' Nature 406, 10471054 (2000), http://arxiv.org/abs/quantph/9908043;
and 'Computational capacity of the universe, Physical Review Letters 88, 237901 (2002),
http://arxiv.org/abs/quantph/0110141.
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/quantph/0501135.
Accounts of the sciences of complexity can be found in The Quark and the Jaguar: Adventures in the Simple and Complex by Murray GellMann, Freeman (1995); Emergence:
From Chaos to Order by John H. Holland, Perseus (1999); and At Home in the
Universe: The Search for Laws of SelfOrganization 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 HalfCentury Survey, R. Herken, ed., pp. 227257, Oxford (1988). The complementary
notion of thermodynamic depth is described in S. Lloyd and H. Pagels, 'Complexity as
Thermodynamic Depth,' Annals of Physics 188, 186213 (1988).
2
