Relationship between Undecidable Problems and Recursively Enumerable languages

Problem Detail: 

I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting problem belongs to a class of languages which are not even recursively enumerable. But the article suggests that the halting problem is recursively enumerable. My doubt is about the relationship between undecidable problems and recursively enumerable languages. Are all undecidable problems recursively enumerable languages?

If there is a problem which belongs to the class of non recursively enumerable languages, will it be always undecidable?

Also could any one suggest a problem which is not even recursively enumerable?

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