From: jamesd@netcom.com (James A. Donald)
Date: Fri, 22 Jul 94 21:57:43 PDT
To: rjc@gnu.ai.mit.edu (Ray)
Subject: Re: GUT and P=NP
In-Reply-To: <9407220444.AA20360@geech.gnu.ai.mit.edu>
Message-ID: <199407230457.VAA19186@netcom13.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Ray writes
> 1) By definition, if something can be computed by a turing machine,
> then it is an algorithm (Lewis and Papadimitriou)

Suppose we have a spatial transform performed by light flowing
through a grid.  Is that an algorithm?   Perhaps it is, but I
am about to describe a case that will stretch your definition
of algorithm rather more drastically.


> 2) a quantum computer can be simulated by a TM with exponential 
> slowdown. (claimed by you on the Extropians list, but also
> claimed by Feynmann I believe, not about qm computers, but qm systems
> in general)

True.

> then by (1) and (2), it follows that
> 3) quantum computers are algorithmic (if not, it would contradict
> 2) and possibly 1)

Suppose our quantum system has thirty two bytes.

Then a classical simulation of our quantum system would require
2^257 words of memory

The computer would require more matter than exists in the universe.

Each step of the simulation would require 2^514 steps by the computer,
which even for a computer constructed of very tiny components out
of all the matter in the universe would still require vastly longer
than the entire lifetime of the univers.

> 
>    It doesn't matter how slow the turing machine runs the simulation
> because we allow an arbitrary time along with the infinite tape
> to complete the computation. 
> -Ray

It does not sound like a very useful algorithm, nor is it one
that is easy to describe.

The difference is like the difference in my example of light
flowing through a grid, as against a fourier transform etc,
but the difference is enormously greater.

You say it makes no difference by definition.  I say such
definitions are misleading when we discuss how problems are
to be solved.


-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com