Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: A story about Python... sort of

Reply
Thread Tools

Re: A story about Python... sort of

 
 
John J Lee
Guest
Posts: n/a
 
      07-07-2003
On Mon, 7 Jul 2003, Bob Gailer wrote:

> At 01:48 PM 7/7/2003 +0100, John J. Lee wrote:
>
> >"Tony Meyer" <(E-Mail Removed)> 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


 
Reply With Quote
 
 
 
 
Erik Max Francis
Guest
Posts: n/a
 
      07-07-2003
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.velocityreviews.com/forums/(E-Mail Removed) && http://www.alcyone.com/max/
__ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
/ \ Said it? yep / Regret it? nope
\__/ Ice Cube
 
Reply With Quote
 
 
 
 
JanC
Guest
Posts: n/a
 
      07-08-2003
John J Lee <(E-Mail Removed)> 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
 
Reply With Quote
 
Russell Reagan
Guest
Posts: n/a
 
      07-08-2003
"John J Lee" <(E-Mail Removed)> 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.


 
Reply With Quote
 
John J. Lee
Guest
Posts: n/a
 
      07-08-2003
"Russell Reagan" <(E-Mail Removed)> writes:

> "John J Lee" <(E-Mail Removed)> 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
 
Reply With Quote
 
John J. Lee
Guest
Posts: n/a
 
      07-08-2003
[utterly OT, but couldn't resist replying again]

Erik Max Francis <(E-Mail Removed)> 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
 
Reply With Quote
 
Michele Simionato
Guest
Posts: n/a
 
      07-09-2003
(E-Mail Removed) (John J. Lee) wrote in message news:<(E-Mail Removed)>...
> [utterly OT, but couldn't resist replying again]
>
> Erik Max Francis <(E-Mail Removed)> 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
 
Reply With Quote
 
John J. Lee
Guest
Posts: n/a
 
      07-10-2003
(E-Mail Removed) (Michele Simionato) writes:
[...]
> Why do you disagree? I would think Erik is right.


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


John
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Tell Your Story - Wondershare Released Photo Story Platinum kena Digital Photography 0 06-12-2007 08:42 AM
Newsweek Story just that a Story Mark Test Digital Photography 21 05-22-2005 02:39 PM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM
RE: A story about Python... sort of Tony Meyer Python 8 07-10-2003 09:53 AM
A story about Python... sort of Max M Python 21 07-07-2003 04:19 PM



Advertisments