Is the Universe Computable?
One group of scholars would argue that our world cannot be a computer simulation because it includes something that is uncomputable, namely the conscious human mind. Three advocates of this view are John Searle, Hubert Dreyfus and Roger Penrose. They marshal quite different arguments in support of their positions, but all three conclude that no algorithmic process could reproduce everything that goes on in the mind. This idea that consciousness guarantees our reality echoes the Cartesian motto "I think, therefore I am."
For those who see no vital difference between brains and computers, the Searle-Dreyfus-Penrose arguments offer no refuge. But perhaps some other computability constraint will intervene. After all, even if it turns out we can simulate a single human mind, it doesn't necessarily follow that we can simulate the entire visible universe.
Writing a program to simulate even a simple physical system—say a few balls on a billiard table—gives you respect for nature's computational abilities. There is so much to keep track of. If you get careless in your collision-detection algorithm, two billiard balls will glide right through each other—a glitch in the Matrix that is sure to be noticed. Performing such a computation for all the atoms in the universe would be truly daunting.
Jürgen Schmidhuber of the Istituto Dalle Molle di Studi sull'Intelligenza Artificiale in Lugano, Switzerland takes up the question of computability in a recent paper titled "A Computer Scientist's View of Life, the Universe and Everything." He concludes that the simplest strategy for simulating the universe might be to compute all possible universes simultaneously. The program for a typical universe would be long and messy, with many tedious special cases. But a trivial metaprogram avoids these complications. It simply enumerates all possible universe-simulating programs in order of increasing length, and executes them simultaneously by interleaving their instructions.