LANGUAGE GENERATED BY M

is eventually printed on the output tape of M}

e.g.

Lemma:
If L is for some TM , then L is a recursively enumerable set.

Converse: If a language is r.e., then it is for some TM .

Proof of the Converse:
Let L be an r.e. set recognized by TM M. Canonical order on :

List words in order of size.
If same size, then numerical order.

If

Is this correct?

• Pair Genetator: :
• Characterization of Recursive Sets by Generators