Recursively enumerable language

A formal language L is said to be partially decidable or recursively enumerable or Turing-recognizable if there is an algorithm with the following behavior:

Definition 1. Given string w as input, the algorithm halts and outputs YES if and only if w belongs to the language L. If w does not belong to the language L, the algorithm either runs forever, or halts and outputs NO.

To formalize the rather vague term "algorithm", one usually employs Turing machines, but several other equivalent approaches are possible.

Another equivalent definition is that a language L is recursively enumerable if it is empty or if there is an algorithm which enumerates the members of the language in the following sense:

Definition 2. The algorithm takes a positive integer, say n as an argument, and produces as output a string in the language L. For every string s which is in L there must be an n so that the algorithm produces the string s.

This is merely a special case of the concept of a recursively enumerable set.

The equivalence of these two definitions can be seen as follows:

1 -> 2 Given an algorithm A according to the first definition for language L (assumed to be non-empty), the following algorithm will enumerate L according to the second definition: Let E be an algorithm which enumerates all strings, and so that every string appears infinitely often in the enumeration. We write E(n) to denote the string produced by algorithm E on input n. Pick a fixed string t in L (possible since L is non-empty). The following algorithm enumerates L:

Given integer n, run algorithm A on input E(n) for n steps. If the answer is YES, output the string E(n). Otherwise, output string t.

This algorithm will only output strings from L, and it will output all of them, since for every string s in L we can find an integer n which is greater than the number of steps that A needs to accept s and such that E(n) = s.

2 -> 1 Given an algorithm A according to the second definition for language L, the following algorithm will answer the question whether a given string s belongs to L in the sense of the first definition:

For all numbers n, starting with 1, and continuing in sequence, test whether the string produced by algorithm A on input n is equal to s. When the first such n is found, output YES. (Otherwise, continue the LOOP)

Note that, if L is infinite, the enumerating algorithm provided by definition 2 can be chosen so that it avoids repetitions, since we can test whether the string produced for number n is "already" produced for a number which is less than n. If it already is produced, use the output for input n+1 instead (recursively), but again, test whether it is "new".

Examples

Some partially decidable languages have an algorithm that always halts and answers YES or NO correctly. Those languages are called decidable languages or recursive languages. Some problems are recursively enumerable but not recursive. One example is the halting problem, which is the problem:

Given a program and input parameters, will that program eventually halt when run with those parameters?

Phrased as a formal language, this one consists of all those strings which encode a program and input parameters (according to an agreed-upon encoding) such that the program run with those parameters will eventually halt.

Another example is:

Given a polynomial (in several variables) with integer coefficients, is it possible to find integer values for the variables so that the polynomial evaluates to zero? (This is Hilbert's Tenth Problem, more under Matiyasevich's theorem.)

All regular, context-free, context-sensitive and recursive languages are recursively enumerable. Some problems are so difficult that they aren't even recursively enumerable. One example is this problem:

Given a program, input parameters, and a prediction about whether it will eventually halt, is that prediction correct?

In general, if a language L is not recursive, then the language consisting of all strings together with a marker symbol saying whether it is or is not in L is not recursively enumerable.

Another example of a problem that is not recursively enumerable is this:

Given a program and input parameters, will that program run forever?

Properties

If L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:

• the Kleene star L^* of L
• the concatentation LP of L and P
• the union L∪P
• the intersection L∩P

Note that the set difference L\\P and in particular the complement of L need not be recursively enumerable. In fact, a language L is recursive if and only if L and its complement are both recursively enumerable.