|Another gem by Wolpert
||[Nov. 4th, 2009|04:12 pm]
The science of complexity and related research
I came across a paper by David H. Wolpert (a researcher I've mentioned before in relation to the no free lunch theorem) This paper is called An incompleteness theorem for calculating the future (NB: The pdf has the pages in reverse order for some reason) and the abstract reads:|
This paper proves that one can not build a computer which can,
for any physical system, take the specification of that system’s state
as input and then correctly predict its future state before that future state
actually occurs. Loosely speaking, this means that one can not build a physical computer
which can be assured of “processing information faster than the universe”.
This result holds even if one restricts one’s attention to predicting the states
of systems which are finite, purely classical, and obey dynamics which is not chaotic,
and even if one uses an infinitely fast, infinitely dense computer.
It's from 1996 and has not been widely cited despite the interesting conclusion:
there are finite, classical systems whose state we humans, even with the aid of electronic computers, can
not compute ahead of time.
There are similar papers elsewhere but it's main contribution seems to be to derive the result without making annoying extra assumptions about the physical system or the computer and that it actually takes "how long does it take to compute?" into account. Sortof a gödel theorem for physics, the author promises us. The author speculates on a physics analogue to the chomsky hierarchy and open problems both computational and philosophical without getting hand-waving and vague. There seems to be some gems in this paper that you can only arrive at through serious theoretical computational science. Take this one for instance:
"“remembering” an event from the past, formally speaking, means predicting that event accurately, using only information from the present"
So how is the claim in the abstract proven? I won't spoil it, but for fans of Douglas Hofstadter and self-referential stuff in general, this should be as obvious as "the butler did it!".
Hint: The computer is also a physical system