Hal Finney wrote:
Whoops, I've heard of the P=NP problem but I guess I was confused about what it meant. But there are some problems where candidate solutions can be checked much faster than new solutions can be generated, no? If you want to know whether a number can be factorized it's easy to check candidate factors, for example, although if the answer is that it cannot be factorized because the number is prime I guess there'd be no fast way to check if that answer is correct.One correction, there are no known problems which take exponential time but which can be checked in polynomial time. If such a problem could be found it would prove that P != NP, one of the greatest unsolved problems in computability theory.
But whatever the degree of risk that the machine will malfunction over any set amount of time, it seems to me that one could always make that risk smaller and smaller over time by building more and more backup machines, so that in the limit the accumulated probability of a malfunction could still be kept small. I haven't thought this through too carefully though.Since Moravec's machine uses time travel, or at least information transfer into the past, it is obviously extremely speculative. But given that, I think your idea does make sense in theory, that if there were an infinite amount of computing power possible in the future, and we sent a signal into the past if a given program ever halted, then the absence of such a signal would imply that the program did not halt.Of course any kind of practical engineering that involves infinities is even more speculative than time travel. You have to assume that a signal can be sent an infinite distance through time, that the future calculation goes on forever and never ends, and so on. It seems difficult to imagine such a degree of consistency and reliability in the imperfect universe where we live.
Anyway, however far-fetched the proposal is, if it could work even in principle it would be relevant to the question of whether quantum gravity allows uncomputable functions to be realized. General relativity does have solutions in which backwards time travel is possible, although I don't know how likely it is that this will remain true in a theory of quantum gravity (is it known if this is true in string theory?) But if it did, and if the theory also did not in principle forbid computing power to increase without limit (perhaps it would forbid it--for example, I'm not sure if Tipler's proposal would work if spacetime were quantized), then this would suggest the laws of physics are uncomputable, even if such a scheme is never actually realized in our universe.
This is also somewhat relevant to "theories of everything" since we might want to ask if somewhere in the set of "all possible universes" there exists one where time travel is possible and computing power increases without bound. If the answer is yes, that might suggest that any TOE based on "all possible computations" is too small to accomodate a really general notion of all possible universes. But it might be possible to arrange things so that one would experience living in such a universe from a first-person POV while your TOE is still based on some notion of all possible computations (as with the universal dovetailer)--one could start out computing different histories in which different possible "messages from the future" are recieved, and then continually spit out copies of the histories where no inconsistency has yet appeared while not doing the same for histories where an inconsistency does crop up, so that in the limit as time goes to infinity the first-person probability of finding oneself in an inconsistent history becomes vanishingly small compared to the probability of finding oneself in a consistent one.
Jesse
_________________________________________________________________
MSN 8 with e-mail virus protection service: 3 months FREE*. http://join.msn.com/?page=features/virus&xAPID=42&PS=47575&PI=7324&DI=7474&SU= http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_eliminateviruses_3mf
