I wrote some time ago about Michael Rabin’s example of how a backward induction argument is killed when you require players’ plans to be computable. Since Rabin’s paper is not available online, I intended to post the proof at some point, but never actually got to do it. Richard Lipton’s post about Emil Post is a good inspiration to pay that debt since the concept of simple set, which was introduced by Post, has a role in Rabin’s example.
A set is simple if is recursively enumerable and its complement is infinite and contains no infinite recursively enumerable subset.
For Rabin’s purpose, what matters is that Post proved the existence of such a set. So Post provides us with a code of a computer program that enumerates over all the elements of and such that no computer program can produce infinitely many elements that are not in . By the way, Post introduces the concept of simple set while working on his eponymous problem which Richard mentions. In fact, if is simple set then is not many-one equivalent to a universal recursively enumerable set.
Now let be a simple set and consider the following three-round game with perfect information. At each round a player announces a natural number (an action): First Alice announces . Then Bob announces and then Alice announces . After the game is played, a winner is determined as follows: Bob wins if and is not the -th element in the enumeration of . Otherwise, Alice wins. Therefore, determining the winner is a task that can be effectively done using the code provided by Post.
Does any of the players have a strategy that guarantee winning regardless of how the opponent play ? The answer to this question depends on which mathematical creature you use to model the intuitive notion of `strategy’.
If by a strategy you mean just a function from histories to current action then Bob has a winning strategy: for every that Alice might chose in the first round there exists some such that , since the complement of is infinite.
But if you think of a strategy as a complete set of instructions, that is a plan or an algorithm that will tell you how to produce your next action given the past, then you want to model a strategy as a computable function. Now, for every computable function that Bob can chose, there exists some such that either or since otherwise would have been a recursive enumeration of infinitely many elements of . In particular, there exists some such that if Alice plays in the first stage and in the third stage she wins against . So, Bob has no winning strategy.