[Retros] Math aspects of Retro from Yefim Treger 08/21/2004

[Seth Breidbart]

TregerYefim at aol.com wrote:


> I have come to this "at first look unusual" idea: there might exist

> a position which cannot be proved to be legal or illegal.


I don't see how, in theory, since Chess is finite.

If it's legal, there exists a proof that it's legal: a proof game.

Now, if Chess were strong enough to emulate a Universal Turing
Machine, there would be unprovable positions.  But it isn't.  Again,
in theory, all positions could be enumerated; then the graph of which
positions could lead to which other positions drawn; then the
transitive closure of that graph from the starting position
calculated.  But the latter is the set of all legal positions.

Now, if you take "cannot be proved" to include limiting the size of
the proof to something reasonable, then there could be such a
position.

Seth