Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

migrated from Apr 26 '11 at 2:06

This question came from our site for theoretical computer scientists and researchers in related fields.

up vote 9 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|cite|improve this answer

Your Answer


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.