Describe recursive languages and recursively enumerable languages.
What is Recursive Language
-
A recursive language is a formal language for which there exists a Turing machine that, when presented with any finite input string, halts and accepts if the string is in the language, and halts and rejects otherwise.
-
The Turing machine always halts: it is known as a decider and is said to decide the recursive language.
-
As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set L={abc, aabbcc, aaabbbccc, ...}; more formally, the set
-
L = { w ∈ {a,b,c}* | w = anbncn for some n ≥ 1}
-
is context-sensitive and therefore recursive.
What is Recursively Enumerable Language
-
A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) which will enumerate all valid strings of the language.
-
Note that if the language is infinite, the enumerating algorithm provided 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".
-
A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language.
-
Contrast this to recursive languages, which require that the Turing machine halts in all cases.
