Let be a function that takes as input a set of nonnegative integers A and returns the set of indices of all recursively enumerable subsets of A. i.e.

(A) = {z | Wz A}.

Let f be a one-to-one total recursive function. The center Cf of f is the smallest set of nonnegative integers such that

1. Every index of the empty set is in Cf and

2. If A Cf , then f((A)) Cf . (f((A)) is the f-image of (A).)

We will partition Cf into levels: The lowest level is the set of indices of the empty set; i.e. z is in the lowest level of Cf if, and only if, Wz = . Given a level L of Cf , there is a uniquely determined next level defined to be f((L)). Given any set of levels of Cf there is a uniquely determined limit level of this collection defined to be the union of the levels in the collection.

Suppose we give names to the levels such that no two levels have the same name. What the names specifically are doesnt matter. Let be the collection of names. Given a name , let L be the level with name . Let V . We then get a set of levels {Lv | v V }. Denote the limit level {Lv | v V } by lim vV Lv.

Theorem: (DO NOT PROVE THIS THEOREM: take it as given.)

1. Every element of Cf is in some level.

2. In any nonempty set of levels of Cf there is a least level with respect to set-inclusion.

3. Let z Cf . Every element n of Wz is a member of a level lower than the least level in which z is a member.

We can play the chicken game on Cf . Play alternates by starting with an arbitrary element of Cf and successively choosing elements in lower and lower levels: if z is chosen then the next player must choose an element of Wz. If there is nothing in Wz to choose, the last player must have chosen an index of the empty set and wins.

Prove that (1) play must terminate. (2) The number of dollars won has no upper bound. (3) It is undecidable whether play has terminated. HINT: If play does not always terminate, then there must be a starting integer from which it is possible to make an infinite sequence of plays. Consider the least level in which there is such a starting integer.