Redirected from Recursively enumerable
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:
The equivalency 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 nonempty), 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 nonempty). The following algorithm enumerates L:
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:
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".
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:
All regular, contextfree, contextsensitive and recursive languages are recursively enumerable. Some problems are so difficult that they aren't even recursively enumerable. One example is this problem:
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:
If L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:
Search Encyclopedia

Featured Article
