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