Jesse & Stephen:
About quantum computing getting around the limitations of Turing machines:
you don't have to cite Feynman, this matter was settled fairly clearly in
David Deutsch's classic work on quantum computation. He showed that the
only quantum-computable functions are Turing-computable functions. Quantum
computers may be able to compute some things *faster* than classical
computers (in the average case), but this is a different story.
In his book Shadows of the Mind, Penrose reacts to this result with
disappointment, and with an expression of hope that "quantum gravity
computers" will be able to compute non-Turing-computable functions. But so
far neither he nor anyone else has offered much more than hope and
speculation in this direction. My own opinion is that this is probably a
pipe dream, and we must make do with Turing-computable functions, but I'm of
course open to new ideas and new information...
-- Ben Goertzel
> -----Original Message-----
> From: Jesse Mazer [mailto:[EMAIL PROTECTED]]
> Sent: Monday, December 30, 2002 11:41 AM
> To: [EMAIL PROTECTED]
> Subject: Re: Quantum Probability and Decision Theory
> Stephen Paul King wrote:
> >Dear Jesse,
> > Please read the below referenced paper. It shows that QM
> comp *CAN* "
> >"solve an undecidable problem"
> > (relative to a classical computer)."
> Where does it say that?
> >I do not see how I misread Feynman's
> Again, the paper says:
> "Is there any hope for quantum computing to challenge the Turing barrier,
> i.e., to solve an undecidable problem, to compute an uncomputable
> According to Feynman's argument ... the answer is negative."
> That seems pretty clear to me--if the answer is negative, that
> means there
> is *not* "any hope for quantum computing to challenge the Turing
> Do you understand "negative" to mean something different?
> MSN 8 limited-time offer: Join now and get 3 months FREE*.