Dear Bruno,
Interleaving.
- Original Message -
From: Marchal Bruno [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Monday, December 30, 2002 8:26 AM
Subject: Re: Quantum Probability and Decision Theory
Stephen Paul King wrote:
There do exist strong arguments that the
Dear Jesse,
Please read the below referenced paper. It shows that QM comp *CAN*
solve an undecidable problem
(relative to a classical computer). I do not see how I misread Feynman's
claim, but I do admit that the quotation what I reproduced is insufficient
to support my claim. It is not an
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
claim
Again, the paper says:
Is there any hope for
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
Stephen Paul King references:
http://www.cs.auckland.ac.nz/~cristian/coinsQIP.pdf
whose abstract begins,
Is there any hope for quantum computer to challenge the Turing barrier,
i.e., to solve an undecidable problem, to compute an uncomputable
function? According to Feynman's '82 argument, the
When a finite quantum computer can break the Turing barrier, that will
prove something. But when your first step is to prepare an infinite
superposition, that has no applicability to the physical universe.
Hal Finney
Precisely. Deutsch's arguments make a lot of assumptions about things
Dear Jesse,
- Original Message -
From: Jesse Mazer [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Monday, December 30, 2002 11:40 AM
Subject: Re: Quantum Probability and Decision Theory
Stephen Paul King wrote:
Dear Jesse,
Please read the below referenced paper. It shows
On Monday, December 30, 2002, at 09:38 AM, Hal Finney wrote:
We discussed this article briefly in July. Calude relies on infinite
dimensional Hilbert space with the inputs prepared in an infinite
superposition. Without claiming to understand all the details, this
looks to me like it would
Dear Hal,
You make a very good point! Thank you for actually reading Calude et
al's paper. ;-) But, I have one nagging question: is the requirement of the
existence of an infinite superposition more or less hard to swallow than
Bruno's arithmetical truth?
I don't see how arithmetical
There go 7 cents out of my 60!...
The case indeed is that if you build a quantum computer by emulating
a Turing-Universal Machine you are a priori circunscribing its own
class of algorithms. That is only natural if that is the largest class of
computable problems you think are worthwhile
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?
[SPK]
In the abstract of http://www.cs.auckland.ac.nz/~cristian/coinsQIP.pdf
Ben Goertzel wrote:
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
Jesse Mazer writes:
I had a science-fictional idea about a way to build an oracle machine after
reading Hans Moravec's article on Time Travel and Computing here:
http://www.frc.ri.cmu.edu/users/hpm/project.archive/general.articles/1991/TempComp.html
As I understood it, the basic idea here
On Monday, December 30, 2002, at 11:57 AM, Jesse Mazer wrote:
As I understood it, the basic idea here was to use the fact that
history must work out consistently to get a machine that could solve
problems much faster than a Turing machine. For example, for any
problem that requires
Hal Finney wrote:
One correction, there are no known problems which take exponential time
but which can be checked in polynomial time. If such a problem could be
found it would prove that P != NP, one of the greatest unsolved problems
in computability theory.
Whoops, I've heard of the P=NP
On Monday, December 30, 2002, at 01:18 PM, Jesse Mazer wrote:
Hal Finney wrote:
One correction, there are no known problems which take exponential
time
but which can be checked in polynomial time. If such a problem could
be
found it would prove that P != NP, one of the greatest unsolved
On 30-Dec-02, you wrote:
Dear Stephen,
...
[Bruno]It is perhaps up to you to show me a quantum computable
function not
being classicaly computable. But if you succeed you will give me
something like an unitary transformation, and then I will show you
how to write a classical program
Hal Finney:
there are no known problems which take
exponential time but which can be checked
in polynomial time. If such a problem could
be found it would prove that P != NP ...
Communications glitch here. The definition
of NP is problems that can be solved in
polynomial time on a
On 31-Dec-02, Hal Finney wrote:
One correction, there are no known problems which take exponential
time but which can be checked in polynomial time. If such a problem
could be found it would prove that P != NP, one of the greatest
unsolved problems in computability theory.
What about
Brent Meeker wrote:
On 31-Dec-02, Hal Finney wrote:
One correction, there are no known problems which take exponential
time but which can be checked in polynomial time. If such a problem
could be found it would prove that P != NP, one of the greatest
unsolved problems in computability
Hans Moravec writes:
Hal Finney:
there are no known problems which take
exponential time but which can be checked
in polynomial time. If such a problem could
be found it would prove that P != NP ...
Communications glitch here. The definition
of NP is problems that can be solved in
On Monday, December 30, 2002, at 03:46 AM, Brent Meeker wrote:
On 31-Dec-02, Hal Finney wrote:
One correction, there are no known problems which take exponential
time but which can be checked in polynomial time. If such a problem
could be found it would prove that P != NP, one of the
Tim May writes:
IF the MWI universe branchings are at all communicatable-with, that is,
at least _some_ of those universes would have very, very large amounts
of power, computer power, numbers of people, etc. And some of them, if
it were possible, would have communicated with us, colonized
Hal Finney:
I'm not sure if you are disagreeing with either of my statements above,
that (1) there are no known problems which take exponential time but
which can be checked in polynomial time, or that (2) if such a problem
could be found it would prove that P != NP.
Ah, I see the
http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node23.html
... It is suspected but not yet known that factoring is NP-complete.
Of course, if factoring were to be shown NP-complete
and quantum computers could be built to run Shor's
factoring algorithm in polynomial time, then quantum
On 31-Dec-02, you wrote:
Hans Moravec writes:
Hal Finney:
there are no known problems which take
exponential time but which can be checked
in polynomial time. If such a problem could
be found it would prove that P != NP ...
OK, you mean that *provably* take exponential time.
...
As
Brent Meeker:
It seems [factoring] has been proven recently to be in P:
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html#PRIMES
No, that's primality testing, which has always been
much easier than factoring.
hi all. Ive been poking at computational complexity theory to various
degrees for close to a decade.
the recent comments on the subject are interesting its not
surprising it has popped up on this list.
I believe complexity theory is going to shed some deep
new light on physics, and has already
Dear Hans, Bret and Friends,
I submit this paper by S. Wolfram on intractability and undecidability
that you all might find of interest:
http://www.stephenwolfram.com/publications/articles/physics/85-undecidabilit
y/2/text.html
Please note the part that discusses coordinate
Dear Joao,
Interleaving.
- Original Message -
From: Joao Leao [EMAIL PROTECTED]
To: Ben Goertzel [EMAIL PROTECTED]
Cc: Hal Finney [EMAIL PROTECTED]; [EMAIL PROTECTED]
Sent: Monday, December 30, 2002 2:11 PM
Subject: Re: Quantum Probability and Decision Theory
There go 7 cents out
hi all. re: the exponential vs polynomial time thread.
imho HFs comments could be interpreted as roughly correct
but stated in a very confusing way I would say, hence
the ensuing confusion. lets give this another shot.
there are no problems for which it has been proven that
there is a **lower
31 matches
Mail list logo
