Take the 2-minute tour ×

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?

share|improve this question
add comment

migrated from cstheory.stackexchange.com Apr 26 '11 at 2:06


1 Answer

up vote 8 down vote accepted

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).

share|improve this answer
add comment

Your Answer


