Recursive vs recursively enumerable language in Turing Machines?

We say language L is recursive if it is decided by a TM.

L is recursively enumerable (r.e.) if it's recognized by a TM.

Suppose, enumerator (en-r) is a deterministic Turing Machine with a printer that starts with a blank tape and can print strings s1, s2, s3, s4... sn... continuing forever if the language is infinite.

The program needs to generate the strings that are being printed, so this is a Turing Machine that generates on the tape somewhere, all of the strings in the language. I can store other things on the tape as well.

The language of an en-r is the set of all strings it prints. En-r is a generator machine, not a recognizer machine.

For enumerator EN we say L(EN) = {s| EN prints s}.

I have 3 questions regarding this situation:

1. Suppose L is an r.e. set, then how do we use the recognizer to create an enumerator for L?

2. If L is a language and there is an enumerator that enumerates L in increasing order, then why is L recursive?

3. Why is it that if L is recursive then there is an en-r that enumerates it in increasing order?

Thanks

I’ll address question (1) last, since it’s probably the trickiest of them.

For (2), suppose you have an enumerator that prints the set in increasing order. To build a decider from it, do the following. Take your input string w, then run the enumerator until one of the following things happen:

1. The enumerator prints your input w. In that case, your input w is definitely in the language.
2. The enumerator prints a string x where w < x. In that case, the enumerator didn’t print your string, and since all the outputs z of the enumerator from this point satisfy w < x < z, it will never print your input. You can then reject.
3. The enumerator halts without printing your input string w. In that case, it’s definitely not in the language, and you can reject.

One of those three options is guaranteed to happen, so you can guarantee that the procedure halts on all inputs and is therefore a decider.

For (3), suppose D is a decider for your language. Here’s pseudocode for an enumerator that prints the strings in the language in increasing order:

for each string w, in increasing order:
    run D on w.
    if D accepts w, print w.

Do you see why this prints the set S in sorted order?

Now, back to (1). There are a couple of ways to prove this. The traditional one is to use the idea of dovetailing. Imagine writing out all strings in the order w0, w1, w2, w3, … in some order. Then, execute this piece of code, assuming R is a recognizer for L:

for i = 1 to infinity
    for j = 0 to i:
        run R on w_j for i - j steps.
        if R accepted, print w_j.

The idea is that for each string w_j in L, there’s some choice of i where R accepts w_j in i - j steps, so this will eventually print every string in L.