Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

add comment

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.