next up previous contents
Next: Enumeration means listing only Up: Recursively Enumerable Languages Previous: Recursively Enumerable Languages

r.e. languages enumerable by TMs

The set of recursively enumerable (r.e.) languages are precisely those languages which can be listed (enumerated) by a TM. Basically, if a TM can generate all the strings in a language, a TM can accept all the strings in a language.