Friday, February 20, 2009

Wolpert proves that in any such system of universes, quantities exist that cannot be ascertained by any inference device inside the system.

From Scientific American:

Within Any Possible Universe, No Intellect Can Ever Know It All

A mathematical theory places limits on how much a physical entity can know about the past, present or future

By Graham P. Collins

Deep in the deluge of knowledge that poured forth from science in the 20th century were found ironclad limits on what we can know. Werner Heisenberg discovered that improved precision regarding, say, an object’s position inevitably degraded the level of certainty of its momentum. Kurt Gödel showed that within any formal mathematical system advanced enough to be useful, it is impossible to use the system to prove every true statement that it contains. And Alan Turing demonstrated that one cannot, in general, determine if a computer algorithm is going to halt.

David H. Wolpert, a physics-trained computer scientist at the NASA Ames Research Center, has chimed in with his version of a knowledge limit. Because of it, he concludes, the universe lies beyond the grasp of any intellect, no matter how powerful, that could exist within the universe. Specifically, during the past two years, he has been refining a proof that no matter what laws of physics govern a universe, there are inevitably facts about the universe that its inhabitants cannot learn by experiment or predict with a computation. Philippe M. Binder, a physicist at the University of Hawaii at Hilo, suggests that the theory implies researchers seeking unified laws cannot hope for anything better than a “theory of almost everything.”

Wolpert’s work is an effort to create a formal rigorous description of processes such as measuring a quantity, observing a phenomenon, predicting a system’s future state or remembering past information—a description that is general enough to be independent of the laws of physics. He observes that all those processes share a common basic structure: something must be configured (whether it be an experimental apparatus or a computer to run a simulation); a question about the universe must be specified; and an answer (right or wrong) must be supplied. He models that general structure by defining a class of mathematical entities that he calls inference devices.

The inference devices act on a set of possible universes. For instance, our universe, meaning the entire world line of our universe over all time and space, could be a member of the set of all possible such universes permitted by the same rules that govern ours. Nothing needs to be specified about those rules in Wolpert’s analysis. All that matters is that the various possible inference devices supply answers to questions in each universe. In a universe similar to ours, an inference device may involve a set of digital scales that you will stand on at noon tomorrow and the question relate to your mass at that time. People may also be inference devices or parts of one.

Wolpert proves that in any such system of universes, quantities exist that cannot be ascertained by any inference device inside the system. Thus, the “demon” hypothesized by Pierre-Simon Laplace in the early 1800s (give the demon the exact positions and velocities of every particle in the universe, and it will compute the future state of the universe) is stymied if the demon must be a part of the universe.

Researchers have proved results about the incomputability of specific physical systems before. Wolpert points out that his result is far more general, in that it makes virtually no assumptions about the laws of physics and it requires no limits on the computational power of the inference device other than it must exist within the universe in question. In addition, the result applies not only to predictions of a physical system’s future state but also to observations of a present state and examining a record of a past state.

The theorem’s proof, similar to the results of Gödel’s incompleteness theorem and Turing’s halting problem, relies on a variant of the liar’s paradox—ask Laplace’s demon to predict the following yes/no fact about the future state of the universe: “Will the universe not be one in which your answer to this question is yes?” For the demon, seeking a true yes/no answer is like trying to determine the truth of “This statement is false.” Knowing the exact current state of the entire universe, knowing all the laws governing the universe and having unlimited computing power is no help to the demon in saying truthfully what its answer will be.

In a sense, however, the existence of such a paradox is not exactly earth-shattering. As Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology, puts it: “That your predictions about the universe are fundamentally constrained by you yourself being part of the universe you’re predicting, always seemed pretty obvious to me—and I doubt Laplace himself would say otherwise if we could ask him.” Aaronson does allow, though, that it is “often a useful exercise to spell out all the assumptions behind an idea, recast everything in formal notation and think through the implications in detail,” as Wolpert has done. After all, the devil, or demon, is in the details.

Editor's Note: This story was originally printed with the title "Impossible Inferences"

No comments: