> > ... there's a known undecidability result (by Bob Hearn) stating that a > game with > > - finite state > > - two teams (with no communication) > > - unbounded horizon > > can be undecidable. The undecidable question is > > "is there a strategy for winning with probability 1 in situation X". > > and an instance is a position X. > > I would be interested in a reference to this result. > > In the book by Hearn & Demaine. There are three players in the game (two in the same team). Sketch of the proof (by reduction to the halting problem): - the two players in a given team try to give a sequence of configurations showing that the Turing machine halts - the third player tries to find a mistake in the sequence of configurations
But as Bob is a reader of this mailing list (I think), he might give a better answer :-) Best regards, Olivier
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
