(Notation:

RE - Recursively Enumerable - Turing-Recognizable Language

R - Recursive - Turing-Decidable Language)

In class, we discussed the following fact: L E RE iff there exists an enumerator for L. Recall that an enumerator is a machine which outputs an infinite list of strings such that for any x L, the enumerator outputs r after some finite time. Suppose that the enumerator first outputs the string E and then r2 E , and so on. For this problem, let us restrict the sequence of strings that the enumerator can output. Namely, define a monotone enumerator as any enumerator with the following guarantees: 1. Xi?2'y for all i j, and 2. 1x1 Ix, l for all i ? j (a) [10 points] Prove the following statement: L e R iff these exists a monotone enu merator for L (b) [10 points] Prove the following statement: If L E RE and infinite, then there exists infinite language L' C L such the L' E R. Hint: You may use part (a). In class, we discussed the following fact: L E RE iff there exists an enumerator for L. Recall that an enumerator is a machine which outputs an infinite list of strings such that for any x L, the enumerator outputs r after some finite time. Suppose that the enumerator first outputs the string E and then r2 E , and so on. For this problem, let us restrict the sequence of strings that the enumerator can output. Namely, define a monotone enumerator as any enumerator with the following guarantees: 1. Xi?2'y for all i j, and 2. 1x1 Ix, l for all i ? j (a) [10 points] Prove the following statement: L e R iff these exists a monotone enu merator for L (b) [10 points] Prove the following statement: If L E RE and infinite, then there exists infinite language L' C L such the L' E R. Hint: You may use part (a)