Wei Dai (
Wed, 6 May 1998 11:28:20 -0700

On Wed, May 06, 1998 at 10:29:46AM -0700, Hal Finney wrote:
> You don't get contradictions, but you do get paradoxes in the sense of
> things which are so contrary to intuition that you almost can't believe
> that they happen.
> There was an article in Extropy many years ago about electronic circuits
> which depended on time travel. It looked like it would be possible to
> do significant amounts of computation in zero time. You set up a system
> which will be inconsistent unless a certain equation is satisfied, and
> presto, the non-contradiction principle automatically means that the
> system satisfies the equation.

Can you also use this device to solve the Halting Problem? I.e., set up a
system with two possible states, one consistent with a Turing machine
halting and another one consistent with the machine not halting? If so we
can rule out the possibility that this device can be physical by assuming
that the universe has a low algorithmic complexity.

> Time travel computers would put quantum computers to shame. Any NP
> problem (that is, any one whose answer can be checked easily, like
> factoring) can be solved in constant time.
> There is a classic sci-fi story in which (to simplify slightly) the
> man who will be known as the inventor of the time machine didn't invent
> it, he was given it by a future version of himself. This would seemingly
> be consistent and has no contradictions, but it is paradoxical that
> a complex device like this would have no inventor.

It wouldn't be so paradoxical if the universe is capable of doing infinite
amount of computation in zero time, since you can think of device as being
computed by the universe at the point of time it is received by the