kummer@.ira.uka.de (Martin Kummer) (08/07/90)
In article <1033@fornax.UUCP> mahajan@fornax.UUCP (Sanjeev Mahajan) writes: >It is known (I forget the reference) that all Borel games are determinate, ... >My question is this: Let us, for simplicity, consider only closed games. ... >the argument that 'there is a first move ...' is in some vague sense >non-constructive. So my question is, is there a constructive version >of this theorem, or does the question even make sense. One way >of formulating the constructive version would be as follows: if >for all computable strategies s of player II, one can uniformly compute, >in a recursive index of s, a computable strategy s' of player I such that >player II does not win then one can construct (uniformly in an index of >the algorithm that computes s' from s) a computable strategy for player I >such that for all computable strategies of player II, player I wins. >If this statement is not true, can it be modified in some non-trivial way, >so that it is true. In article <1990Aug4.070937.6798@zaphod.mps.ohio-state.edu> Randell Dougherty points out that every recursive clopen game, such that neither player has a recursive winning strategy, is a counterexample to the proposed constructive version above. A quite easy special case is provided by the following 3-round game which is essentially due to Rabin (1957) : Let f be a total recursive function which enumerates an r.e. nonrecursive set. Two Players W and B. Round 1: W chooses n Round 2: B chooses k Round 3: W chooses m W wins iff f(m)=n and not f(k)=n. Clearly, B has a winning strategy. Given any recursive strategy s for B one can compute a strategy for W which beats s, and vice versa. Finally I would like to enclose an exercise concerning recursive strategies for truly infinite games: Given a set M of natural numbers. Players W and B alternately choose finite sets of natural numbers disjoint with any previously chosen set. The game lasts infinitely many rounds. Let U denote the union of all sets chosen by W. W wins iff the intersection of U and M is infinite. Characterize those sets M such that W has a recursive winning strategy. Martin Kummer