Recursive and recursively enumerable language definition for a layman

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?

Answer

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.

Attribution
Source : Link , Question Author : samsri , Answer Author : Community

Leave a Comment