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.
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.
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.
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)
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:
Another example is:
Examples
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.
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?
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