There are two sides to this question that may be clouding the
argument and maybe suggest a change in thread. Here go my 2 cents:
1) Yes, indeed there is no hope that a Quantum Computer _as we
understand it today_ (and I underscore this last point) is likely to
violate the Turing's Halting Theorem for example and that is
a stronger statement than any reference to the Church-Turing
thesis which, after all, is only an heuristic presumption...
2) But it is also a fact that Quantum Computers, in the Benioff-Feynman-
Deutsch model are constructed having in mind the Turing Machine model
of computation and that may not be the most general one conceivable. Even
before QC people have proposed other models which would not be bound
by the "limitations" of the Turing Model (see Boolos & Jeffrey "Computability
and Logic" for an example of one such avatar called the "Zeus machine".
Granted these are not "physical models" but neither is the Turing Machine!
All physical computers are Finite Automata of some sort, as everyone knows...
Now the 69 cent question is: can Quantu Mechanics provide us with a
trans-Turing model of computation with some hope of physical realization?
Now, I am only paying my 2 cents of wisdom so don't count on my answering
this one....
Cordially,
-Joao Leao
P.S. - Happy New Year Everybody on Everything...
Jesse Mazer wrote:
> Stephen Paul King wrote:
>
> >>Also, any quantum computer or physical system can be simulated by a
> >>classical computer.
> >
> >[SPK]
> >
> > Bruno has made similar statements and I do not understand how this is
> >true. I have it from multiple sources that this is not true. Do you recall
> >the famous statement by Richard Feynman regarding the "exponential
> >slowdown"
> >of classical system attempting to simulate QM systems?
>
> It is true that classical computers will take an exponentially long time to
> simulate quantum ones, but as far as I know it's still true that there are
> no problems that are solvable by a quantum computer that cannot also be
> solved by a classical computer (possibly much more slowly).
>
> >Let me quote from a
> >paper by Karl Svozil et al: http://tph.tuwien.ac.at/~svozil/publ/embed.htm
> >
> >
> I don't see how this supports your argument either.
>
> --Jesse
>
> _________________________________________________________________
> Add photos to your e-mail with MSN 8. Get 3 months FREE*.
> http://join.msn.com/?page=features/featuredemail&xAPID=42&PS=47575&PI=7324&DI=7474&SU=
> http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_addphotos_3mf
--
Joao Pedro Leao ::: jleao.domain.name.hidden
Harvard-Smithsonian Center for Astrophysics
1815 Massachussetts Av. , Cambridge MA 02140
Work Phone: (617)-496-7990 extension 124
VoIP Phone: (617)=384-6679
Cell-Phone: (617)-817-1800
----------------------------------------------
"All generalizations are abusive (specially this one!)"
-------------------------------------------------------
Received on Mon Dec 30 2002 - 12:11:29 PST