?

Log in

Another gem by Wolpert - Complexity research [entries|archive|friends|userinfo]
The science of complexity and related research

[ website | A science at 30 ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Another gem by Wolpert [Nov. 4th, 2009|04:12 pm]
The science of complexity and related research

all_complexity

[shamebear]
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
LinkReply

Comments:
[User Picture]From: 403
2009-11-04 04:20 pm (UTC)
Good timing. Someone brought up the subject in my Intro to Chaos class yesterday.
(Reply) (Thread)
[User Picture]From: shamebear
2009-11-04 04:28 pm (UTC)
Great! :-) There's a lot of good discussion material in papers like this
(Reply) (Parent) (Thread)
[User Picture]From: _candide_
2009-11-06 02:19 pm (UTC)
I'm looking forward to reading it!

BTW, care to clarify what you mean by the, "chomsky hierarchy?" It's not sounding familiar to me. (And since language & linguistics is something of a hobby of mine, I do know who Noam is. ^_^)


Of course, the one flaw in cavalier philosophical interpretations of Wolpert's work is ignoring approximation. Not that you'd do that, sir. However, there are many who would make that assumption implicitly. You and I both know, though, that you can get quite far using some accurate approximations. ^_^

After all, what is Physics but the Art of Accurate Approximation? ;)
(Reply) (Thread)
[User Picture]From: shamebear
2009-11-06 09:23 pm (UTC)
The chomsky hiearchy is one of those things I think I know it until I try to explain it. :-) So I think I'll have to resort to
wikipedia: http://en.wikipedia.org/wiki/Chomsky_hierarchy

It's true, there's no such thing as "approximation" in kolmogorov complexity or most notions of computation, which makes it difficult to translate these things into philosophy, or physics for that matter :-)
(Reply) (Parent) (Thread)