Re: Time Machines, FTL, and P=NP

On 19 veebr, 23:10, Michael Ash <m...@[EMAIL PROTECTED]
> wrote:
> Harry Erwin <her...@[EMAIL PROTECTED]
> wrote:
> > Aaronson's article in the March 2008 points out that a universe with
> > time machines (and/or FTL) has PSPACE = P. Note that PSPACE is a
> > superset of NP.
>
> It'll depend on what sort of time travel you get, but generally you'll
be
> able to perform infinite computation in finite time. The only reason
this
> doesn't solve the Halting Problem is because you don't have infinite
> storage. It does let you solve the version of the Halting Problem
extended
> to real, space-limited hardware. This is technically in PSPACE but in a
> practical sense is unsolveable for any non-trivial hardware. The ability
> to build oracles, even limited oracles that assume finite storage, would
> change a lot.
>
How much storage does an oracle need to be programmatically useful at
all?

Suppose that you have a laptop which contains four wormholes - two in
one corner and two in diagonally opposite corner. The wormholes are
two wormhole pairs such that each wormhole pair individually does not
contain a closed lightlike curve, but the two pairs combined do
contain that.

As the diagonal of your laptop is about 30 cm, the oracle can receive
signals send about 2 ns from future.

If you are able to write a program which receives the message, checks
it against a condition and sends it into past all in 1 ns, then you
can deliver your message 1 ns towards past every cycle. So, you can
receive a message sent tomorrow some 86 billions and 400 milliards of
cycles later.

But how would you write programs where you have oracle function at
your disposal?