1
$\begingroup$

I'd like to read up on non-recursively enumerable languages. Which textbooks should I look into to get a decent understanding about the subject?

Thank you.

$\endgroup$
3
$\begingroup$

Despite its name, Soare's book Recursively enumerable sets and degrees has lots of information about this. In particular, it covers in pretty good detail the arithmetical hierarchy.

(Incidentally, note that the non-r.e. elements of the arithmetical hierarchy aren't all "r.e.-hard." For example, consider any minimal $\Delta^0_2$ degree, that is any Turing degree $\le_T{\bf 0'}$ which is nonzero but not strictly above any nonzero Turing degree. There are infinitely many minimal $\Delta^0_2$ degrees; by the Sacks Density Theorem, they are all non-r.e. and hence by minimality don't compute any nonrecursive r.e. sets. The way in which the r.e. degrees sit inside the $\Delta^0_2$ degrees is actually fairly complicated.)

$\endgroup$
1
  • $\begingroup$ I'm going to have to accept this because I like that it covers arith. hierarchy. $\endgroup$ Jul 14 '20 at 23:17
2
$\begingroup$

Any book on computability will cover the subject.

In any case, if a language is not recursively enumerable, it means no Turing machine (or program in any language, for that matter) is able to recognize it's members, not even given unlimited time to check. That essentially tells you that they are languages that are very hard to characterize.

There is an extension to Rice's theorem that characterizes languages that are recursively enumerable, that is a starting point for your quest.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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