Asked By : Deepu
Answered By : Patrick87
Are all undecidable problems recursively enumerable languages?
No. See my answer to your third question.
If there is a problem which belongs to the class of non recursively enumerable languages, will it be always undecidable?
Yes. In particular, recursive (decidable) languages are a subset of the recursively enumerable languages, so anything that’s not recursively enumerable isn’t recursive (decidable).
Also could any one suggest a problem which is not even recursively enumerable?
The complement of the halting problem is not recursively enumerable. Suppose that it were. Then you could begin recursively enumerating the set $H$ of halting programs at the same time that I’m recursively enumerating the set $H’$ of non-halting programs. Every program would eventually be listed by one of us; if you listed it, you’d shout “accept” and I’d stop enumerating, and if I listed it, I’d shout “reject” and you’d stop enumerating. We’d have an effective procedure for deciding the halting problem. Note that this generalizes: the complement of any recursively-enumerable (but non-recursive) problem is non-recursively-enumerable, for the reason outlined above.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12747