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