Recursively Enumerable Languages

The most general class of languages processed by automata are the recursively enumerable (RE) languages—those that are recognized by a Turing machine. There are important subcategories within the RE languages that we’ll also explore. Most languages of practical use are in the subset of RE languages known as recursive languages. We’ll also lift all restrictions on rewriting systems to obtain grammars that generate the recursively enumerable languages.

Definition of recursively enumerable languages

A recursively enumerable language is a language that has an associated Turing machine that recognizes all and only the strings in the language. It may “hang” (run forever) when given an input string which is not in the language.

The term “recognized” is crucial. A $\text{TM}$ recognizes an input string if it halts in an accepting state when processing it. The set of all such strings constitutes the language of the $\text{TM}$. If an input string is not in the language, the $\text{TM}$ may (rarely) halt and reject it, or it may (more likely) get stuck in an infinite loop (“hang”). In other words, it knows one when it sees one, but it can’t always tell when a string is not in the language. This is a consequence of the fact that $\text{TM}$s do not always halt. All the languages that we have seen so far are recognized by $\text{TM}$s that always halt (i.e., they are decided by the $\text{TM}$). We must do a bit of work to contrive a language that is RE but not recursive.

Definition of a recursive language

A recursive language is a language that has an associated $\text{TM}$ that decides all input strings. The machine always halts, explicitly accepting all the strings in the language and rejecting those not in the language.

In other words, there is an algorithm that decides whether or not any given string is in a recursive language. We say that the $\text{TM}$ “decides” the language, instead of just “recognizing” it.

Remember: A recursively enumerable language has a Turing machine that recognizes it (it may hang on strings outside the language). A recursive language has a Turing machine that always halts, deciding each string. ...