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.
4 comments
April 21, 2010 at 1:34 pm
Jonathan Weinstein
Sometimes people really don’t know what to call something, and they come up with the silliest terms. “Simple”? The idea here is: we know enumerating the complement of an r.e. set may be impossible. Here not only is that impossible, it’s impossible to even enumerate an infinite subset. In other words, it’s really *hard* to identify elements not in S. Simple, indeed.
If I had to try to justify “simple,” I suppose I would note that S^c can’t be decomposed into finitely many r.e. sets. Kind of reminiscent of a simple group. Very vaguely.
It’s interesting to think a little further about Bob’s dilemma. He can’t identify for sure an element not in S. What he can do is make Alice work hard to prove him wrong. He can, for any computable function t(n), play an m which is not one of the first t(n) elements enumerated in S. Then Alice will have to work harder than t(n) to prove him wrong, if he is unlucky and the element is actually in S.
April 21, 2010 at 2:34 pm
Eran
I was also wondering about `simple’.. maybe it’s because S itself is recursively enumerable so it is simple to produce elements of S. So, compared to other sets that have the property that their complement does not contain infinite r.e sets, S is simple.
but i guess with this kind of justification everything can be called simple.
April 22, 2010 at 3:13 am
Vladimir Nesov
Consider the notions of strategy that apply to Alice, particularly in the second case where “Bob has no winning strategy”. How do you define Alice’s winning strategy for that case? What if Bob can look at that strategy (which requires again redefining the notion of Bob’s strategy)?
April 22, 2010 at 5:36 pm
Eran
The fact that Bob has no winning strategy doesn’t mean that Alice has a winning strategy. It only mean that for every strategy of Bob, Alice has a strategy that beats him. But then Bob can change to a strategy that beats Alice’s.
A similar situation occurs when we play a game in which you and I simultaneously chose a natural number and then the person who chose a higher number wins. If I know in advance what you are going to do I can win, and if you know what I am going to do you can win.
The difference is that in the game described by Rabin, there are no simultaneous moves