Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are .

Can some one please tell me what they are in simple words?

Thanks in advance.

share|improve this question

migrated from cstheory.stackexchange.com Dec 24 '12 at 21:27

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

5 Answers 5

up vote 4 down vote accepted

Not really. You should read a few books. Perhaps we can recommend some.

That said, a language is recursive if there is a Turing machine than can always reply "yes" or "no" if a given string is part of this language. If we lift this requirement to merely say "yes" for strings of the language (it can run forever if it is not) then we have a recursively enumerable language. It is not hard to see, that a recursive language can be decided by a Turing machine, while a recursively enumerable language can have its strings listed (for example, by running an infinite number of Turing machines in parallel — yes this is possible, see dove-tailing — on all strings of the alphabet, and outputting a string if the corresponding TM accepts). There are many, many equivalent definitions.

share|improve this answer

A problem is recursive or decidable if a machine can compute the answer.

A problem is recursively enumerable or semidecidable if a machine can be convinced that the answer is positive.

share|improve this answer

A Language is just a set of strings. Possibly of infinite cardinality.

A language is recursive enumerable if there exists a TM that keeps outputting strings that belong to the language (and only such strings), such that eventually every string in the language will be in the output.

A language is recursive if, the above TM not only outputs all the strings in the language, but also do it in order! (say, lexicographically).

I'm sure you can easily think of recursive languages (and build a TM that outputs them by order). It's quite difficult to come up with recursive enumerable languages (that are not recursive), unless you read some more about undecidability and diagonalization. But such languages do exist.

share|improve this answer
    
To me your definition is best, up to one detail: the order must be a computable order: it must be possible to compare any two strings with a terminating TM. Many of the other definitions confuse enumerability and decidability. These are different concepts, though they can be proved equivalent for sets of finite strings.(see for example: Can languages with infinite strings be recursively enumerable?. –  babou Sep 13 at 6:55

I feel the main difference between recursive and recursively enumerable languages is that Recursive Turing machine halts in non-final state if it does not accepts a string

Recursively enumerable Turing machine if it not accepts a string may halt in non final state or loop for ever which is not the case for recursive languages

share|improve this answer

Recursive languages are decidable by some Turing Machine, i.e., there is a TM that can, given any input string (over the appropriate alphabet) correctly answer yes if the string is in the language, or no if it isn't.

Recursively enumerable languages are only recognized, i.e., there exists a Turing Machine that accepts when the string is in the language but it may loop forever if the string is not in the language.

share|improve this answer

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.