Loading ...
Sorry, an error occurred while loading the content.
 

Curious point beyond computability

Expand Messages
  • Michael Hruska
    In the light of quantum computing as a reality and improvement being inevitable, we can make some assumptions. Many things that are not computable will become
    Message 1 of 19 , Apr 11, 2007
      In the light of quantum computing as a reality and improvement being
      inevitable, we can make some assumptions.



      Many things that are not computable will become computable (ie. NP Complete
      sets, etc.).



      If all that was necessary to be computed was capable of being computed (we'd
      have to assume a situation where there are adequate software engineers of
      course with skill enough to code any worldly problem with ample logic), we
      may have some interesting situations...



      When computing questions are exhausted what other types of questions could
      be asked?



      A few, right?. Well... there would have to be a "computable" answer.



      So, you can rule out some questions. But, what can you rule in?

      "What do I do next?" - Is that acceptable (I urge you to dig for some..)



      What answers would remain for this question set?









      [Non-text portions of this message have been removed]
    • Bruno Marchal
      ... This is wrong. Quantum computer does not violate Church s thesis, so that they compute the same class of computable functions than classical universal
      Message 2 of 19 , Apr 13, 2007
        Le 12-avr.-07, à 18:58, Michael Hruska a écrit :

        > In the light of quantum computing as a reality and improvement being
        > inevitable, we can make some assumptions.
        >
        > Many things that are not computable will become computable (ie. NP
        > Complete
        > sets, etc.).


        This is wrong. Quantum computer does not violate Church's thesis, so
        that they compute the same class of computable functions than classical
        universal machine.
        Perhaps you were talking about "practical computability"? Indeed in
        this case quantum computer seems to be able to compute more quicky some
        class of function (but caution, this does not include the NP
        complete!).




        >
        > If all that was necessary to be computed was capable of being
        > computed (we'd
        > have to assume a situation where there are adequate software
        > engineers of
        > course with skill enough to code any worldly problem with ample
        > logic), we
        > may have some interesting situations...
        >
        > When computing questions are exhausted what other types of questions
        > could
        > be asked?
        >
        > A few, right?. Well... there would have to be a "computable" answer.
        >
        > So, you can rule out some questions. But, what can you rule in?
        >
        > "What do I do next?" - Is that acceptable (I urge you to dig for
        > some..)
        >
        > What answers would remain for this question set?
        >
        > [Non-text portions of this message have been removed]


        Perhaps you could elaborate? You are not quite clear here. I think that
        you should distinguish computing and proving. The universality of the
        notion of computability entails the necessary NON universality of
        provability, so that "after" having computed everything computable it
        remains an infinity (even a transfinity) of unsolved problems, even in
        the restricted area of number or machine theory. Ask if you want I
        clarify this.


        Bruno


        http://iridia.ulb.ac.be/~marchal/


        [Non-text portions of this message have been removed]
      • Michael Bacon
        In Fabric-of-Reality@yahoogroups.com, Bruno Marchal ... However, at least in theory it may be possible (if a quantum computer has access to
        Message 3 of 19 , Apr 13, 2007
          In Fabric-of-Reality@yahoogroups.com, Bruno Marchal <marchal@...>
          wrote:

          > Indeed in this case quantum computer seems to be able to compute
          > more quicky some class of function (but caution, this does not
          > include the NP complete!

          However, at least in theory it may be possible (if a quantum
          computer has access to closed timelike curve qubits) to compute NP
          complete problems in practice. Dave Bacon has written a paper that
          says:

          "Quantum computation with quantum data that can traverse closed
          timelike curves represents a new physical model of computation. We
          argue that a model of quantum computation in the presence of closed
          timelike curves can be formulated which represents a valid
          quantification of resources given the ability to construct compact
          regions of closed timelike curves. The notion of self-consistent
          evolution for quantum computers whose components follow closed
          timelike curves, as pointed out by Deutsch [Phys. Rev. D 44, 3197
          (1991)], implies that the evolution of the chronology respecting
          components which interact with the closed timelike curve components
          is nonlinear. We demonstrate that this nonlinearity can be used to
          efficiently solve computational problems which are generally thought
          to be intractable. In particular we demonstrate that a quantum
          computer which has access to closed timelike curve qubits can solve
          NP-complete problems with only a polynomial number of quantum gates."

          Do closed timelike curves exist? Can they be harnessed? I don't
          know. But if they do and if they can, then given some time, we may
          figure out a way to do it.

          You can find his paper here: http://arxiv.org/PS_cache/quant-
          ph/pdf/0309/0309189v3.pdf

          Best regards,
          Michael Bacon (no relation to Dave)
        • DJ
          ... I have nothing like the math expertise to comment at the heady levels generally seen here; mine is a lay interest, since David s book was quite accessible.
          Message 4 of 19 , Apr 14, 2007
            >Do closed timelike curves exist? Can they be harnessed? I don't
            >know. But if they do and if they can, then given some time, we may
            >figure out a way to do it.
            >
            >You can find his paper here:
            ><http://arxiv.org/PS_cache/quant->http://arxiv.org/PS_cache/quant-
            >ph/pdf/0309/0309189v3.pdf
            >
            >Best regards,
            >Michael Bacon (no relation to Dave)

            I have nothing like the math expertise to comment at the heady levels
            generally seen here; mine is a lay interest, since David's book was
            quite accessible. So pardon any comments which may be too elementary
            to be replied to; no response is necessary.

            So saying, in general, I thought that closed timelike loops would not
            be considered a violation of causality specifically due to the MWI
            interpretetation; that on a macro scale at least, something like time
            travel would involve no paradoxes per se since you wouldn't actually
            be travelling into your 'own' past.

            But even if I understand that correctly, I'm not sure whether it
            applies at the eensy-teensy level, where there may be extreme
            fungibility between which entity is which.

            So under MWI, would a closed timelike loop by a quantum system just
            obey the standard splitting of worldlines as it seemingly must, or
            would it create a 'new' worldline? Seems like it should be the
            former, if they exist...

            but again, I'm 'way out of my depth.

            still, it's interesting to TRY thinking about....

            dj

            [Non-text portions of this message have been removed]
          • Charles Goodwin
            For those of us without the necessary expertise to follow physics papers in detail, there was a cover article in the 31/3 New Scientist about a computer that
            Message 5 of 19 , Apr 14, 2007
              For those of us without the necessary expertise to follow physics papers in
              detail, there was a cover article in the 31/3 New Scientist about a computer
              that would use quantum gravity to (in theory) "give answers before they were
              asked", and which quotes David Deutsch and Lucien Hardy (who has a recent
              paper at www.arxiv.org/abs/quant-ph/0701019 for those who can follow them).

              (Harnessing closed timelike curves would of course allow all sorts of
              interesting things to happen, not just in computation....see "Doctor Who"
              for further details!)

              Charles

              > -----Original Message-----
              > From: Fabric-of-Reality@yahoogroups.com [mailto:Fabric-of-
              > Reality@yahoogroups.com] On Behalf Of Michael Bacon
              > Sent: Saturday, 14 April 2007 7:26 a.m.
              > To: Fabric-of-Reality@yahoogroups.com
              > Subject: Re: Curious point beyond computability
              >
              > In Fabric-of-Reality@yahoogroups.com, Bruno Marchal <marchal@...>
              > wrote:
              >
              > > Indeed in this case quantum computer seems to be able to compute
              > > more quicky some class of function (but caution, this does not
              > > include the NP complete!
              >
              > However, at least in theory it may be possible (if a quantum
              > computer has access to closed timelike curve qubits) to compute NP
              > complete problems in practice. Dave Bacon has written a paper that
              > says:
              >
              > "Quantum computation with quantum data that can traverse closed
              > timelike curves represents a new physical model of computation. We
              > argue that a model of quantum computation in the presence of closed
              > timelike curves can be formulated which represents a valid
              > quantification of resources given the ability to construct compact
              > regions of closed timelike curves. The notion of self-consistent
              > evolution for quantum computers whose components follow closed
              > timelike curves, as pointed out by Deutsch [Phys. Rev. D 44, 3197
              > (1991)], implies that the evolution of the chronology respecting
              > components which interact with the closed timelike curve components
              > is nonlinear. We demonstrate that this nonlinearity can be used to
              > efficiently solve computational problems which are generally thought
              > to be intractable. In particular we demonstrate that a quantum
              > computer which has access to closed timelike curve qubits can solve
              > NP-complete problems with only a polynomial number of quantum gates."
              >
              > Do closed timelike curves exist? Can they be harnessed? I don't
              > know. But if they do and if they can, then given some time, we may
              > figure out a way to do it.
              >
              > You can find his paper here: http://arxiv.org/PS_cache/quant-
              > ph/pdf/0309/0309189v3.pdf
              >
              > Best regards,
              > Michael Bacon (no relation to Dave)
              >
              >
              >
              >
              > Yahoo! Groups Links
              >
              >
              >
            • Bruno Marchal
              I think you are asking a very difficult but quite interesting question. Strictly speaking QM and General Relativity have not yet been clearly made compatible,
              Message 6 of 19 , Apr 17, 2007
                I think you are asking a very difficult but quite interesting question.
                Strictly speaking QM and General Relativity have not yet been clearly
                made compatible, so "experts" have no definite answers on this point
                yet (I think).
                David Deutsch considers that there is no "universe splitting", only
                differentiations, so that a closed timelike loop should resemble to an
                infinite (in string theory) or perhaps finite (in loop gravity theory)
                set of "parallel" circles. Time travel paradox would not occur, like in
                FOR, but I am not sure some other difficulties would not be raised by
                making possible to move from circle to another. May be physicist could
                say more here.

                Bruno

                Le 14-avr.-07, à 22:17, DJ a écrit :

                > >Do closed timelike curves exist? Can they be harnessed? I don't
                > >know. But if they do and if they can, then given some time, we may
                > >figure out a way to do it.
                > >
                > >You can find his paper here:
                > ><http://arxiv.org/PS_cache/quant->http://arxiv.org/PS_cache/quant-
                > >ph/pdf/0309/0309189v3.pdf
                > >
                > >Best regards,
                > >Michael Bacon (no relation to Dave)
                >
                > I have nothing like the math expertise to comment at the heady levels
                > generally seen here; mine is a lay interest, since David's book was
                > quite accessible. So pardon any comments which may be too elementary
                > to be replied to; no response is necessary.
                >
                > So saying, in general, I thought that closed timelike loops would not
                > be considered a violation of causality specifically due to the MWI
                > interpretetation; that on a macro scale at least, something like time
                > travel would involve no paradoxes per se since you wouldn't actually
                > be travelling into your 'own' past.
                >
                > But even if I understand that correctly, I'm not sure whether it
                > applies at the eensy-teensy level, where there may be extreme
                > fungibility between which entity is which.
                >
                > So under MWI, would a closed timelike loop by a quantum system just
                > obey the standard splitting of worldlines as it seemingly must, or
                > would it create a 'new' worldline? Seems like it should be the
                > former, if they exist...
                >
                > but again, I'm 'way out of my depth.
                >
                > still, it's interesting to TRY thinking about....
                >
                > dj
                >
                > [Non-text portions of this message have been removed]
                >
                >
                http://iridia.ulb.ac.be/~marchal/


                [Non-text portions of this message have been removed]
              • Russell Standish
                I would have thought the image is one of a spiral. Go around the spiral, and one is at the same (x,y) coordinates, but shifted one level in the z. For those
                Message 7 of 19 , Apr 17, 2007
                  I would have thought the image is one of a spiral. Go around the
                  spiral, and one is at the same (x,y) coordinates, but shifted one
                  level in the z.

                  For those who've studied complex analysis, think of the logarithmic
                  function on the comnplex plane. Starting from a real number, follow a
                  loop around zero ending back at the same real number. The analytic
                  continuation of the logarithmic function will have an imaginary
                  component added to the real value of log(x).

                  Quite how this fits into a "no-splitting" picture, I'm really not
                  sure. All I can think of is that splitting is not physical splitting,
                  but splitting of observers, but I find DD particularly incoherent on
                  this point.

                  Cheers

                  On Tue, Apr 17, 2007 at 03:49:41PM +0200, Bruno Marchal wrote:
                  > I think you are asking a very difficult but quite interesting question.
                  > Strictly speaking QM and General Relativity have not yet been clearly
                  > made compatible, so "experts" have no definite answers on this point
                  > yet (I think).
                  > David Deutsch considers that there is no "universe splitting", only
                  > differentiations, so that a closed timelike loop should resemble to an
                  > infinite (in string theory) or perhaps finite (in loop gravity theory)
                  > set of "parallel" circles. Time travel paradox would not occur, like in
                  > FOR, but I am not sure some other difficulties would not be raised by
                  > making possible to move from circle to another. May be physicist could
                  > say more here.
                Your message has been successfully submitted and would be delivered to recipients shortly.