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?
migrated from cstheory.stackexchange.com Apr 26 '11 at 2:06
This question came from our site for theoretical computer scientists and researchers in related fields.
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).