- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Hal Finney <hal.domain.name.hidden>

Date: Mon, 30 Dec 2002 12:37:51 -0800

Jesse Mazer writes:

*> I had a science-fictional idea about a way to build an oracle machine after
*

*> reading Hans Moravec's article on "Time Travel and Computing" here:
*

*>
*

*> http://www.frc.ri.cmu.edu/users/hpm/project.archive/general.articles/1991/TempComp.html
*

*>
*

*> As I understood it, the basic idea here was to use the fact that history
*

*> must work out consistently to get a machine that could solve problems much
*

*> faster than a Turing machine. For example, for any problem that requires
*

*> exponential time to reach a solution but for which possible solutions can be
*

*> checked in polynomial time, you could have the machine pick a possible
*

*> solution at random, then check to see if the solution actually works, then
*

*> if it *doesn't* work it sends back a sort of override command that changes
*

*> the original guess, which would create an inconsistency. The only consistent
*

*> history in this case would be one where the machine's first guess happened
*

*> to be correct, so if history is indeed constrained to be consistent, you are
*

*> guaranteed to get the correct answer on the first guess.
*

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.

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.

Hal Finney

Received on Mon Dec 30 2002 - 15:40:10 PST

Date: Mon, 30 Dec 2002 12:37:51 -0800

Jesse Mazer writes:

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.

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.

Hal Finney

Received on Mon Dec 30 2002 - 15:40:10 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*