0
$\begingroup$

If so what are they? These are Computational Complexity Classes that are not in RE but are in ALL. What would a problem in one of these classes look like? Would any of these problems be decidable?

$\endgroup$
4
  • 1
    $\begingroup$ For example, see en.wikipedia.org/wiki/Arithmetical_hierarchy . $\endgroup$ Nov 26, 2021 at 13:21
  • $\begingroup$ Any class that contains RE has undecidable problems. $\endgroup$ Nov 26, 2021 at 14:50
  • $\begingroup$ @Yuval Filmus. Yes i know that. But what I'm asking is are there any decidable problems that are not in RE? $\endgroup$ Nov 26, 2021 at 19:57
  • 1
    $\begingroup$ RE contains all decidable problems. $\endgroup$ Nov 26, 2021 at 22:19

1 Answer 1

1
$\begingroup$

As has been commented above, decidability implies recursive enumerability - indeed, one of the standard exercises in any computability theory book is proving that a set is decidable iff it is both r.e. and co-r.e. (note that "decidable," "recursive," and "computable" are all synonyms). So no, a fortiori there are no decidable problems outside of $\mathsf{RE}$.

But that doesn't mean that there aren't interesting non-r.e. problems or classes of problems. For example, the set $\mathsf{Tot}$ of (indices for) Turing machines which halt on all inputs is strictly more complicated than any r.e. set; in a precise sense it is the halting problem's halting problem.

A good starting point here is the arithmetical hierarchy. This may seem abstract at first, but results like Post's theorem and Shoenfield's lemma will help demystify it. And even that is only the start of the very intricate picture; further keywords include "hyperarithmetic" and "projective."

I strongly recommend the treatment in the first part of Soare's original recursion theory textbook.

$\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.