Re: A story about Python... sort of

Discussion in 'Python' started by John J Lee, Jul 7, 2003.

  1. John J Lee

    John J Lee Guest

    On Mon, 7 Jul 2003, Bob Gailer wrote:

    > At 01:48 PM 7/7/2003 +0100, John J. Lee wrote:
    >
    > >"Tony Meyer" <> writes:

    [...]
    > >No matter how distant, it's nowhere near as far off as 'solving' chess
    > >(which is no doubt physically impossible, at least with classical
    > >(Turing machine) computation).

    >
    > Physically impossible? or impractical. If it can be solved by Turing
    > machine computation then it is physically possible, even though it might
    > take more time/resources than anyone cares to expend.


    I really did mean impossible, not impractical (barring a drastic pruning
    of the space of possible games, of course).

    What is computable depends on the laws of physics. A complete
    (brute-force) Turing-machine (ie. classical) enumeration of all possible
    chess games (as opposed to a quantum computation) would probably take more
    computational resources than our universe has to offer. My excuse for not
    attempting to work out the number of chess games is that my undergrad
    maths books are currently propping up the monitor I'm using to write this
    <0.5 wink>. A Google result (appropriately enough, given the origin of
    the name Google) suggested 10**120, and I seem to have a number in my head
    of 10**80 non-virtual particles in the universe (though I've no
    recollection where *that* number came from either!-). That's 10**40 chess
    games for every particle in the universe, which is quite a lot <wink>.
    If you took over the universe and did nothing else with it but play chess
    games, you'd still never finish the problem. In other words, it's
    physically impossible to do it.

    Possibly there is a quantum algorithm that makes use of many universes to
    solve the problem, though (no I'm not joking: the many-worlds
    'interpretation' is widely accepted amongst physicists working on quantum
    computation).

    Wait a minute...

    <google result="http://www.qubit.org/people/david/Articles/Frontiers.html#correction">

    [...] Scott Aaronson at UC Berkeley has since drawn my attention to some
    comments by Richard Cleve (quant-ph/9906111) pointing out that chess and
    chess-like games (with a fixed number of choices per move, especially if
    this number is small) are not very suitable for speedup by Grover
    searching. At best one would expect a speedup by a moderate, fixed factor.
    This does not rule out quantum chess-playing algorithms altogether, just
    algorithms based on Grover-accelerated brute-force searching. But there is
    no special reason to expect better quantum chess algorithms to exist.

    </google>

    So, it seems quite plausible that complete solution of the chess problem
    is flat-out physically impossible.

    Very readable talk by David Deutsch (founder of the theory of universal
    quantum computers) about the relationship between physics and computation:

    http://www.qubit.org/people/david/Articles/PPQT.pdf

    And his home page:

    http://www.qubit.org/people/david/David.html


    > But remember "When Harley Was One" and he invented the G.O.D.?


    I don't get the reference there.


    John
    John J Lee, Jul 7, 2003
    #1
    1. Advertising

  2. John J Lee wrote:

    > A Google result (appropriately enough, given the origin of
    > the name Google) ...


    But the origin of the name was generated from a misspelling of _googol_
    (the name for 10^100), which evidently was found via Web searches. So
    the origin of the name of the search engine

    > ... suggested 10**120, and I seem to have a number in my head
    > of 10**80 non-virtual particles in the universe (though I've no
    > recollection where *that* number came from either!-).


    Typically the total number of elementary particles in the observable
    Universe is given as 10^80. But when you're talking about such rough
    estimates, the difference between 10^80, 10^100, and 10^120, although
    incredibly huge, aren't all that much. What's twenty or forty orders of
    magnitude between friends?

    Note that the qualification "observable Universe" here is crucial. We
    can only see to the edge of the cosmological horizon, where due to
    cosmological expansion, particles are receding at greater than the speed
    of light. This is due to the finiteness of the speed of light and the
    fact that the Universe is not infinitely old. As time progresses, we'll
    see more of the Universe, and so the observable Universe will increase
    in size.

    In standard Friedmann-Robertson-Walker models, you have open, flat, or
    closed universes. Recent observations seem to suggest that we live in
    an open universe -- one which will continue to expand forever until
    matter itself decays. In FRW models, open (and flat) universes have
    infinite spatial extent. So, presuming we live in a universe that
    follows this models, the true Universe is infinitely large, even though
    we can only see a finite, small part of it.

    > Possibly there is a quantum algorithm that makes use of many universes
    > to
    > solve the problem, though (no I'm not joking: the many-worlds
    > 'interpretation' is widely accepted amongst physicists working on
    > quantum
    > computation).


    Since it's an interpretation, though, it's just an intuitive way of
    looking at the situation. Quantum mechanical interpretations do not
    modify the theory itself; that is, they neither add nor subtract
    anything from the theory which is testable in any way.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    __ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
    / \ Said it? yep / Regret it? nope
    \__/ Ice Cube
    Erik Max Francis, Jul 8, 2003
    #2
    1. Advertising

  3. John J Lee

    JanC Guest

    John J Lee <> schreef:

    >> But remember "When Harley Was One" and he invented the G.O.D.?

    >
    > I don't get the reference there.


    It's a SF-novel from 1972 by David Gerrold, about a intelligent computer
    creating a new computer "intelligence" far superior to what any human being
    can understand.

    BTW: this book was also the first time a "computer virus" was mentioned.

    --
    JanC

    "Be strict when sending and tolerant when receiving."
    RFC 1958 - Architectural Principles of the Internet - section 3.9
    JanC, Jul 8, 2003
    #3
  4. "John J Lee" <> wrote:

    > A Google result (appropriately enough, given the origin of
    > the name Google) suggested 10**120


    10**120 is the estimate of "paths", or "games", not "positions". The
    estimate of unique positions is 10**40, give or take. I don't recall whether
    that figure includes illegal positions that could never exist in a legal
    game of chess.
    Russell Reagan, Jul 8, 2003
    #4
  5. John J Lee

    John J. Lee Guest

    "Russell Reagan" <> writes:

    > "John J Lee" <> wrote:
    >
    > > A Google result (appropriately enough, given the origin of
    > > the name Google) suggested 10**120

    >
    > 10**120 is the estimate of "paths", or "games", not "positions". The
    > estimate of unique positions is 10**40, give or take. I don't recall whether

    [...]

    Yeah. The previous couple of lines you snipped from my post:

    | attempting to work out the number of chess games is that my undergrad
    ^^^^^^^^^^^^^^^^^^^^^

    | maths books are currently propping up the monitor I'm using to write this
    | <0.5 wink>. A Google result (appropriately enough, given the origin of
    | the name Google) suggested 10**120, and I seem to have a number in my head


    John
    John J. Lee, Jul 8, 2003
    #5
  6. John J Lee

    John J. Lee Guest

    [utterly OT, but couldn't resist replying again]

    Erik Max Francis <> writes:

    > John J Lee wrote:
    >
    > > A Google result (appropriately enough, given the origin of
    > > the name Google) ...

    >
    > But the origin of the name was generated from a misspelling of _googol_
    > (the name for 10^100), which evidently was found via Web searches. So
    > the origin of the name of the search engine


    Yeah -- I just meant they're both pretty large numbers.


    [...]
    > infinite spatial extent. So, presuming we live in a universe that
    > follows this models, the true Universe is infinitely large, even though
    > we can only see a finite, small part of it.


    True, though infinite spatial extent doesn't necessarily mean infinite
    computation, of course (though it's true people have claimed both open
    and closed universes allow, or require, infinite computation). I
    suppose a lot of this is up for grabs ATM, with the recent discoveries
    about the cosmological constant &c. Still, questions like 'is chess
    physically solveable' (in a sense I hope we all grok by this point in
    the thread) are questions about physics, which I guess is the real
    point I was making to the guy I was replying to. <irony>Doubtless
    he'll put that insight to use in his next Python script.</irony>


    [...]
    > Since it's an interpretation, though, it's just an intuitive way of
    > looking at the situation. Quantum mechanical interpretations do not
    > modify the theory itself; that is, they neither add nor subtract
    > anything from the theory which is testable in any way.


    I disagree with all of that. Further discussion taken off-list!


    John
    John J. Lee, Jul 8, 2003
    #6
  7. (John J. Lee) wrote in message news:<>...
    > [utterly OT, but couldn't resist replying again]
    >
    > Erik Max Francis <> writes:
    >
    > [...]
    > > Since it's an interpretation, though, it's just an intuitive way of
    > > looking at the situation. Quantum mechanical interpretations do not
    > > modify the theory itself; that is, they neither add nor subtract
    > > anything from the theory which is testable in any way.

    >
    > I disagree with all of that. Further discussion taken off-list!
    >
    >
    > John


    Why do you disagree? I would think Erik is right.
    BTW, speaking as a physicist, I would say that the many-worlds
    interpretation is absolutely minoritary in the community: If it
    was wideaspread, I would have studied it ;)
    The only thing I know is that there is no relativistic
    extension and this killed any further interest of mine.


    Michele
    Michele Simionato, Jul 9, 2003
    #7
  8. John J Lee

    John J. Lee Guest

    (Michele Simionato) writes:
    [...]
    > Why do you disagree? I would think Erik is right.


    Off-list, please! (yeah, I'm a hypocrite)


    John
    John J. Lee, Jul 10, 2003
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Max M

    A story about Python... sort of

    Max M, Jul 3, 2003, in forum: Python
    Replies:
    21
    Views:
    807
    Dave Brueck
    Jul 7, 2003
  2. Tony Meyer

    RE: A story about Python... sort of

    Tony Meyer, Jul 7, 2003, in forum: Python
    Replies:
    8
    Views:
    299
    Anton Vredegoor
    Jul 10, 2003
  3. Peter Hansen
    Replies:
    1
    Views:
    320
    Robert Oschler
    Jul 11, 2003
  4. Replies:
    8
    Views:
    332
  5. Navin
    Replies:
    1
    Views:
    675
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page