Xref: utzoo sci.math:11893 comp.theory:919
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uunet!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!function.mps.ohio-state.edu!rld
From: rld@function.mps.ohio-state.edu (Randall L Dougherty)
Newsgroups: sci.math,comp.theory
Subject: Re: Infinite games
Keywords: Determinacy, Borel games.
Message-ID: <1990Aug4.070937.6798@zaphod.mps.ohio-state.edu>
Date: 4 Aug 90 07:09:37 GMT
References: <1033@fornax.UUCP>
Sender: usenet@zaphod.mps.ohio-state.edu
Organization: Dept of Mathematics, The Ohio State University
Lines: 57

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. 

A more standard way of stating this question would be: do computable
closed games have computable winning strategies?  A closed set is considered
to be computable if there is an algorithm for generating a list (probably
infinite) of basic open sets whose union is the complement of the given
closed set.

It turns out that the answer to this is negative.  There are computable
clopen games (both the winning set and its complement are computable closed
sets) such that neither player has a computable winning strategy.  In
fact, to find winning strategies for all computable clopen games,
one has to go arbitrarily high up in the hyperarithmetic hierarchy
(the computable analogue of the Borel hierarchy; level 0 is the
recursive sets, level 1 is the recursively enumerable sets and their
complements, etc.).  This result appears as 6E.8 from "Descriptive
Set Theory" by Y. Moschovakis.

This also gives a negative answer to the original formulation above.
If we are given a computable clopen game such that player I has a
winning strategy but no computable winning strategy, then any
given strategy for player II must fail, and in fact must fail after
finitely many steps, since the game is clopen.  To find a strategy
for player I which beats this strategy for II, just search through
all finite sequences of moves until one is found for which II's
strategy has already failed; this is clearly a computable process.
On the other hand, since no computable strategy for I is a
winning strategy, the same argument shows that, given a computable
strategy for I, II can find a computable strategy which beats it
(just search for a suitable finite sequence of moves and then
always play 0).

Given these results, it is unlikely that any nontrivial reformulation
of the original question (without drastic restrictions) will have a
positive answer.


Randall Dougherty                       [Disclaimer out of order]
Internet: rld@function.mps.ohio-state.edu
UUCP: ...!{att,pyramid}!osu-cis!function.mps.ohio-state.edu!rld
"I have yet to see any problem, however complicated, that when looked at in the
right way didn't become still more complicated."  Poul Anderson, "Call Me Joe"