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