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?
$\begingroup$
$\endgroup$
0
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Dec 25, 2012 at 4:04
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ 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?. $\endgroup$– babouSep 13, 2014 at 6:55
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
==> 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.
