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 mth Turing machine halts, it puts m in the bag. In this case, the program also checks to see what number the mth Turing machine output when it halted; call it m_1. If eventually the m_1th Turing machine halts, the program takes m out of the bag. In this case, the program also checks to see what number the m_1th Turing machine output when it halted; call it m_2. If eventually the m_2th 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 mth 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s