# Another Puzzle in Recursion Theory: n-Enumerable Sets

We can think of a computably enumerable (or c.e.) set as a bag which some computer program puts more and more numbers into over time. The set then consists of all numbers which are in the bag from some point on (i.e., the numbers which are eventually put in the bag by the program).

Suppose that we relax the restrictions on the program, and we allow it to take a number out of the bag that it has put in (but once the program has done that, the number stays out forever). We call the set of numbers which are in the bag from some point on (i.e., the set of numbers which are put in the bag and never taken out) in a procedure of this sort a 2-c.e. set.

We can analogously let an $n$-c.e. set be one given by a program which can, for each number, “toggle” that number’s status up to and including $n$ times if it likes.

The puzzle is then to find, for each $n$, an example of a set which is $n$-c.e. but not $n-1$-c.e.

Here is an example of a set which is $n$-c.e. but not $n-1$-c.e.: The program simulates all Turing machines simultaneously (by dovetailing, this can still be done with a finite algorithm).

For each $m$ it does the following: If the $m$th Turing machine halts, it puts $m$ in the bag. In this case, the program also checks to see what number the $m$th Turing machine output when it halted; call it $m_1$. If eventually the $m_1$th Turing machine halts, the program takes $m$ out of the bag. In this case, the program also checks to see what number the $m_1$th Turing machine output when it halted; call it $m_2$. If eventually the $m_2$th Turing machine halts, the program puts $m$ back in the bag. And so on, up to a maximum of $n$ times.

Call that set $S_n$. Clearly it’s $n$-c.e. We have to show that it’s not $n-1$-c.e.

First observe that each $S_n$ is complete with respect to $n$-c.e. sets. This means that if $S$ is $n$-c.e., then there is a computable function $f$ such that $m\in S$ iff $f(m)\in S_n$ for all $m\in\mathbb{N}$.

Now observe that if $S_n$ is $n-1$-c.e., then its complement $\bar{S_n}$ is $n$-c.e. We can find an $n$-c.e. presentation of $\bar{S_n}$ by letting our computer program start by putting all numbers in the bag and then doing the opposite of what the $n-1$-c.e. presentation of $S_n$ does.

Combining these two observations, there is a computable function $f$ such that for all $m\in\mathbb{N}$, $m\in S_n$ iff $f(m) \notin S_n$. By Kleene’s Fixed Point Theorem (also known as Kleene’s Recursion Theorem), there is an $m$ such the $m$th Turing machine behaves the same as the $f(m)$th Turing machine. For this particular $m$ we then have that $m\in S_n$ iff $m\notin S_n$, which is a contradiction.