Definition and Examples

Definition and Examples

A recursively enumerable language is a type of formal language that can be recognised by a Turing machine. This means that there exists a Turing machine that will accept any string in the language, but it may not halt for strings not in the language. In contrast, a recursively decidable language has a Turing machine that will halt for all strings, accepting those in the language and rejecting those not in it.

Definition of Recursively Enumerable Languages

A language L is recursively enumerable if there exists a Turing machine M such that:

• If a string w is in L, M accepts w (halts and enters an accepting state).
• If a string w is not in L, M may either reject w (halt and enter a rejecting state) or run indefinitely (not halt).

In formal terms, we define a recursively enumerable language as follows:

L is recursively enumerable if there exists a Turing machine M such that:

M(w) = accepted if w ∈ L

M(w) = not accepted if w ∉ L (may run indefinitely)

Examples of Recursively Enumerable Languages

Example 1: The Language of All Strings Over {0, 1}

Consider the language L1 = {w | w is a string over the alphabet {0, 1}}. This language includes all possible strings formed by the symbols 0 and 1. A Turing machine M that accepts this language can be defined as follows:

1. Read the input string w.
2. Since every string over {0, 1} is valid, M will enter the accepting state after reading the entire string.

Thus, L1 is recursively enumerable because the Turing machine always halts and accepts any string in the language.

Example 2: The Halting Problem

The Halting Problem is another classic example of a recursively enumerable language. This problem involves determining whether a given Turing machine M halts on a given input w. We can define the language L2 as follows:

L2 = { (M, w) | M is a Turing machine and M halts on input w }

To show that L2 is recursively enumerable, we can construct a Turing machine M that operates as follows:

1. Simulate the execution of M on input w.
2. If M halts, accept (enter the accepting state).
3. If M does not halt, do not accept (run indefinitely).

Therefore, L2 is recursively enumerable because there exists a Turing machine that accepts all pairs (M, w) where M halts on w, but it may run indefinitely for pairs where M does not halt.

Example 3: The Language of Valid Parentheses

Consider the language L3 = {w | w contains valid parentheses}. This language includes strings such as "()", "(())", and "(()())". To show that L3 is recursively enumerable, we can define a Turing machine M:

1. Read the input string w.
2. Use a stack to keep track of the parentheses.
3. For each opening parenthesis '(', push onto the stack.
4. For each closing parenthesis ')', pop from the stack if there is a matching opening parenthesis.
5. If the stack is empty after processing the entire string, accept (valid parentheses).

Thus, L3 is recursively enumerable because the Turing machine accepts valid strings of parentheses but may run indefinitely for invalid strings.

Characteristics of Recursively Enumerable Languages

Recursively enumerable languages have several important characteristics:

• They can be recognised by Turing machines.
• They may not be decidable, meaning there is no guarantee that a Turing machine will halt for all inputs.
• They can be generated by context-free grammars or recursively enumerable grammars.

Relation to Other Language Classes

Recursively enumerable languages are part of the Chomsky hierarchy, which classifies languages into four types:

1. Type 0: Recursively enumerable languages (Turing machines)
2. Type 1: Context-sensitive languages (Linear-bounded automata)
3. Type 2: Context-free languages (Pushdown automata)
4. Type 3: Regular languages (Finite automata)

Every regular language is context-free, every context-free language is context-sensitive, and every context-sensitive language is recursively enumerable. However, the reverse is not true.

Conclusion

In summary, recursively enumerable languages can be recognised by Turing machines, but they are not necessarily decidable. Examples include the language of all strings over a given alphabet, the Halting Problem, and the language of valid parentheses. Understanding these languages is crucial for exploring more complex topics such as Turing machines and their properties.

Check your understanding

• What defines a recursively enumerable language?
• Give an example of a recursively enumerable language and explain why it is recursively enumerable.
• What is the difference between a recursively enumerable language and a decidable language?
• Explain how the Halting Problem is related to recursively enumerable languages.