Re: Quantum Probability and Decision Theory
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 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. [SPK] Where is this explained? Please, some papers that you did not write... If you simulate
Re: Quantum Probability and Decision Theory
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 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/dialupxAPID=42PS=47575PI=7324DI=7474SU= http://www.hotmail.msn.com/cgi-bin/getmsgHL=1216hotmailtaglines_newmsn8ishere_3mf
Re: Quantum Probability and Decision Theory
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/featuredemailxAPID=42PS=47575PI=7324DI=7474SU= http://www.hotmail.msn.com/cgi-bin/getmsgHL=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
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
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
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
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
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 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/junkmailxAPID=42PS=47575PI=7324DI=7474SU= http://www.hotmail.msn.com/cgi-bin/getmsgHL=1216hotmailtaglines_advancedjmf_3mf
RE: Quantum Probability and Decision Theory
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/featuredemailxAPID=42PS=47575PI=7324DI=7474SU= http://www.hotmail.msn.com/cgi-bin/getmsgHL=1216hotmailtaglines_addphotos_3mf
RE: Quantum Probability and Decision Theory
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
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/virusxAPID=42PS=47575PI=7324DI=7474SU= http://www.hotmail.msn.com/cgi-bin/getmsgHL=1216hotmailtaglines_eliminateviruses_3mf
Re: Quantum Probability and Decision Theory
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
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
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
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
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
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: 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: http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node23.html ... It is suspected but not yet known that factoring is NP-complete.
Re: Quantum Probability and Decision Theory
http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node23.html ... It is suspected but not yet known that factoring is NP-complete. Of course, if factoring were to be shown NP-complete and quantum computers could be built to run Shor's factoring algorithm in polynomial time, then quantum computers could solve all NP-complete problems in polynomial time. Big advance for quantum computation.
Re: Quantum Probability and Decision Theory
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
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
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
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, 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
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
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/~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
Re: Quantum Probability and Decision Theory
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
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
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
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
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
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
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: http://www.ceptualinstitute.com/uiu_plus/evolcons.htm (1996) Jamie Rose Ceptual Institute Dec 23, 2002
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. 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.
Re: Quantum Probability and Decision Theory
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. 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