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.