I am simply wondering, as the title states, what the central differences are between recursive and recursively enumerable languages? If I am not mistaken a recursive language is a is Turing decidable while a recursively enumerable one is only Turing recognizable but I suspect that is either wrong or does not capture the whole picture. Can anybody give a brief answer?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Recursive / Turing-decidable languages have a Turing machine that can always decide in finite time whether a word is in the language.
Recursively enumerable / RE / Turing-recognizable languages have a Turing machine that will accept a word in the language in finite time, but not necessarily stop to reject a word that's not in the language.
Recursive implies RE but not vice versa.
A language and its complement are RE if and only if the language is recursive (which is equivalent to saying that the complement of the language is recursive).
answered Apr 26, 2011 at 2:12