One thing I understand is that the complement of every Turing recognizable(but not decidable) language is non Turing recognizable.

What about the complement of non Turing recognizable language? Is the complement of every non r.e a recognizable language.

I don't know how to approach this problem.

But one idea I had was this:

If the complement of every non r.e were a r.e language then there would be a bijection from r.e to non r.e. This bijection maps a r.e to a non r.e . The set of r.e languages is countable(even though infinite). If a bijection exists then non r.e would also be countable. But the union of r.e and non r.e is uncountable. This means one of them must be uncountable. So the original supposition must be wrong.

I am new to coutability and such things. So it may be possible that the idea is compeletely wrong.

Anyhow can someone provide an approach to this problem.


1 Answer 1


Your proof is fine. There are also explicit languages which are neither r.e. nor co-r.e., for example the language of all total Turing machines (Turing machines halting on every input).

In fact, the language of all total Turing machines is $\Pi_2$-complete, which means, in a sense, that there is no better way to "solve" it than to run all on inputs and see whether the given machine halts on each of them (of course, you can't do this with a Turing machine, but perhaps with a more powerful device...). Take a look at the arithmetical hierarchy for more on this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.