Hal Finney wrote:
>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.
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.
>
>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.
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.
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
Received on Mon Dec 30 2002 - 16:21:20 PST