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 {S\subseteq\mathbb{N}} is simple if {S} is recursively enumerable and its complement {S^c} 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 {S} and such that no computer program can produce infinitely many elements that are not in {S}. By the way, Post introduces the concept of simple set while working on his eponymous problem which Richard mentions. In fact, if {S} is simple set then {S} is not many-one equivalent to a universal recursively enumerable set.

Now let {S} 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 {n}. Then Bob announces {m} and then Alice announces {t}. After the game is played, a winner is determined as follows: Bob wins if {m>n} and {m} is not the {t}-th element in the enumeration of {S}. 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 {n} that Alice might chose in the first round there exists some {m>n} such that {m\notin S}, since the complement of {S} 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 {f:\mathbb{N}\rightarrow\mathbb{N}} that Bob can chose, there exists some {m} such that either {f(m)\leq m} or {f(m)\in S} since otherwise {f(0),f(f(0)),f(f(f(0))),\dots} would have been a recursive enumeration of infinitely many elements of {S^c}. In particular, there exists some {t} such that if Alice plays {m} in the first stage and {t} in the third stage she wins against {f}. So, Bob has no winning strategy.