Re: R: Quantum Probability and Decision Theory

[Joao Leao]

The Borromean ring analogy to the GHZ state is due to Aravind.
On the same thematic, i.e., that there may be a simple topological
analogy to the structure of multipartite entanglement there are
a couple of papers by Zapatrin:

 http://arXiv.org/abs/quant-ph/0211077
http://arXiv.org/abs/quant-ph/0207058

along different lines from Kauffmann and Lomonaco.


scerir wrote:

> [scerir]
> > As far as I know you can describe certain classes of entanglement
> > by means of Borromean rings, which are beautiful and sometimes
> > also unpredictable.
>
> I realize that Kauffman already wrote something ...
> http://www.math.uic.edu/~kauffman/QETE.pdf

--

Joao Pedro Leao  :::  [EMAIL PROTECTED]
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!)"
---

R: Quantum Probability and Decision Theory

[scerir]

[scerir] 
> As far as I know you can describe certain classes of entanglement
> by means of Borromean rings, which are beautiful and sometimes
> also unpredictable. 

I realize that Kauffman already wrote something ... 
http://www.math.uic.edu/~kauffman/QETE.pdf

R: Quantum Probability and Decision Theory

[scerir]

[Joao Leao]
What we lack is a genuinely quantum model of
computation that could be mathematically tractable as the Turing or Post
models and can account for entanglement in all its glory.

As far as I know you can describe certain classes of entanglement
by means of Borromean rings, which are beautiful and sometimes
also unpredictable. That is not much indeed, just something!
http://www.liv.ac.uk/~spmr02/rings/
http://paradise.caltech.edu/~cook/Workshop/Math/Borromean/Borrring.html
http://astronomy.swin.edu.au/~pbourke/surfaces/borromean/
http://seemanlab4.chem.nyu.edu/borro.html

Brunniam links are also interesting in connection with QM and QC.
http://www.cs.ubc.ca/nest/imager/contributions/scharein/brunnian/brunnian.ht
ml
http://members.tripod.com/vismath5/bor/bor7.htm

Happy N.Y. (which is already coming, here in Rome)

s.

Re: R: Quantum Probability and Decision Theory

[Stephen Paul King]

Dear Joao and Friends,

Since you mentioned the word "resource", let me add this paper by C.
Caves et al to the list of "must read" papers on QC.

http://arxiv.org/abs/quant-ph/0204157

from the abstract:
Climbing Mount Scalable: Physical-Resource Requirements for a Scalable
Quantum Computer
Authors: Robin Blume-Kohout (1), Carlton M. Caves (2), Ivan H. Deutsch (2)
((1) Los Alamos National Laboratory, (2) University of New Mexico)
Comments: LATEX, 24 pages, 1 color .eps figure. This new version has been
accepted for publication in Foundations of Physics

  The primary resource for quantum computation is Hilbert-space dimension.
Whereas Hilbert space itself is an abstract construction, the number of
dimensions available to a system is a physical quantity that requires
physical resources. Avoiding a demand for an exponential amount of these
resources places a fundamental constraint on the systems that are suitable
for scalable quantum computation. To be scalable, the effective number of
degrees of freedom in the computer must grow nearly linearly with the number
of qubits in an equivalent qubit-based quantum computer.

In a related question, is anyone here familiar with the problem of
defining a Lebesgue measure for a infinitely dimensional Hilbert space?

http://www.lns.cornell.edu/spr/2000-04/msg0023750.html

Kindest regards,

Stephen

- Original Message -
From: "Joao Leao" <[EMAIL PROTECTED]>
To: "scerir" <[EMAIL PROTECTED]>
Cc: <[EMAIL PROTECTED]>
Sent: Tuesday, December 31, 2002 10:02 AM
Subject: Re: R: Quantum Probability and Decision Theory


> I don't agree with Tim's suggestion  that infinite-dimensional Hilbert
spaces
> are somewhat "ancilliary" in QM and that all systems are calculable in
> finite dimensional modes. In fact infinite sets of spaces are the rule in
> QM and
> the finite dimensional subspaces only serve as toy systems.
>
> Having said that, yes: entanglement is the "maximal peculiarity" of
quantum
> systems and it is more or less established that entanglement is the
"resource"
> that is reponsible for the quantum computational speed up. That does not
> necessarily mean that it would lead to the "computational of the (Turing)
> uncomputable" but it is the natural place to look. The KSW states
described
> in the paper you mention below are certainly worth investigating but
finitely
> entangled states already display most of the capabilities (teleportation,
dense
> coding, speed up, non-locality) that we came to associate with quantum
> information processing. What we lack is a genuinely quantum model of
> computation that could be mathematically tractable as the Turing or Post
> models and can account for entanglement in all its glory.
>
> -Joao Leao
snip

Re: R: Quantum Probability and Decision Theory

[Joao Leao]

I don't agree with Tim's suggestion  that infinite-dimensional Hilbert spaces
are somewhat "ancilliary" in QM and that all systems are calculable in
finite dimensional modes. In fact infinite sets of spaces are the rule in
QM and
the finite dimensional subspaces only serve as toy systems.

Having said that, yes: entanglement is the "maximal peculiarity" of quantum
systems and it is more or less established that entanglement is the "resource"
that is reponsible for the quantum computational speed up. That does not
necessarily mean that it would lead to the "computational of the (Turing)
uncomputable" but it is the natural place to look. The KSW states described
in the paper you mention below are certainly worth investigating but finitely
entangled states already display most of the capabilities (teleportation, dense

coding, speed up, non-locality) that we came to associate with quantum
information processing. What we lack is a genuinely quantum model of
computation that could be mathematically tractable as the Turing or Post
models and can account for entanglement in all its glory.

-Joao Leao

scerir wrote:

> [Tim May, in another thread]
> Any finite system, which of course all systems are, can have all of its
> quantum mechanics calculations done with finite-dimensional vector
> spaces. The "full-blown machinery" of an infinite-dimensional Hilbert
> space is nice to have, in the same way that Fourier analysis is more
> elegantly done with all possible frequencies even though no actual
> system (including the universe!) needs all frequencies.
>
> [J. Leao]
> Another point worth making is that it seems unlikely that the recourse
> to the infinite superposability of quantum states is going to be of any
> help in this circunstance. It may be more profitable to look to
> entanglement (which incidentaly is the trully novelty that QC brings
> to the realm of computation) as the road to a trans-Turing class of
> computations.
>
> [SPK]
> Entanglement is somewhat involved. See this paper:
> http://www.arxiv.org/abs/quant-ph/0201143
>
> And what about these "infinitely entangled states"?
> s.
>
> M. Keyl, D. Schlingemann, R. F. Werner
> http://arxiv.org/abs/quant-ph/0212014
> For states in infinite dimensional Hilbert spaces entanglement quantities
> like the entanglement of distillation can become infinite. This leads
> naturally to the question, whether one system in such an infinitely
> entangled state can serve as a resource for tasks like the teleportation of
> arbitrarily many qubits. We show that appropriate states cannot be obtained
> by density operators in an infinite dimensional Hilbert space. However,
> using techniques for the description of infinitely many degrees of freedom
> from field theory and statistical mechanics, such states can nevertheless be
> constructed rigorously. We explore two related possibilities, namely an
> extended notion of algebras of observables, and the use of singular states
> on the algebra of bounded operators. As applications we construct the
> essentially unique infinite analogue of maximally entangled states, and the
> singular state used heuristically in the fundamental paper of Einstein,
> Rosen and Podolsky.

--

Joao Pedro Leao  :::  [EMAIL PROTECTED]
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!)"
---

R: Quantum Probability and Decision Theory

[scerir]

[Tim May, in another thread]
Any finite system, which of course all systems are, can have all of its
quantum mechanics calculations done with finite-dimensional vector
spaces. The "full-blown machinery" of an infinite-dimensional Hilbert
space is nice to have, in the same way that Fourier analysis is more
elegantly done with all possible frequencies even though no actual
system (including the universe!) needs all frequencies.

[J. Leao]
Another point worth making is that it seems unlikely that the recourse
to the infinite superposability of quantum states is going to be of any
help in this circunstance. It may be more profitable to look to
entanglement (which incidentaly is the trully novelty that QC brings
to the realm of computation) as the road to a trans-Turing class of
computations.

[SPK]
Entanglement is somewhat involved. See this paper:
http://www.arxiv.org/abs/quant-ph/0201143



And what about these "infinitely entangled states"?
s.

M. Keyl, D. Schlingemann, R. F. Werner
http://arxiv.org/abs/quant-ph/0212014
For states in infinite dimensional Hilbert spaces entanglement quantities
like the entanglement of distillation can become infinite. This leads
naturally to the question, whether one system in such an infinitely
entangled state can serve as a resource for tasks like the teleportation of
arbitrarily many qubits. We show that appropriate states cannot be obtained
by density operators in an infinite dimensional Hilbert space. However,
using techniques for the description of infinitely many degrees of freedom
from field theory and statistical mechanics, such states can nevertheless be
constructed rigorously. We explore two related possibilities, namely an
extended notion of algebras of observables, and the use of singular states
on the algebra of bounded operators. As applications we construct the
essentially unique infinite analogue of maximally entangled states, and the
singular state used heuristically in the fundamental paper of Einstein,
Rosen and Podolsky.

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

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 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 considering. But it
> isn't necessarily the only one. This approach surfaces here and there
> in the literature. See for example:
>
> http://arXiv.org/abs/quant-ph/0205093
>

[SPK]

Nice paper! I will be adding this one to my homework. Thank you! What we
need is a good general definition of what exactly is a QM computation that
we can all agree on.

> Another point worth making is that it seems unlikely that the recourse
> to the infinite superposability of quantum states is going to be of any
> help in this circunstance. It may be more profitable to look to
> entanglement (which incidentaly is the trully novelty that QC brings
> to the realm of computation) as the road to a trans-Turing class of
> computations.
>

[SPK]

Entanglement is somewhat involved. See this paper:

http://www.arxiv.org/abs/quant-ph/0201143


> As to your reference to Penrose, Ben, I should probably add that
> his much maligned ideas concerning the possibility of using Quantum
> Gravity as a basis for understanding the psychology of mathematical
> invention are perhaps worth a second look now that we are learning a
> good deal more about quantum information in Black Holes etc...

[SPK]

I am a deep admirer of Penrose. It was his ideas that awoke me to QM
comp as a possible way of modeling the psyche.

Kindest regards,

Stephen

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

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 reparametrizations"
between finitely specified 4-manifolds ... ;-)

Kindest regards,


Stephen

- Original Message -
From: "Hans Moravec" <[EMAIL PROTECTED]>
To: "Brent Meeker" <[EMAIL PROTECTED]>; "Everything-list"
<[EMAIL PROTECTED]>
Cc: "Hans Moravec" <[EMAIL PROTECTED]>
Sent: Monday, December 30, 2002 9:39 PM
Subject: Re: Quantum Probability and Decision Theory


> 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.
>
>

Re: Quantum Probability and Decision Theory

[Hans Moravec]

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.

Re: Quantum Probability and Decision Theory

[Brent Meeker]

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 I understand the state of play, factoring into primes is not
> known to be NP-complete, but the contrary is not known, either.
> Factoring is strongly suspected not to be NP-complete but that has
> not been proven. So it is still possible that factoring into primes
> is just as hard as the TSP, although it is thought to be unlikely
> (it would imply that NP = coNP).

It seems it has been proven recently to be in P:
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html#PRIMES

Brent Meeker
"One cannot guess the real difficulties of a problem before
having solved it."
   --- Carl Ludwig Siegel

Re: Quantum Probability and Decision Theory

[Hans Moravec]

>> ... 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
computers could solve all NP-complete problems in
polynomial time.  Big advance for quantum computation.

Re: Quantum Probability and Decision Theory

[Hans Moravec]

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 communications glitch was at my end!

You were being precise: NP-complete is not
known (for sure) to be exponentially hard,
so NP-complete problems are not counterexamples
to statement (1)

But maybe (2) doesn't follow.
There must be problems where checking some
negative cases (in the TSP sense) takes more
than polynomial time (maybe doesn't terminate),
but positive answers can be checked in polynomial
time.  Those would fit the criteria, but not
be in NP. (Trying to make one up ...)


As I understand the state of play, factoring into primes is not known
to be NP-complete, but the contrary is not known, either.  Factoring is
strongly suspected not to be NP-complete but that has not been proven.
So it is still possible that factoring into primes is just as hard as
the TSP, although it is thought to be unlikely (it would imply that
NP = coNP).


Right again, though apparently opinions differ about the unknowns:


>> ... It is suspected but not yet known that factoring is NP-complete.

Re: Quantum Probability and Decision Theory

[Tim May]

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 greatest
unsolved problems in computability theory.


What about Hamiltonian circuits or factoring an integer or roots of a
Diophantine equation?


Hal will probably answer. I initially had the same reaction you had 
(except only about Hamiltonian cycles and roots of Diophantines, but 
not factoring, as factoring is not known to be NP-complete).

But upon rereading what Hal wrote, and what I had already drafted a 
nearly complete reply to, I saw that he was making the subtle point 
that there are "no known problems which take exponential time."

All of the NP-complete problems (Hamiltonian cycle, Diophantine, etc.) 
currently only have exponential-time solutions. But there is no 
guarantee that a polynomial solution (which is not NP, that is, is not 
the result of a "guess" or an "oracle") will not be found sometime in 
the future.

Proving that there "are" problems which can only be solved in 
exponential time but which can be checked in polynomial time is subtly 
different from saying that all problems in the class NP-complete admit 
no polynomial time solutions.

(I'm trying to avoid using shorthand like P and NP and Exptime, as a 
lot of confusion enters when shorthand gets misinterpreted.)


--Tim May

Re: Quantum Probability and Decision Theory

[Hal Finney]

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
> polynomial time on a "nondeterministic"
> machine, that is one that can test
> simultaneously all candidate solutions
> (effectively by creating exponentially
> many processes for testing all possible
> combinations of undetermined variables,
> each individual combination taking polynomial
> time to check)

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.

> By the way, it is known that factoring into
> primes is easier than the TSP.  The discovery
> of a classical polynomial time algorithm for
> factoring would cause much less shock than
> one for the TSP (which is "NP-complete",
> the hardest class of NP problems.

As I understand the state of play, factoring into primes is not known
to be NP-complete, but the contrary is not known, either.  Factoring is
strongly suspected not to be NP-complete but that has not been proven.
So it is still possible that factoring into primes is just as hard as
the TSP, although it is thought to be unlikely (it would imply that
NP = coNP).

Hal Finney

Re: Quantum Probability and Decision Theory

[Hal Finney]

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 theory.
>
> What about Hamiltonian circuits or factoring an integer or roots of a
> Diophantine equation?

I don't believe any of those are known to take exponential time.  For all
we know a polynomial time solution may yet be found for all of these.

Hal

Re: Quantum Probability and Decision Theory

[Brent Meeker]

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 Hamiltonian circuits or factoring an integer or roots of a
Diophantine equation?

Brent Meeker
"Just when I thought things couldn't get worse, I installed
Windows XP."
  --- DaveP

Re: Quantum Probability and Decision Theory

[Hans Moravec]

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 "nondeterministic"
machine, that is one that can test
simultaneously all candidate solutions
(effectively by creating exponentially
many processes for testing all possible
combinations of undetermined variables,
each individual combination taking polynomial
time to check)

A favorite example is the traveling
salesman problem (TSP), stated as "There is
a cycle of length no greater than L that
passes through all N nodes of this graph
exactly once."  (True or False)

There are exponentially (in N) many cycles,
so determining if any one of them has
length less than L would seem to require
exponential time (barring some yet-
undiscovered P=NP trick)

But if an exponential solution finder
also returns, when it answers "True", a
cycle it found that had length <=L, that
answer can be checked in linear time: just
add up the arc distances.

It is conceivable that an efficient TSP
solver could correctly return "Yes" for a
given L without being able to identify a
winning cycle.

Checking that answer would then be no easier
than solving the original problem.

By the way, it is known that factoring into
primes is easier than the TSP.  The discovery
of a classical polynomial time algorithm for
factoring would cause much less shock than
one for the TSP (which is "NP-complete",
the hardest class of NP problems.  A polynomial
solution for any NP-complete problem can
be mapped into a polynomial solution for all
NP-complete problems, and thus all NP problems,
and factoring).

Re: Quantum Probability and Decision Theory

[Brent Meeker]

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 emulating this unitary
> transformation. See Pour El and Richard's book on how to conceive
> differential equations with non computable solutions (but still
> locally generable by the UD though), but anyway, linear quantum
> waves are classicaly emulable. It is a tedious but conceptually not
> so hard exercise.
> 
> 
>> 
>>I can not see how this is possible given that (as Svozil et at
>> state in http://tph.tuwien.ac.at/~svozil/publ/embed.htm ) "for
>> quantum systems representable by Hilbert spaces of dimension higher
>> than two, there does not exist any such valuation s: L® {0,1} ...
>> there exist different quantum propositions which cannot be
>> distinguished by any classical truth assignment."

This is the Kochen-Specker theorem.  It depends on the existence of an
Hermitean operator to implement any function of variables.  You
should be aware that this problem is avoided by Bohm's intepretation
of quantum mechanics - so it is not inherent in the physics.  See
http://www.math.rutgers.edu/~oldstein/quote.html

Brent Meeker
There is a theory which states that if ever anybody discovers
exactly what the Universe is for and why it is here, it will
instantly disappear and be replaced by something even more
bizarre and inexplicable. There is another theory which states
that this has already happened.
-- Douglas Adams (Hitchhiker's Guide to the Galaxy)

RE: Quantum Probability and Decision Theory

[Jesse Mazer]

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 problem but I guess I was confused about what 
it meant. But there are some problems where candidate solutions can be 
checked much faster than new solutions can be generated, no? If you want to 
know whether a number can be factorized it's easy to check candidate 
factors, for example, although if the answer is that it cannot be factorized 
because the number is prime I guess there'd be no fast way to check if that 
answer is correct.


Since Moravec's machine uses time travel, or at least information transfer
into the past, it is obviously extremely speculative.  But given that,
I think your idea does make sense in theory, that if there were an
infinite amount of computing power possible in the future, and we sent
a signal into the past if a given program ever halted, then the absence
of such a signal would imply that the program did not halt.

Of course any kind of practical engineering that involves infinities
is even more speculative than time travel.  You have to assume that a
signal can be sent an infinite distance through time, that the future
calculation goes on forever and never ends, and so on.  It seems difficult
to imagine such a degree of consistency and reliability in the imperfect
universe where we live.


But whatever the degree of risk that the machine will malfunction over any 
set amount of time, it seems to me that one could always make that risk 
smaller and smaller over time by building more and more backup machines, so 
that in the limit the accumulated probability of a malfunction could still 
be kept small. I haven't thought this through too carefully though.

Anyway, however far-fetched the proposal is, if it could work even in 
principle it would be relevant to the question of whether quantum gravity 
allows uncomputable functions to be realized. General relativity does have 
solutions in which backwards time travel is possible, although I don't know 
how likely it is that this will remain true in a theory of quantum gravity 
(is it known if this is true in string theory?) But if it did, and if the 
theory also did not in principle forbid computing power to increase without 
limit (perhaps it would forbid it--for example, I'm not sure if Tipler's 
proposal would work if spacetime were quantized), then this would suggest 
the laws of physics are uncomputable, even if such a scheme is never 
actually realized in our universe.

This is also somewhat relevant to "theories of everything" since we might 
want to ask if somewhere in the set of "all possible universes" there exists 
one where time travel is possible and computing power increases without 
bound. If the answer is yes, that might suggest that any TOE based on "all 
possible computations" is too small to accomodate a really general notion of 
all possible universes. But it might be possible to arrange things so that 
one would experience living in such a universe from a first-person POV while 
your TOE is still based on some notion of all possible computations (as with 
the universal dovetailer)--one could start out computing different histories 
in which different possible "messages from the future" are recieved, and 
then continually spit out copies of the histories where no inconsistency has 
yet appeared while not doing the same for histories where an inconsistency 
does crop up, so that in the limit as time goes to infinity the first-person 
probability of finding oneself in an inconsistent history becomes 
vanishingly small compared to the probability of finding oneself in a 
consistent one.

Jesse

_
MSN 8 with e-mail virus protection service: 3 months FREE*. 
http://join.msn.com/?page=features/virus&xAPID=42&PS=47575&PI=7324&DI=7474&SU= 
http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_eliminateviruses_3mf

RE: Quantum Probability and Decision Theory

[Hal Finney]

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 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 
> exponential time to reach a solution but for which possible solutions can be 
> checked in polynomial time, you could have the machine pick a possible 
> solution at random, then check to see if the solution actually works, then 
> if it *doesn't* work it sends back a sort of override command that changes 
> the original guess, which would create an inconsistency. The only consistent 
> history in this case would be one where the machine's first guess happened 
> to be correct, so if history is indeed constrained to be consistent, you are 
> guaranteed to get the correct answer on the first guess.

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.

Since Moravec's machine uses time travel, or at least information transfer
into the past, it is obviously extremely speculative.  But given that,
I think your idea does make sense in theory, that if there were an
infinite amount of computing power possible in the future, and we sent
a signal into the past if a given program ever halted, then the absence
of such a signal would imply that the program did not halt.

Of course any kind of practical engineering that involves infinities
is even more speculative than time travel.  You have to assume that a
signal can be sent an infinite distance through time, that the future
calculation goes on forever and never ends, and so on.  It seems difficult
to imagine such a degree of consistency and reliability in the imperfect
universe where we live.

Hal Finney

RE: Quantum Probability and Decision Theory

[Jesse Mazer]

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 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...

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 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 
exponential time to reach a solution but for which possible solutions can be 
checked in polynomial time, you could have the machine pick a possible 
solution at random, then check to see if the solution actually works, then 
if it *doesn't* work it sends back a sort of override command that changes 
the original guess, which would create an inconsistency. The only consistent 
history in this case would be one where the machine's first guess happened 
to be correct, so if history is indeed constrained to be consistent, you are 
guaranteed to get the correct answer on the first guess.

Moravec says that although this would allow you to solve certain problems 
faster than a classical computer or a traditional quantum computer, it would 
not actually allow you to solve any uncomputable problems. But suppose we 
combine the idea of time-travel computers with the idea that intelligent 
life will find a way to increase the total amount of computing power 
available without bound as time goes to infinity (as in Freeman Dyson's 
proposal) or as time approaches the moment of the big crunch (as in Frank 
Tipler's proposal). Then it seems you could use such a machine to solve the 
halting problem--the machine could originally guess randomly whether to 
display the output "does not halt" or "halts after n steps" (where n is any 
whole number), and then you could run the computation indefinitely, and if 
it ever does halt and the number of steps is different from the original 
guess (or if it passes the number of steps in the original guess without 
halting), the machine is programmed to send back a message which overrides 
the original guess, which would create a contradiction. Thus, for history to 
work out consistently, the original guess must have been the correct one.

It seems to me that one could use this idea of time-travel-computers in a 
universe where computing power increases without bound not just to create 
first-level oracle machines which tell you if the nth Turing machine halts 
or not, but also arbitrary higher-level oracle machines which tell you if 
the nth m-level oracle machine halts or not, where m is any countable 
ordinal (Penrose discusses the notion of higher-level oracle machines in 
'Shadows of the Mind'). I'm not sure if there are any conceivable types of 
"machines" consisting of a finite set of well-defined operations that could 
not be simulated in such a universe.

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

Re: Quantum Probability and Decision Theory

[Jesse Mazer]

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


Please read this paper. It explains the basis of my claim.


Apologies, I hadn't even read the entire abstract so I didn't notice that 
they went on to argue that Feynman's conclusion was wrong. Still, I think 
that their proposal is something different from the usual notion of a 
"quantum computer", since I was under the impression that people like 
Feynman and Deutsch had already shown definitively that a quantum computer 
cannot solve any classically-unsolvable problems. I'll leave it to others 
who understand this paper better than I to discuss the merits of this new 
proposal.

Jesse


_
MSN 8: advanced junk mail protection and 3 months FREE*. 
http://join.msn.com/?page=features/junkmail&xAPID=42&PS=47575&PI=7324&DI=7474&SU= 
http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_advancedjmf_3mf

Re: Quantum Probability and Decision Theory

[Tim May]

On Monday, December 30, 2002, at 11:18  AM, Tim May wrote:



On Monday, December 30, 2002, at 10:44  AM, Stephen Paul King wrote:

QM comp seems to operate in the space of the Reals (R) and TM 
operates
in the space of Integers (Z), is this correct?

Any finite system, which of course all systems are, can have all of 
its quantum mechanics calculations done with finite-dimensional vector 
spaces. The "full-blown machinery" of an infinite-dimensional Hilbert 
space is nice to have, in the same way that Fourier analysis is more 
elegantly done with all possible frequencies even though no actual 
system (including the universe!) needs all frequencies.


Lest there be no confusion, I meant that all actual systems can be 
computed with finite-dimensional vector spaces which have inner 
products. Or in Von Neumann's more precise language, "complete complex 
inner product spaces." (Since all Hilbert spaces with an infinite 
number of dimensions are isomorphic, this gives rise to just saying 
"Hilbert space" in the singular.)

The point is that the arbitrary-dimension elegance of a full-blown 
Hilbert space is nice to have, especially for theorem-proving, but not 
essential.

More speculatively, postulating that a quantum state in the real world 
(in a quantum computer, or atom cage, etc.) is "actually" a vector with 
an infinite degree of positional accuracy, is akin to saying that it 
computes with the reals, which touches on the Blum-Shub-Smale issue I 
talked about earlier this morning.

As Hal says, the world is not actually Newtonian. And neither is it 
actually quantum-mechanical in the  ideal, limiting, 
infinite-dimensional case.

--Tim May

Re: Quantum Probability and Decision Theory

[Tim May]

On Monday, December 30, 2002, at 10:44  AM, Stephen Paul King wrote:

QM comp seems to operate in the space of the Reals (R) and TM 
operates
in the space of Integers (Z), is this correct?

Any finite system, which of course all systems are, can have all of its 
quantum mechanics calculations done with finite-dimensional vector 
spaces. The "full-blown machinery" of an infinite-dimensional Hilbert 
space is nice to have, in the same way that Fourier analysis is more 
elegantly done with all possible frequencies even though no actual 
system (including the universe!) needs all frequencies.


We must additionally account for, at least, the "illusion" of time 
and
concurrency of events.


I don't see any problems with either. (Yes, I have read Huw Price's 
book.)


--Tim May

Re: Quantum Probability and Decision Theory

[Joao Leao]

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 considering. But it
isn't necessarily the only one. This approach surfaces here and there
in the literature. See for example:

http://arXiv.org/abs/quant-ph/0205093

Another point worth making is that it seems unlikely that the recourse
to the infinite superposability of quantum states is going to be of any
help in this circunstance. It may be more profitable to look to
entanglement (which incidentaly is the trully novelty that QC brings
to the realm of computation) as the road to a trans-Turing class of
computations.

As to your reference to Penrose, Ben, I should probably add that
his much maligned ideas concerning the possibility of using Quantum
Gravity as a basis for understanding the psychology of mathematical
invention are perhaps worth a second look now that we are learning a
good deal more about quantum information in Black Holes etc...

-Joao Leao


Ben Goertzel wrote:

> > 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 being
> "finitely given"; Calude's theory makes very different assumptions.  If you
> take Calude's assumptions and replace them with finite-precision
> assumptions, the non-Turing stuff goes away.
>
> Less formally: you need to put noncomputable information into QM to get
> noncomputable information out of QM.  If you don't explicitly put
> noncomputable information into it, you won't get any out.
>
> ben

--

Joao Pedro Leao  :::  [EMAIL PROTECTED]
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!)"
---

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

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 truth" is a simpler assumption than the
existence of an infinite superposition (in Hilbert space?). It seems to me
that the former is a subset of the latter, not the other way around. Again,
I go back to Cantor's proof showing that the integers and the Reals have
distinct cardinalities and the simple question of "what breaths fire into
the equations?" (or Bruno's UD)?

QM comp seems to operate in the space of the Reals (R) and TM operates
in the space of Integers (Z), is this correct?

We must additionally account for, at least, the "illusion" of time and
concurrency of events.

Kindest regards,

Stephen

- Original Message -
From: "Hal Finney" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Monday, December 30, 2002 12:38 PM
Subject: Re: Quantum Probability and Decision Theory


> 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 answer is negative.
> This paper re-opens the case: we will discuss solutions to a few simple
> problems which suggest that quantum computing is theoretically capable
> of computing uncomputable functions."
>
>
> 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 require an infinite amount of work to prepare.
>
> It is well known that under idealized classical Newtonian physics,
> computations are possible that break the Turing barrier if you have
> infinite precision in your inputs.  Of course, we don't live in a
> Newtonian universe.  This new result has something of the same flavor,
> applied to a quantum mechanical universe.  It still relies on infinities.
>
> 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
>
>

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

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 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

Please read this paper. It explains the basis of my claim.

Kindest regards,

Stephen

> >I do not see how I misread Feynman's
> >claim
>
> 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
function?
> 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 barrier".
> Do you understand "negative" to mean something different?
>

[SPK]

Perhaps we should consider that our dear Mr. Feynman did not fully
appreciate his own idea. ;-)

Kindest regards,

Stephen

RE: Quantum Probability and Decision Theory

[Ben Goertzel]

> 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 being
"finitely given"; Calude's theory makes very different assumptions.  If you
take Calude's assumptions and replace them with finite-precision
assumptions, the non-Turing stuff goes away.

Less formally: you need to put noncomputable information into QM to get
noncomputable information out of QM.  If you don't explicitly put
noncomputable information into it, you won't get any out.

ben

Re: Quantum Probability and Decision Theory

[Hal Finney]

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 answer is negative.
This paper re-opens the case: we will discuss solutions to a few simple
problems which suggest that quantum computing is theoretically capable
of computing uncomputable functions."


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 require an infinite amount of work to prepare.

It is well known that under idealized classical Newtonian physics,
computations are possible that break the Turing barrier if you have
infinite precision in your inputs.  Of course, we don't live in a
Newtonian universe.  This new result has something of the same flavor,
applied to a quantum mechanical universe.  It still relies on infinities.

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

Re: Quantum Probability and Decision Theory

[Joao Leao]

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  :::  [EMAIL PROTECTED]
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!)"
---

RE: Quantum Probability and Decision Theory

[Ben Goertzel]

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
> >claim
>
> 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
> function?
> 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
> barrier".
> Do you understand "negative" to mean something different?
>
> Jesse
>
> _
> MSN 8 limited-time offer: Join now and get 3 months FREE*.
> http://join.msn.com/?page=dept/dialup&xAPID=42&PS=47575&PI=7324&DI
=7474&SU=
http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_newmsn8ishe
re_3mf

re:Re: Quantum Probability and Decision Theory

[Marchal Bruno]

Dear Stephen,

>[SPK]
>
>When what is [relevant]?
>
>> Quantum computer can be emulated by classical computer (see below).
>
>[SPK]
>
>Please point me to some paper, other than yours, that gives something
>better than a hand-waving argument of this statement.

See Deutsch 1985. (precise ref in my thesis)

>
>> Quantum computer does not violate Church thesis. The set of
>> quantum computable functions is the same as the set of classically
>> computable functions.
>
>[SPK]
>
>This is one statement that I found:
>
>http://www.netaxs.com/people/nerp/automata/church8.html
>"Church's thesis. All the models of computation yet developed, and all those
>that may be developed in the future, are equivalent in power. We will not
>ever find a more powerful model."
>
>
>Statements of this kind are found in religious dogma and are not
>acceptable in mathematical and logical circles unless they have adjoining
>caveats and attempted proofs. No where do I find this. It reminds me of
>Kronecker's statement "God made the integers; all else is the work of man."


Church thesis is indeed a non trivial hypothesis in the foundation
of computer science. The main conceptual argument is the closure of the
set of partial recursive functions for the diagonalisation procedure.
An empirical argument is that all attempt to define the set of computable
functions leads to the same class of functions. A relevant book is Webb 1980.


>
>I do not intend to be impolite here, Bruno, but, Please, give me some
>reference that discusses how it is that "The set of
>quantum computable functions is the same as the set of classically
>computable functions."

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 emulating this unitary transformation.
See Pour El and Richard's book on how to conceive differential equations
with non computable solutions (but still locally generable by the UD though),
but anyway, linear quantum waves are classicaly emulable. It is a tedious
but conceptually not so hard exercise.


>
>I can not see how this is possible given that (as Svozil et at state in
>http://tph.tuwien.ac.at/~svozil/publ/embed.htm )
>"for quantum systems representable by Hilbert spaces of dimension higher
>than two, there does not exist any such valuation s: L® {0,1} ... there
>exist different quantum propositions which cannot be distinguished by any
>classical truth assignment."
>
>If there does not exist a unique Boolean valuation for QM systems that
>can be taken to exist a priori and given that UTMs, including UD, demand the
>existence of such for their definition, how is it that you can continue to
>make this statement?

Because the physical world is a first person modality. The accessible
probable worlds can not *appear* in a boolean way from inside. Apparantly
it appears in some quantum logical way. The physical world is not
include in the UD; it emerges from the inside modal first person
statistics from the machines point of view. Those modalities are made
non trivial by the constraints of theoretical computer science and
logic of provability.


>[SPK]
>
>Can UD run them all simultaneously or in some concurrent way that would
>give us some way of finding solutions to the "foliation of space-like
>hypersurfaces" problem of GR? Also, what are the "physical resource"
>requirements of UD? What consitutes it's "memory" and its "read/write head"?

Good question. I hope so :)

>Also, what are the "physical resource"
>requirements of UD? What consitutes it's "memory" and its 
>"read/write head"?


I do not need the hypothesis of the existence of "physical resource".
The UD has no other requirement than arithmetical truth. You know,
infinity of primes, and other chinese theorems ...


>I like this part of your thesis and my interest in it makes me ask these
>very pointed questions. Additionally, I hope you would agree that there may
>be an additional problem of how the "Principle of Least action" of physics
>come about. Could it be considered, within your thesis, as just another
>1-person aspect?


Absolutely. Unless comp is false, and that's what makes comp testable.



>Appeals to polls and beliefs should not be made. It would be more
>helpfull if we considered such things as G. Chaitin's Omega when discussing
>random sequences. Can UD compute Omega?

No. But it trivially generates it. Uninterestingly, 'cause we cannot
recognize it. If you dont't like polls you can use the betting manner
of defining probabilities by iterating duplication of population of
machines.



>> Now, the simple reason why the quantum is turing-emulable is that the
>> solutions of Schroedinger or Dirac Wave Equation(s) are computable.
>
>[SPK]
>
>Where is this explained? Please, some papers that you did not write...


See ref above. Deutsch 1985. Or Deutsc

Re: Quantum Probability and Decision Theory

[Jesse Mazer]

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 quantum computing to challenge the Turing barrier, 
i.e., to solve an undecidable problem, to compute an uncomputable function? 
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 barrier". 
Do you understand "negative" to mean something different?

Jesse

_
MSN 8 limited-time offer: Join now and get 3 months FREE*. 
http://join.msn.com/?page=dept/dialup&xAPID=42&PS=47575&PI=7324&DI=7474&SU= 
http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_newmsn8ishere_3mf

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

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 issue of "speed" that I am trying to point
out, it is an issue of computational "expressiveness".
Unless I am mistaken, UTMs of all kinds operate in the space of
Integers, QM comps operate, at least, in the space of the Reals. ...

Kindest regards,

Stephen


- Original Message -
From: "Jesse Mazer" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Monday, December 30, 2002 11:01 AM
Subject: Re: Quantum Probability and Decision Theory


snip


http://www.cs.auckland.ac.nz/~cristian/coinsQIP.pdf
> >
> >
> >**
> >1. INTRODUCTION
> >
> >For over fifty years the Turing machine model of computation has defined
> >what it means to ''compute'' something; the foundations of the modern
> >theory of computing are based on it. Computers are reading text,
> >recognizing
> >speech, and robots are driving themselves across Mars. Yet this
> >exponential race will not produce solutions to many intractable and
> >undecidable
> >problems. Is there any alternative? Indeed, quantum computing
> >offers one such alternative (see Ref. 7, 10, 11, 23, 35). To date,
quantum
> >computing has been very successful in ''beating'' Turing machines in the
> >race of solving intractable problems, with Shor and Grover algorithms
> >achieving the most impressive successes; the progress in quantum hardware
> >is also impressive. Is there any hope for quantum computing to challenge
> >the
> >Turing barrier, i.e., to solve an undecidable problem, to compute an
> >uncomputable function? According to Feynman's argument (see Ref. 20, a
> >paper reproduced also in Ref. 25, regarding the possibility of simulating
a
> >quantum system on a (probabilistic) Turing machine) the answer is
> >negative.
>
> This seems to say the opposite of what you are arguing. Look at the last
two
> sentences--they ask if quantum computers can "solve an undecidable
problem"
> (relative to a classical computer) or "compute an uncomputable function",
> but according to Feynman "the answer is negative"--ie a quantum computer
can
> *not* solve any classically-unsolvable problems. I take it you interpreted
> Feynman's negative answer to refer to "the possibility of simulating a
> quantum system on a (probabilistic) Turing machine", but because of the
way
> the sentences are constructed I think you misread it. I suspect that
> "Feynman's argument" involved showing that you *can* simulate a quantum
> system on a probabilistic Turing machine, and that he used that to prove
> that quantum computers cannot do anything fundamentally new, even if they
> may in some cases work much faster.

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

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 "macroscopic state" of
neurons
> >is not completely classical and thus some degree of QM entanglement is
> >involved. But hand waving arguments aside, I would really like to
understand
> >how you and Bruno (and others), given the proof and explanations
contained
> >in these above mentioned papers and others, maintain the idea that "any
> >quantum computer or physical system can be simulated by a classical
> >computer."
>
> I agree with almost all the quotations you gave in your post
> http://www.escribe.com/science/theory/m4254.html
> But they are not relevant for our issue.

[SPK]

When what is?

> Quantum computer can be emulated by classical computer (see below).

[SPK]

Please point me to some paper, other than yours, that gives something
better than a hand-waving argument of this statement.

> Quantum computer does not violate Church thesis. The set of
> quantum computable functions is the same as the set of classically
> computable functions.

[SPK]

This is one statement that I found:

http://www.netaxs.com/people/nerp/automata/church8.html
"Church's thesis. All the models of computation yet developed, and all those
that may be developed in the future, are equivalent in power. We will not
ever find a more powerful model."


Statements of this kind are found in religious dogma and are not
acceptable in mathematical and logical circles unless they have adjoining
caveats and attempted proofs. No where do I find this. It reminds me of
Kronecker's statement "God made the integers; all else is the work of man."

I do not intend to be impolite here, Bruno, but, Please, give me some
reference that discusses how it is that "The set of
quantum computable functions is the same as the set of classically
computable functions."

I can not see how this is possible given that (as Svozil et at state in
http://tph.tuwien.ac.at/~svozil/publ/embed.htm )
"for quantum systems representable by Hilbert spaces of dimension higher
than two, there does not exist any such valuation s: L® {0,1} ... there
exist different quantum propositions which cannot be distinguished by any
classical truth assignment."

If there does not exist a unique Boolean valuation for QM systems that
can be taken to exist a priori and given that UTMs, including UD, demand the
existence of such for their definition, how is it that you can continue to
make this statement?

>
> The difference are the following points 1) and 2):
> 1) A classical computer cannot emulate a quantum computer in "real time",
> nor 2) can a classical computer provide a pure 3-person emulation of
> some quantum *processes* like the generation of truly random
> numbers.
>
> But this is not relevant concerning our fundamental issue.
> Concerning 1) the only thing which matters is that the classical UD
> runs all programs including quantum one.

[SPK]

Can UD run them all simultaneously or in some concurrent way that would
give us some way of finding solutions to the "foliation of space-like
hypersurfaces" problem of GR? Also, what are the "physical resource"
requirements of UD? What consitutes it's "memory" and its "read/write head"?

> THEN, by UDA reasoning, it is
> shown that "real time" is a 1-person (plural) emerging notion. Even
> if the UD need many googol-years to compute each "quantum step", from the
> inside 1-person point of view, that delays are not observable. CF the
> "invariance lemma" in UDA.

[SPK]

I like this part of your thesis and my interest in it makes me ask these
very pointed questions. Additionally, I hope you would agree that there may
be an additional problem of how the "Principle of Least action" of physics
come about. Could it be considered, within your thesis, as just another
1-person aspect?


> Concerning 2): idem! We cannot generate truly random sequences, but we
> can easily (with the comp hyp!!!) generate histories in which
> most average observers will correctly believe in truly random sequences.

[SPK]

Appeals to polls and beliefs should not be made. It would be more
helpfull if we considered such things as G. Chaitin's Omega when discussing
random sequences. Can UD compute Omega?

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/#PL


> It is enough for that purpose to iterate the Washington-Moscow
> self-duplication experiment. If you iterate this 64 times, most of
> the 1.85 10^19 v

Re: Quantum Probability and Decision Theory

[Jesse Mazer]

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


***
4  Summary
We have reviewed several options for a classical ``understanding'' of
quantum mechanics. Particular emphasis has been given to techniques for
embedding quantum universes into classical ones. The term ``embedding'' is
formalized here as usual. That is, an embedding is a mapping of the entire
set of quantum observables into a (bigger) set of classical observables 
such
that different quantum observables correspond to different classical ones
(injectivity).
The term ``observables'' here is used for quantum propositions, some of
which (the complementary ones) might not be co-measurable, see Gudder [14].

This problem of "embedding" seems different from the question of whether 
quantum computers can do anything classical computers cannot--for example, 
the last sentence above talks about the problem of whether complementary 
observables might have definite classical values, but a quantum computer's 
output must be measurable--you can't have an "output" which involves two 
bits encoded in terms of complementary observables, since it would be 
impossible to measure the value of both those bits simultaneously.

Perhaps someone who understands that paper better could comment further, but 
I don't think it supports the view that a quantum computer could solve 
problems which are unsolvable by a classical one.

 Let me quote from some other papers to reinforce my argument.

http://www.cs.auckland.ac.nz/~cristian/coinsQIP.pdf


**
1. INTRODUCTION

For over fifty years the Turing machine model of computation has defined

what it means to ''compute'' something; the foundations of the modern

theory of computing are based on it. Computers are reading text, 
recognizing

speech, and robots are driving themselves across Mars. Yet this

exponential race will not produce solutions to many intractable and
undecidable

problems. Is there any alternative? Indeed, quantum computing

offers one such alternative (see Ref. 7, 10, 11, 23, 35). To date, quantum

computing has been very successful in ''beating'' Turing machines in the

race of solving intractable problems, with Shor and Grover algorithms

achieving the most impressive successes; the progress in quantum hardware

is also impressive. Is there any hope for quantum computing to challenge 
the

Turing barrier, i.e., to solve an undecidable problem, to compute an

uncomputable function? According to Feynman's argument (see Ref. 20, a

paper reproduced also in Ref. 25, regarding the possibility of simulating a

quantum system on a (probabilistic) Turing machine4) the answer is 
negative.

This seems to say the opposite of what you are arguing. Look at the last two 
sentences--they ask if quantum computers can "solve an undecidable problem" 
(relative to a classical computer) or "compute an uncomputable function", 
but according to Feynman "the answer is negative"--ie a quantum computer can 
*not* solve any classically-unsolvable problems. I take it you interpreted 
Feynman's negative answer to refer to "the possibility of simulating a 
quantum system on a (probabilistic) Turing machine", but because of the way 
the sentences are constructed I think you misread it. I suspect that 
"Feynman's argument" involved showing that you *can* simulate a quantum 
system on a probabilistic Turing machine, and that he used that to prove 
that quantum computers cannot do anything fundamentally new, even if they 
may in some cases work much faster.


We also have:

http://xxx.lanl.gov/abs/quant-ph/0204153


A stronger no-cloning theorem
Authors: Richard Jozsa (University of Bristol UK)
Comments: 4 pages. An error in version 1 corrected. Further 
interpretational
comments added


 It is well known that (non-orthogonal) pure states cannot be cloned so 
one
may ask: how much or what kind of additional (quantum) information is 
needed
to supplement one copy of a quantum state in order to be able to produce 
two
copies of that state by a physical operation? For classical information, no
supplementary information is required. However for pure quantum
(non-orthogonal) states, we show that the supplementary information must
always be as large as it can possibly be i.e. the clone must be able to be
generated

Re: Quantum Probability and Decision Theory

[Marchal Bruno]

Stephen Paul King wrote:

>There do exist strong arguments that the "macroscopic state" of neurons
>is not completely classical and thus some degree of QM entanglement is
>involved. But hand waving arguments aside, I would really like to understand
>how you and Bruno (and others), given the proof and explanations contained
>in these above mentioned papers and others, maintain the idea that "any
>quantum computer or physical system can be simulated by a classical
>computer."

I agree with almost all the quotations you gave in your post 
http://www.escribe.com/science/theory/m4254.html
But they are not relevant for our issue.
Quantum computer can be emulated by classical computer (see below).
Quantum computer does not violate Church thesis. The set of 
quantum computable functions is the same as the set of classically
computable functions.

The difference are the following points 1) and 2):
1) A classical computer cannot emulate a quantum computer in "real time",
nor 2) can a classical computer provide a pure 3-person emulation of
some quantum *processes* like the generation of truly random
numbers.

But this is not relevant concerning our fundamental issue.
Concerning 1) the only thing which matters is that the classical UD
runs all programs including quantum one. THEN, by UDA reasoning, it is
shown that "real time" is a 1-person (plural) emerging notion. Even
if the UD need many googol-years to compute each "quantum step", from the
inside 1-person point of view, that delays are not observable. CF the
"invariance lemma" in UDA.
Concerning 2): idem! We cannot generate truly random sequences, but we
can easily (with the comp hyp!!!) generate histories in which 
most average observers will correctly believe in truly random sequences. 
It is enough for that purpose to iterate the Washington-Moscow 
self-duplication experiment. If you iterate this 64 times, most of 
the 1.85 10^19 version of you will conclude (correctly with comp) that
they are unable to predict their next self-output (W or M) and that their
histories, in this context are truly random.

Now, the simple reason why the quantum is turing-emulable is that the
solutions of Schroedinger or Dirac Wave Equation(s) are computable.
If you simulate such a wave you will realise that it simulates the
many-world or many-dreams, even in such a way of making extravaguant
histories much more rare than normal (lawfull) histories.
This is not yet obvious with pure comp, where non quantum histories
must yet be proved measure-negligeable (but see my thesis and posts to
get a feeling why with comp it should be so, and why indeed it seems to
be so).

Bruno

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

Dear Wei,

Interleaving.

- Original Message -
From: "Wei Dai" <[EMAIL PROTECTED]>
To: "Stephen Paul King" <[EMAIL PROTECTED]>
Cc: <[EMAIL PROTECTED]>
Sent: Friday, December 27, 2002 4:18 PM
Subject: Re: Quantum Probability and Decision Theory


> On Thu, Dec 26, 2002 at 08:21:38PM -0500, Stephen Paul King wrote:
> > Forgive me if my writting gave you that opinion. I meant to imply
that
> > any mind, including that of a bat, is quantum mechanical and not
classical
> > in its nature. My ideas follow the implications of Hitoshi Kitada's
theory
> > of Local Time.
>
> Please explain how your ideas follow from Hitoshi Kitada's theory
> of Local Time. Keep in mind that most of us are not familiar with that
> theory.
>

[SPK]

It is hard for me to condense the theory of Local Time, it is better to
refer you to Hitoshi Kitada's papers. You will find them here:

http://www.kitada.com/#time

> 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?  Let me quote from a
paper by Karl Svozil et al:  http://tph.tuwien.ac.at/~svozil/publ/embed.htm

***
4  Summary
We have reviewed several options for a classical ``understanding'' of
quantum mechanics. Particular emphasis has been given to techniques for
embedding quantum universes into classical ones. The term ``embedding'' is
formalized here as usual. That is, an embedding is a mapping of the entire
set of quantum observables into a (bigger) set of classical observables such
that different quantum observables correspond to different classical ones
(injectivity).
The term ``observables'' here is used for quantum propositions, some of
which (the complementary ones) might not be co-measurable, see Gudder [14].
It might therefore be more appropriate to conceive these ``observables'' as
``potential observables.'' After a particular measurement has been chosen,
some of these observables are actually determined and others (the
complementary ones) become ``counterfactuals'' by quantum mechanical means;
cf. Schrödinger's catalogue of expectation values [42]. For classical
observables, there is no distinction between ``observables'' and
``counterfactuals,'' because everything can be measured precisely, at least
in principle.

We should mention also a caveat. The relationship between the states of a
quantum universe and the states of a classical universe into which the
former one is embedded is beyond the scope of this paper.

As might have been suspected, it turns out that, in order to be able to
perform the mapping from the quantum universe into the classical one
consistently, important structural elements of the quantum universe have to
be sacrificed:


  ·
  Since per definition, the quantum propositional calculus is
nondistributive (nonboolean), a straightforward embedding which preserves
all the logical operations among observables, irrespective of whether or not
they are co-measurable, is impossible. This is due to the quantum mechanical
feature of complementarity.
  ·
  One may restrict the preservation of the logical operations to be valid
only among mutually orthogonal propositions. In this case it turns out that
again a consistent embedding is impossible, since no consistent meaning can
be given to the classical existence of ``counterfactuals.'' This is due to
the quantum mechanical feature of contextuality. That is, quantum
observables may appear different, depending on the way by which they were
measured (and inferred).
  ·
  In a further step, one may abandon preservation of lattice operations such
as not and the binary and and or operations altogether. One may merely
require the preservation of the implicational structure (order relation). It
turns out that, with these provisos, it is indeed possible to map quantum
universes into classical ones. Stated differently, definite values can be
associated with elements of physical reality, irrespective of whether they
have been measured or not. In this sense, that is, in terms of more
``comprehensive'' classical universes (the hidden parameter models), quantum
mechanics can be ``understood.''
***

What this paper points out is that it is impossible to completely embed
a "QM universe" in a classical one. If, as you say, it is possible to
simulate quantum computer or physical system by a classical computer, then
we find outselves in an odd predicament.


  Let me quote from some other papers to reinforce my argument.

http://www.cs.auckland.ac.nz/~cr

Re: Quantum Probability and Decision Theory

[Wei Dai]

On Thu, Dec 26, 2002 at 08:21:38PM -0500, Stephen Paul King wrote:
> Forgive me if my writting gave you that opinion. I meant to imply that
> any mind, including that of a bat, is quantum mechanical and not classical
> in its nature. My ideas follow the implications of Hitoshi Kitada's theory
> of Local Time.

Please explain how your ideas follow from Hitoshi Kitada's theory
of Local Time. Keep in mind that most of us are not familiar with that 
theory.

Also, any quantum computer or physical system can be simulated by a
classical computer. So in theory, even if human minds are quanum
mechanical, we can simulate a complete human being from conception to
adulthood in a classical computer, and then copy him to another classical
computer, so the no-cloning theorem doesn't prevent copying of minds.

Besides, the no-cloning theorem only says that there's no method for
duplicating arbitrary quantum systems in such a way that no statistical
test can tell the difference between the original and the copy. There is
no evidence that the information that can't be copied are crucial to the
workings of a human mind. I think current theories of how the brain works
have its information stored in macroscopic states such as neuron
connections and neurotransmitter concentrations, which can be copied.

Re: Quantum Probability and Decision Theory

[Joao Leao]

Stephen,

Thanks for clarifying that point. I take it it was a misprint. I am new to
this list and am still trying to understand what you guys are talking about.
Forgive me if I pick on you but your interventions seem to me the most lucid
of the ones I have read thus far! I have two naive comments at this stage:

1) I am as puzzled with your suspicion that "all minds are quantum mechanical"
as I would perhaps be with the obverse suspicion that "all minds are classical
mechanical"! Both seem to me rather vaccuous statements since we don't
really yet have a theory, classical or quantum or whathaveyou , of what a
mind is or does. I don't mean an emprirical, or verifiable, or decidable
or merely speculative theory! I mean ANY theory. Please show me I
am wrong if you think otherwise.

2) I deduce from your web pages that you are curious about and sympathetic
of daring spaculations on these "frontier" matters. So am I. But you are
luckier
and abler than me if you understand Kitada's papers. It may just be that he
expresses himself so poorely in english that the ideas don't quite come
through.
He appears to believe in something like a "quantum origin of abstract concepts"

which is an interesting subject, at least to me. Maybe you can explain how
this comes out of his "internal time"! I fail to see the chain of reasoning...

Thanks,

-Joao

Stephen Paul King wrote:

> Dear Joao,
>
> Forgive me if my writting gave you that opinion. I meant to imply that
> any mind, including that of a bat, is quantum mechanical and not classical
> in its nature. My ideas follow the implications of Hitoshi Kitada's theory
> of Local Time.
>
> Kindest regards,
>
> Stephen
>
> - Original Message -
> From: "Joao Leao" <[EMAIL PROTECTED]>
> To: "Stephen Paul King" <[EMAIL PROTECTED]>
> Cc: <[EMAIL PROTECTED]>
> Sent: Thursday, December 26, 2002 2:47 PM
> Subject: Re: Quantum Probability and Decision Theory
>
> > I am sorry but I have to ask: why would "minds" be quantum
> > mechanical but "bat minds" be classical  in your suspicions?
> > I am not sure I am being "batocentric" here but I can anticipate
> > a lot of bats waving their wings in disagreament...
> >
> > -Joao
> >
> >
> > Stephen Paul King wrote:
> >
> > > [SPK]
> > >
> > > Yes. I strongly suspect that "minds" are quantum mechanical. My
> > > arguement is at this point very hand waving, but it seems to me that if
> > > minds are purely classical when it would not be difficult for us to
> imagine,
> > > i.e. compute, what it is like to "be a bat" or any other classical mind.
> >
> > --
> >
> > Joao Pedro Leao  :::  [EMAIL PROTECTED]
> > 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!)"
> > ---
> >

--

Joao Pedro Leao  :::  [EMAIL PROTECTED]
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!)"
---

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

Dear Joao,

Forgive me if my writting gave you that opinion. I meant to imply that
any mind, including that of a bat, is quantum mechanical and not classical
in its nature. My ideas follow the implications of Hitoshi Kitada's theory
of Local Time.

Kindest regards,

Stephen

- Original Message -
From: "Joao Leao" <[EMAIL PROTECTED]>
To: "Stephen Paul King" <[EMAIL PROTECTED]>
Cc: <[EMAIL PROTECTED]>
Sent: Thursday, December 26, 2002 2:47 PM
Subject: Re: Quantum Probability and Decision Theory


> I am sorry but I have to ask: why would "minds" be quantum
> mechanical but "bat minds" be classical  in your suspicions?
> I am not sure I am being "batocentric" here but I can anticipate
> a lot of bats waving their wings in disagreament...
>
> -Joao
>
>
> Stephen Paul King wrote:
>
> > [SPK]
> >
> > Yes. I strongly suspect that "minds" are quantum mechanical. My
> > arguement is at this point very hand waving, but it seems to me that if
> > minds are purely classical when it would not be difficult for us to
imagine,
> > i.e. compute, what it is like to "be a bat" or any other classical mind.
>
> --
>
> Joao Pedro Leao  :::  [EMAIL PROTECTED]
> 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!)"
> ---
>

Re: Quantum Probability and Decision Theory

[Joao Leao]

I am sorry but I have to ask: why would "minds" be quantum
mechanical but "bat minds" be classical  in your suspicions?
I am not sure I am being "batocentric" here but I can anticipate
a lot of bats waving their wings in disagreament...

-Joao


Stephen Paul King wrote:

> [SPK]
>
> Yes. I strongly suspect that "minds" are quantum mechanical. My
> arguement is at this point very hand waving, but it seems to me that if
> minds are purely classical when it would not be difficult for us to imagine,
> i.e. compute, what it is like to "be a bat" or any other classical mind.

--

Joao Pedro Leao  :::  [EMAIL PROTECTED]
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!)"
---

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

Dear Bruno and Tim and Eric,

Thank you for you thoughtful and thought provoking replies. What your
comments point out is that I need to sharpen my argument and study more so
that I can better understand the ideas, for example, that "The no-cloning
theorem is also a consequence of comp".
Bruno, I am still not convinced that the statements that "If we are
consistent machine we cannot know which machine we are" and "Godel's and
Lob's incompleteness prevent us to identify any intuitive first person
knowledge with objective third person communicable statements"  mutes my
question since it seems that it makes my predicament much worse! It seems
that your idea prevents me from "knowing what it is like to be a bat" by not
allowing me to have any 1-person certainty at all, in other words, I can not
be sure that I am not a "bat" or a "amoeba" or a "Dark Cloud" or whatever.
 Do you see any possibility that we might use omega-incompleteness to
recover, at least, some form of justification, albeit vanishing in the omega
limit, that, for example, I am a human and not a bat?

Kindest regards,

Stephen

- Original Message -
From: "Marchal Bruno" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Tuesday, December 24, 2002 4:03 AM
Subject: Re: Quantum Probability and Decision Theory


> Stephen Paul King wrote:
>
>
> >Yes. I strongly suspect that "minds" are quantum mechanical. My
> >arguement is at this point very hand waving, but it seems to me that if
> >minds are purely classical when it would not be difficult for us to
imagine,
> >i.e. compute, what it is like to "be a bat" or any other classical mind.
I
> >see this as implied by the ideas involved in Turing Machines and other
> >"Universal" classical computational systems.
>
> I'm afraid you have a pregodelian (or better a preEmilPostian) view
> of machine. If we are consistent machine we cannot know which machine
> we are. We cannot consistently identify formal and intuitive probability.
> Godel's and Lob's incompleteness prevent us to identify any intuitive
> first person knowledge with objective third person communicable
statements.
> Gunderson has given also non-godelian argument, based on simple assymmetry
> considerations illustrating the point. Actually duplication experiments
> provide intuitive understanding of that phenomenon: if you are duplicated
> at the right level, none of "you" can understand what it is like to be the
> other. You could look at "Benacerraf" in the archive to see more.
> Note also the UD Argument works for quantum brain too. Although quantum
> states are not duplicable, it is still possible to prepare them in many
> instances, and that is what the UD does (quantum universal machine *are*
> emulable by classical machine).
>
> The no-cloning theorem is also a consequence of comp. Knowing that
> our experiential states supervene not on a "physical state" but on
> the whole set of histories going through that states, it is hard to
imagine
> how anyone could duplicate anything below its substitution level.
>
> Bruno
>
>
>

Re: Quantum Probability and Decision Theory

[Eric Hawthorne]

Stephen Paul King wrote:


it seems to me that if
minds are purely classical when it would not be difficult for us to imagine,
i.e. compute, what it is like to "be a bat" or any other classical mind. I
see this as implied by the ideas involved in Turing Machines and other
"Universal" classical computational systems.


Ah, but human thinking is a resource-bounded, real-time computational activity.
Despite the massive parallelism of brain computation, we are of necessity
"lazy evaluators" of thoughts. If we weren't, we'd all go mad or become
successful zen practitioners. Sure, we do some free-form associative thought,
and ponder connections subconsciously in the background, but if there's one thing
my AI and philosophy studies have taught me, it is that prioritization
and pruning of reasoning are fundamental keys. There are an infinite
number of implications and probability updates that could be explored, given our
present knowledge. But clearly we're only going to do task-directed, motivationally
directed, sense-data-related subsets of those inferences, and a finite amount 
of related associative inference in the background to support those. 

Therefore, if nothing else, we can't imagine what it is like to be a bat
because we would have to have the reasoning time and resources to explore all of a bat's
experience to get there. And it would also be difficult and probably impossible, 
because the bat's mind at birth would be preloaded with different "firmware" instinctive 
behaviours than ours is. Also, the bat's mind would be connected to a different
though analogous set of nerves, sense organs, and motor control systems, 
and to a differently balanced neurochemical emotional (reasoning prioritization) system. 

Regarding emulating another person's experience. The trouble is, again, that you'd
have to emulate all of it from (before) birth, because clearly our minds are built 
up of our individual experiences and responses to our environment, and our own 
particularly skewed generalizations from those, as much as from anything else.
And again, you'd have to compensate (emulate) for the subtle but vast differences in the firmware
of each person's brain as it came out of the womb. It's an impossible project in
practical terms, even if the brains are Turing equivalent, which they are.

You don't need to resort to QM to explain the difficulty of emulating other minds.
It's simply a question of combinatorics and vast complexity and subtlety of firmware, 
experience and knowledge. 

Remember on the other hand that human linguistic communication only communicates
"tips of icebergs" of meaning explicitly in the words, and assumes that the utterer
and the reader/listener share a vast knowledge, belief and experience base, and
have similar tendencies toward conjuring up thinking contexts in response to the
prodding of words. (Words are to mentally stored concepts as URLs are to documents).

In order to communicate, we do have to emulate (imagine) our target audience's 
thought patterns and current thinking context and emotional state, so that we can know 
which sequence of words is likely to direct their thoughts and
feelings thus and so as we wish to direct them.

Eric

Re: Quantum Probability and Decision Theory

[Marchal Bruno]

Stephen Paul King wrote:


>Yes. I strongly suspect that "minds" are quantum mechanical. My
>arguement is at this point very hand waving, but it seems to me that if
>minds are purely classical when it would not be difficult for us to imagine,
>i.e. compute, what it is like to "be a bat" or any other classical mind. I
>see this as implied by the ideas involved in Turing Machines and other
>"Universal" classical computational systems.

I'm afraid you have a pregodelian (or better a preEmilPostian) view
of machine. If we are consistent machine we cannot know which machine
we are. We cannot consistently identify formal and intuitive probability.
Godel's and Lob's incompleteness prevent us to identify any intuitive
first person knowledge with objective third person communicable statements.
Gunderson has given also non-godelian argument, based on simple assymmetry
considerations illustrating the point. Actually duplication experiments
provide intuitive understanding of that phenomenon: if you are duplicated
at the right level, none of "you" can understand what it is like to be the
other. You could look at "Benacerraf" in the archive to see more.
Note also the UD Argument works for quantum brain too. Although quantum
states are not duplicable, it is still possible to prepare them in many
instances, and that is what the UD does (quantum universal machine *are*
emulable by classical machine).

The no-cloning theorem is also a consequence of comp. Knowing that
our experiential states supervene not on a "physical state" but on
the whole set of histories going through that states, it is hard to imagine
how anyone could duplicate anything below its substitution level.

Bruno

Re: Quantum Probability and Decision Theory

[James N Rose]

Stephen Paul King wrote:
> 
> Dear Wei,
> 
> Interleaving.
> 
> [SPK]
> 
> Yes. I strongly suspect that "minds" are quantum mechanical. My
> arguement is at this point very hand waving, but it seems to me that if
> minds are purely classical when it would not be difficult for us to imagine,
> i.e. compute, what it is like to "be a bat" or any other classical mind. I
> see this as implied by the ideas involved in Turing Machines and other
> "Universal" classical computational systems.
> The no cloning theoren of QM seems to have the "right flavor" to explain
> how it is that we can not have first person experience of each other's
> minds, whereas the UTM model seems to strongly imply that I should be able
> to know exactly what you are thinking. In the words of Sherlock Holmes, this
> is a "the dog did not bark" scenario.
> 
>  > What about AIs running on classical computers?
> >
> 
> [SPK]
> 
> It would help us to find out if an AI, running on a classical computer,
> could pass the Turing test. 


To Stephen, et al.,

I strongly urge contemplating a new set 
of criteria to replace the Turing Test.

Suggested reading:


(1996)

Jamie Rose
Ceptual Institute
Dec 23, 2002

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

Dear Wei,

Interleaving.

- Original Message -
From: "Wei Dai" <[EMAIL PROTECTED]>
To: "Stephen Paul King" <[EMAIL PROTECTED]>
Cc: <[EMAIL PROTECTED]>
Sent: Monday, December 23, 2002 5:16 PM
Subject: Re: Quantum Probability and Decision Theory


> On Wed, Dec 18, 2002 at 08:54:30PM -0500, Stephen Paul King wrote:
> > Two ideas would seem to mute this strange thought.
> >
> > 1) The no-cloning theorem, iff the world follows QM and not just
classical
> > physics.
>
> Are you saying the no-cloning theorem will prevent copying of minds?

[SPK]

Yes. I strongly suspect that "minds" are quantum mechanical. My
arguement is at this point very hand waving, but it seems to me that if
minds are purely classical when it would not be difficult for us to imagine,
i.e. compute, what it is like to "be a bat" or any other classical mind. I
see this as implied by the ideas involved in Turing Machines and other
"Universal" classical computational systems.
The no cloning theoren of QM seems to have the "right flavor" to explain
how it is that we can not have first person experience of each other's
minds, whereas the UTM model seems to strongly imply that I should be able
to know exactly what you are thinking. In the words of Sherlock Holmes, this
is a "the dog did not bark" scenario.

 > What about AIs running on classical computers?
>

[SPK]

It would help us to find out if an AI, running on a classical computer,
could pass the Turing test. We seem to have become so extreme in our
rejection of Lucas and Serle that we have fallen off the edge and assume
that zombies could not exist.

> > 2) van Fraassen's Reflection Principle seems to ignore the possibility
that
> > probabilities and their distributions are given ab inition and that the
> > notion of "updating" and/or revising one's expectations is negligible.
>
> I don't understand what you're trying to say. Can you expand on it please?

[SPK]

I wrote incorrectly. What I wrote should have read:

> > 2) van Fraassen's Reflection Principle seems to ignore the possibility
that
> > probabilities and their distributions are NOT given ab inition and that
the
> > notion of "updating" and/or revising one's expectations is negligible.

Let me see if I can find the paper that I read about the Reflection
Principle and see if I can be a bit more pointed in my argument.

See:
http://www.brown.edu/Departments/Philosophy/homepages/weatherson/Dutchmar.pd
f

In it we find:

***
Van Fraassen on Reflection

In Belief and the Will (1984) van Fraasen argues that we should follow a
principle called Reflection. If we

think that tomorrow we'll believe that the probability of p is x then today
we should believe the probability

of p is x.

***

 It was this passage that lead me to the belief that Van Fraasen assumed
that the equality p is x is one that is not subject to updating. In other
words that our expectations based on current information are not subject to
revisions such that  tomorrow's  p is x  will be identical with today's.

What I see implicit in this discussion is an attempt to deal
quantitatively with the notion of expectations. I am reminded of having read
somewhere about games theories where the palyers did not have complete
knowledge of the other player's possible moves. Brian Weatherson's paper,
from which I quoted, seems to imply such an idea but does not address it
directly.

Any comments?

Kindest regards,

Stephen

Re: Quantum Probability and Decision Theory

[Wei Dai]

On Wed, Dec 18, 2002 at 08:54:30PM -0500, Stephen Paul King wrote:
> Two ideas would seem to mute this strange thought.
> 
> 1) The no-cloning theorem, iff the world follows QM and not just classical
> physics.

Are you saying the no-cloning theorem will prevent copying of minds? What
about AIs running on classical computers?

> 2) van Fraassen's Reflection Principle seems to ignore the possibility that
> probabilities and their distributions are given ab inition and that the
> notion of "updating" and/or revising one's expectations is negligible.

I don't understand what you're trying to say. Can you expand on it please?

Re: Quantum Probability and Decision Theory

[Stephen Paul King]

Dear Wei,

Two ideas would seem to mute this strange thought.

1) The no-cloning theorem, iff the world follows QM and not just classical
physics.

2) van Fraassen's Reflection Principle seems to ignore the possibility that
probabilities and their distributions are given ab inition and that the
notion of "updating" and/or revising one's expectations is negligible.

Kindest regards,

Stephen

- Original Message -
From: "Wei Dai" <[EMAIL PROTECTED]>
To: "Marchal Bruno" <[EMAIL PROTECTED]>
Cc: <[EMAIL PROTECTED]>
Sent: Wednesday, December 18, 2002 8:15 PM
Subject: Re: Quantum Probability and Decision Theory


> On Wed, Dec 04, 2002 at 04:00:07PM +0100, Marchal Bruno wrote:
> > Have you read the "revisited" paper by Wallace on Everett/decision
> > theory? Quite interesting imo, and relevant for some discussion,
> > about MWI and decision theory we have had on this list.
> >
> > http://philsci-archive.pitt.edu/documents/disk0/00/00/08/85/index.html
>
> Thanks for this pointer. I highly recommend this paper as well, for an
> introduction to decision theory and an example its implications.
> Unfortunately the author is not aware of some serious problems with the
> subjective-indeterministic version of decision theory that he adopts,
> which we've discussed on this list in the past. I'll attach an email that
> I sent him summarizing the problems with the subjective-indeterministic
> view.
>
> ---
>
> 1. The SI viewpoint is not evolutionarily adaptive if copying is possible.
> Suppose a company invents a non-destructive matter-transporter and offers
> to create copies of paying customers on distant planets with the
> opportunity to colonize them. And suppose the expected living standards on
> the colonized planets would be just slightly lower than those on Earth.
> Those who accept the SI viewpoint would refuse to pay anything for this
> service, since it would lower their expected utility. The universe would
> quickly be dominated by the OD viewpoint.
>
> 2. A similar issue arises in quantum splitting. In a thought experiment
> that Max Tegmark calls quantum suicide (see his "The Interpretation of
> Quantum Mechanics: Many Worlds or Many Words?" available at
> http://www.hep.upenn.edu/~max/everett.html), the experimenter is killed
> every time a quantum measurement comes out a certain way (say spin up).
> People who accept the SI viewpoint will have no problem with doing this
> experiment. People who accept OD can actually benefit at their expense,
> for example by offering to gamble with the experimenter on the outcome of
> the measurement. The experimenter will believe that the probability of
> spin down is 1, and will accept any odds on a gamble that pays on spin
> down.
>
> 3. The SI viewpoint either contradicts van Fraassen's Reflection Principle
> or leads to counterintuitive results. Saunders tries to address this in
> his paper (section 4.3) but I don't think his argument is convincing.
> Consider Fig.1 in his paper (page 15, at
> http://philsci-archive.pitt.edu/documents/disk0/00/00/04/65/ in case you
> don't have it handy). Before the copying, it seems reasonable to follow
> Saunders and assign 1/4, 1/4, and 1/2 to the probabilities of E, E', and
> E'' respectively. But consider after copying, when you're one of the three
> copies of A1 but don't know which one yet. I think anyone who has worked
> with computers will say that all exact copies are equivalent, and the
> "history" of how the copies are done is irrelevent. Thus there is a strong
> intuition that after copying, the probabilities should be 1/3, 1/3, 1/3.
>
> 4. Something similar to 3 happens with quantum suicide. Suppose you do two
> independent spin measurements, creating four branches, and label them
> (0,0),(0,1),(1,0),(1,1) according to the results of the measurements. And
> suppose you set up your quantum suicide machine to tell you the result of
> the first measurement, kill you if you're in branch (0,0) and then tell
> you the result of the second measurement. Before the experiment begins, it
> seems reasonable to believe that the probabilities of ending up in
> (0,1),(1,0),(1,1) are 1/2, 1/4, and 1/4, but afterwards it seems they
> should be 1/3, 1/3, and 1/3. (BTW, what is the answer according to the QS
> axioms?)
>
> 5. The SI perspective does not allow preferences for diversity of
> experience across branches or copies. (This is what I brought up in my
> earlier email.) In the case of copying, this is again an evolutionary
> disadvantage.
>
> So I think the SI perspective is seriously flawed, but as you point out
> the OD perspective also has its problems. Adopt

Re: Quantum Probability and Decision Theory

[Wei Dai]

On Wed, Dec 04, 2002 at 04:00:07PM +0100, Marchal Bruno wrote:
> Have you read the "revisited" paper by Wallace on Everett/decision
> theory? Quite interesting imo, and relevant for some discussion,
> about MWI and decision theory we have had on this list.
> 
> http://philsci-archive.pitt.edu/documents/disk0/00/00/08/85/index.html

Thanks for this pointer. I highly recommend this paper as well, for an
introduction to decision theory and an example its implications.
Unfortunately the author is not aware of some serious problems with the
subjective-indeterministic version of decision theory that he adopts,
which we've discussed on this list in the past. I'll attach an email that
I sent him summarizing the problems with the subjective-indeterministic
view.

---

1. The SI viewpoint is not evolutionarily adaptive if copying is possible. 
Suppose a company invents a non-destructive matter-transporter and offers 
to create copies of paying customers on distant planets with the 
opportunity to colonize them. And suppose the expected living standards on 
the colonized planets would be just slightly lower than those on Earth. 
Those who accept the SI viewpoint would refuse to pay anything for this 
service, since it would lower their expected utility. The universe would
quickly be dominated by the OD viewpoint.

2. A similar issue arises in quantum splitting. In a thought experiment 
that Max Tegmark calls quantum suicide (see his "The Interpretation of 
Quantum Mechanics: Many Worlds or Many Words?" available at 
http://www.hep.upenn.edu/~max/everett.html), the experimenter is killed 
every time a quantum measurement comes out a certain way (say spin up). 
People who accept the SI viewpoint will have no problem with doing this 
experiment. People who accept OD can actually benefit at their expense, 
for example by offering to gamble with the experimenter on the outcome of 
the measurement. The experimenter will believe that the probability of 
spin down is 1, and will accept any odds on a gamble that pays on spin 
down.

3. The SI viewpoint either contradicts van Fraassen's Reflection Principle 
or leads to counterintuitive results. Saunders tries to address this in 
his paper (section 4.3) but I don't think his argument is convincing. 
Consider Fig.1 in his paper (page 15, at 
http://philsci-archive.pitt.edu/documents/disk0/00/00/04/65/ in case you 
don't have it handy). Before the copying, it seems reasonable to follow 
Saunders and assign 1/4, 1/4, and 1/2 to the probabilities of E, E', and 
E'' respectively. But consider after copying, when you're one of the three 
copies of A1 but don't know which one yet. I think anyone who has worked 
with computers will say that all exact copies are equivalent, and the 
"history" of how the copies are done is irrelevent. Thus there is a strong 
intuition that after copying, the probabilities should be 1/3, 1/3, 1/3.

4. Something similar to 3 happens with quantum suicide. Suppose you do two 
independent spin measurements, creating four branches, and label them 
(0,0),(0,1),(1,0),(1,1) according to the results of the measurements. And 
suppose you set up your quantum suicide machine to tell you the result of 
the first measurement, kill you if you're in branch (0,0) and then tell 
you the result of the second measurement. Before the experiment begins, it 
seems reasonable to believe that the probabilities of ending up in 
(0,1),(1,0),(1,1) are 1/2, 1/4, and 1/4, but afterwards it seems they 
should be 1/3, 1/3, and 1/3. (BTW, what is the answer according to the QS 
axioms?)

5. The SI perspective does not allow preferences for diversity of
experience across branches or copies. (This is what I brought up in my
earlier email.) In the case of copying, this is again an evolutionary
disadvantage.

So I think the SI perspective is seriously flawed, but as you point out 
the OD perspective also has its problems. Adopting OD would require 
abandoning our current concept of probability and everything based on it, 
which of course no one wants to do. At this point I'm not sure what the 
answer is. One answer may be that the QS axioms can be thought of as 
approximately describing the preferences of most people, except for their 
preferences about copying and quantum suicide, and so they can use 
probabilities as a tool for making decisions but with the understanding 
that it's only an instrument with limited accuracy and application.

Quantum Probability and Decision Theory

[Marchal Bruno]

Hi Wei Dai,

Have you read the "revisited" paper by Wallace on Everett/decision
theory? Quite interesting imo, and relevant for some discussion,
about MWI and decision theory we have had on this list.

http://philsci-archive.pitt.edu/documents/disk0/00/00/08/85/index.html


Bruno