Recursively Enumerable Languages
Theorem: For every URG G, there is an TM  M         such that L(G) = L(M).
Proof: See page 714 in [Meduna: Automata and Languages]
Conclusion: The fundamental models for recursively  enumerable languages are
1) Unrestricted grammars
2) Turing Machines
Definition: Let L be a language. L is a resurcively enumerable language if there exists an Turing machine M that L = L(M).
Theorem: For every TM M, there is an URG G         such that L(M) = L(G).
Proof: See page 715 in [Meduna: Automata and Languages]
29/45