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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
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.
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.
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
==> A language is recursive if there exists a Turing machine that accepts every string in the language and rejects if it is not in the language. for example lets take Turing machine M and String w: if string w is a member of the Turing machine M, then M halts in its final state otherwise it rejects the computation. ==>==> A language is recursive enumerable if there exists a Turing machine that accepts every string in the language and rejects if it is not in the language may be loop forever. for example lets take Turing machine M and String w: if string w is in the language , then M halts in its final state. Otherwise it rejects the computation or may be run forever.