Closure Properties of Recursive Languages

In mathematics, logic and computer science, a recursively enumerable language is a type of formal language, also known as partially decidable or Turing-recognizable. In the Chomsky hierarchy it is known as a type-0 language. The class of all recursively enumerable languages is called RE.

Definitions

There are three main equivalent definitions of the concept of a recursively enumerable language.

1. A recursively enumerable formal language is a recursively enumerable subset of the set of all possible words over the alphabet of the language.
2. A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that enumerates all valid strings of the language. Note that if the language is infinite, one can choose an enumeration algorithm that avoids repetitions, since for the string with number n one can check whether it has "already" been output under a number less than n. If it has, then the output number n+1 is used instead (recursively), again checking whether it is "new".
3. A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that halts and accepts any input string from the language, but halts and rejects, or does not halt at all, for any input string not in the language. Recursive languages require the Turing machine to halt in every case.

All regular, context-free, context-sensitive and recursive languages are recursively enumerable.

Post's theorem shows that RE, together with its complement co-RE, corresponds to the first level of the arithmetical hierarchy.

Closure properties

Recursively enumerable languages are closed under the following operations. Let L and P be two recursively enumerable languages; then the following languages are also recursively enumerable:

• the Kleene star of L
• the concatenation of L and P
• the union
• the intersection

Note that recursively enumerable languages are not closed under set difference or complement. The set difference L\P may or may not be recursively enumerable. If L is recursively enumerable, then the complement of L is recursively enumerable if and only if L is also recursive.

Closure of recursive languages under various operations is a property of programming languages that can describe computable functions using recursion. Let us consider some operations that can be applied to recursive languages:

1. Union: If L1 and L2 are recursive languages, then their union 2L1∪L2 is also a recursive language. This follows from the fact that the union of two recursive sets can also be described using recursion.

2. Intersection: If L1 and L2 are recursive languages, then their intersection 2L1∩L2 is also a recursive language. This requires creating additional rules describing the conditions under which strings belong to both L1 and L2.

3. Concatenation: If L1 and L2 are recursive languages, then their concatenation 2L1⋅L2 is also a recursive language. The rules of recursive concatenation can be defined using recursive functions.

4. Kleene Closure: If L is a recursive language, then its Kleene closure L∗ is also a recursive language. This is due to the ability to describe repeating patterns using recursion.

5. Set Difference: If L1 and L2 are recursive languages, then their difference L1−L2 is also a recursive language, provided that the rules of the difference are defined using recursive rules.

These operations make it possible to build new recursive languages from existing ones. Closure under these operations is due to the fact that the rules for these operations can be formulated using recursion, which is a characteristic feature of recursive languages.

Example

The set of halting Turing machines is recursively enumerable but not recursive. Indeed, one can run a Turing machine and accept if the machine halts, hence the set is recursively enumerable. On the other hand, the problem is undecidable.

Some other recursively enumerable languages that are not recursive include:

• The Post correspondence problem
• Mortality (halting problem) (computability theory)

• Entscheidungsproblem (decision problem)

See also

• Computably enumerable set
• Recursion