Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)

 John J Lee 07-07-2003 10:11 PM

Re: A story about Python... sort of

On Mon, 7 Jul 2003, Bob Gailer wrote:

> At 01:48 PM 7/7/2003 +0100, John J. Lee wrote:
>
> >"Tony Meyer" <ta-meyer@ihug.co.nz> 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...

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

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

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

 Erik Max Francis 07-07-2003 11:46 PM

Re: A story about Python... sort of

John J Lee wrote:

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

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 && max@alcyone.com && http://www.alcyone.com/max/
__ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
/ \ Said it? yep / Regret it? nope
\__/ Ice Cube

 JanC 07-08-2003 02:57 AM

Re: A story about Python... sort of

John J Lee <jjl@pobox.com> 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

 Russell Reagan 07-08-2003 03:33 AM

Re: A story about Python... sort of

"John J Lee" <jjl@pobox.com> 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.

 John J. Lee 07-08-2003 01:16 PM

Re: A story about Python... sort of

"Russell Reagan" <rreagan@attbi.com> writes:

> "John J Lee" <jjl@pobox.com> 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 07-08-2003 01:32 PM

Re: A story about Python... sort of

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

Erik Max Francis <max@alcyone.com> 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

 Michele Simionato 07-09-2003 09:44 PM

Re: A story about Python... sort of

jjl@pobox.com (John J. Lee) wrote in message news:<87smphp2in.fsf@pobox.com>...
> [utterly OT, but couldn't resist replying again]
>
> Erik Max Francis <max@alcyone.com> 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

 John J. Lee 07-10-2003 12:51 PM

Re: A story about Python... sort of

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

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

John

 All times are GMT. The time now is 10:53 AM.