A story about Python... sort of

[John J Lee]

On Mon, 7 Jul 2003, Bob Gailer wrote:

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

<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